## Mock CCC '23 Contest 1 J4 - String Decryption

View as PDF

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

The alphabetical sum of an alphabetic string is defined as the sum of the indices of each character in the alphabet. For example, the alphabetical value of the string abce is , since the indices of a, b, c, and e are , , , and , respectively, and .

Steven has a string which consists strictly of lowercase letters and asterisks. The asterisks can each be replaced with any lowercase letter in the English alphabet.

Given an integer , representing Tommy's desired alphabetical sum, Steven wonders whether it is possible to construct a string with an alphabetical sum of by replacing the asterisks in his string. If it is, he wants to know the lexicographically smallest such string.

Definition: A string is lexicographically smaller than a string if and at the first index where , .

#### Input Specification

The input consists of two lines. The first line contains , representing Tommy's desired alphabetical sum. The second line contains , representing the string Steven has.

The following table shows how the available 15 marks are distributed.

Mark AwardedExpected Alphabetical ValueLength of Steven's String marks   marks  #### Output Specification

If it is impossible to construct a string that satisfies Tommy's expectations, output Impossible.

Otherwise, output the lexicographically smallest string such that the alphabetical sum of the string is .

#### Sample Input 1

2
a*

#### Output for Sample Input 1

aa

#### Explanation of Output for Sample Input 1

The alphabetical sum of aa is . It can be shown that aa is the only possible string in this case.

#### Sample Input 2

4
a**

#### Output for Sample Input 2

aab

#### Explanation of Output for Sample Input 2

The alphabetical value of aab is . Other possible strings like aba also have as the alphabetical sum, but aab is the lexicographically smallest.

#### Sample Input 3

1
a*

#### Output for Sample Input 3

Impossible

#### Explanation of Output for Sample Input 3

It can be shown that we cannot construct a string for this case that has an alphabetical sum of .