hackercupai/hackercup

1Carlos has been working in technology so long that he's starting to feel a bit2burnt out. Hoping to rejuvenate himself, Carlos has been seeking out more3artistic opportunities.4 5Yamaha, the well-known creator of musical apparatus, has approached Carlos6with a request that might be right up his alley: they'd like him to design a7brand new instrument. Immediately, Carlos knows what to do.8 9_ "You may have seen Pat Metheny's 42-string guitar, but that's nothing10compared to what we're going to make together." _11 12Carlos presents his plan for a 1,000-string guitar, complete with programmatic13tuning so that you don't need to turn 1,000 knobs by hand. Yamaha's market14research suggests that these sorts of guitars would be great for playing15palindromic chords, chords where the first string plays the same note as the16last string, the second string plays the same note as the second-to-last17string, and so on. Carlos is quickly tasked with developing default tunings18for the strings so that the guitars are ready to play right out of the box.19 20For various integers **K**, Carlos wants to find a set of at most 1,00021strings on which exactly **K** distinct palindromic chords can be played. The22guitar's strings are arranged in a line, and each one must be tuned to a note23from the set {A, B, C, D, E, F, G}. A chord is then played by strumming a24contiguous subset of 1 or more strings. Two chords are considered to be25distinct if there is at least one string that is used in one chord but not the26other; chords involving the same notes but different strings are considered27different.28 29For example, if **K** = 9, a set of 7 strings could be tuned to the notes C,30A, B, B, A, G, E in order from left to right. You can play 7 different31palindromic chords by strumming single strings, the chord BB by strumming the323rd and 4th strings, and the chord ABBA by strumming the 2nd, 3rd, 4th, and335th strings. This is a total of 9 distinct palindromic chords. **34 35Output any non-empty string of valid musical notes, with length at most 1,000,36representing the tunings of sequential strings. An aspiring musician must be37able to play exactly **K** distinct palindromic chords on these strings. It's38guaranteed that there is at least one valid output for each possible valid39input.40 41### Input42 43Input begins with an integer **T**, the number of tunings that Carlos needs to44figure out.  45For each tuning, there is a single line containing the integer **K**.46 47### Output48 49For the _i_th tuning, print a line containing "Case #_i_: " followed by a50string of up to 1,000 characters representing a tuning of strings as described51above on which exactly **K** distinct palindromic chords can be played.52 53### Constraints54 551 ≤ **T** ≤ 500  561 ≤ **K** ≤ 100,000  57 58### Explanation of Sample59 60In the first case, "ACE" is a valid output as it contains exactly 361palindromes: "A", "C", and "E". On the other hand, "DAD" would not be valid as62it contains 4 palindromes.63 64In the second case, "GAGA" is a valid output as it contains exactly 665palindromes: "G", "A", "G", "A", "GAG", and "AGA".66 67**_Note that other outputs would also be accepted for each sample case._**68 69