WC '18 Contest 4 J4 - Your Name, Please

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type
Woburn Challenge 2018-19 Round 4 - Junior Division

Billy is just about to begin playing the classic role-playing game EarthBound! His first order of business will be to enter a name for his character.

EarthBound's name entry system displays the uppercase letters A through Z in a row, with a cursor indicating the one currently selected (initially A). It also displays the name which the player has entered so far (initially an empty string).

At any point in time, Billy may press a button to perform one of the following actions:

  • <: Move the cursor to the previous letter, wrapping around to the end if necessary (e.g. Y \rightarrow X, A \rightarrow Z)
  • >: Move the cursor to the next letter, wrapping around to the start if necessary (e.g. I \rightarrow J, Z \rightarrow A)
  • A: Append the currently-selected letter to the end of the current name (without moving the cursor)
  • +: Submit the current name, thus completing the name entry process

Given any name, there are multiple possible sequences of button presses which would end up submitting it. However, as the king of video games, Billy will showcase his skills right off the bat by entering his name of choice using the minimum possible number of button presses.

What remains is choosing an appropriate name...

Billy has decided that his name will consist of exactly N (1 \le N
\le 100) letters. To make things particularly interesting, he's also decided to choose a name such that the minimum number of button presses required to enter it is exactly K (1 \le K \le 10\,000).

Help Billy come up with any name satisfying both of the above criteria, or determine that no such name exists!

Input Specification

The first and only line of input consists of two space-separated integers, N and K.

Output Specification

Output a single string, either a valid name consisting of N uppercase letters, or Impossible if no such name exists.

Sample Input 1

2 6

Sample Output 1


Sample Input 2

1 20

Sample Output 2


Sample Explanation

In the first case, CB meets both criteria: it consists of 2 letters, and requires a minimum of exactly 6 button presses to enter (>, >, A, <, A, +). Note that other outputs would also be accepted.

In the second case, there exists no single-letter name whose minimum number of required button presses is exactly 20.


There are no comments at the moment.