Yet Another Contest 1 P4 - No More Searching

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Java 4.0s
Python 2.0s
Memory limit: 128M
Java 256M
Python 256M

Author:
Problem types

Mike is growing tired of searching for strings, and has instead become interested in breaking them apart! Given a string S, he wants to break it into any number of subsequences. Each character in S should belong to exactly one subsequence.

The i-th letter in the English alphabet is assigned the value i (e.g. A1, B2, ..., Z26).

For each subsequence, let vci and vcj be the value of the first and last characters. Then, the score of the subsequence is equal to (vcivcj)(vci+vcj). Note that scores can be negative. For example, the sequence HELLO will have a score of (815)(8+15)=161.

The total score of a string is equal to the sum of all the scores of its subsequences. To satisfy Mike's curiosity, you want to determine all the possible total scores for a given string.

Constraints

1N250

S only consists of uppercase letters A...Z.

Subtask 1 [10%]

1N5

Subtask 2 [10%]

S only consists of uppercase letters A and B.

Subtask 3 [30%]

1N50

Subtask 4 [50%]

No additional constraints.

Input Specification

The first line contains one integer N, the length of the string.

The second line contains the string S.

Output Specification

On the first line, output a single integer M, the total number of possible scores.

On the next M lines, output the possible scores sorted in ascending order.

Sample Input 1

Copy
3
ADB

Sample Output 1

Copy
4
-15
-3
0
12

Explanation for Sample Output 1

There are five possible ways to break up the string into subsequences:

AD B

The total score for the first arrangement is (14)(1+4)+(22)(2+2)=15.

AB D

The total score for the second arrangement is (12)(1+2)+(44)(4+4)=3.

A D B

The total score for the third arrangement is (11)(1+1)+(44)(4+4)+(22)(2+2)=0.

A DB

The total score for the fourth arrangement is (11)(1+1)+(42)(4+2)=12.

ADB

The total score for the fifth arrangement is (12)(1+2)=3, which results in the same total score as the second arrangement.

Sample Input 2

Copy
3
AAC

Sample Output 2

Copy
2
-8
0

Explanation for Sample Output 2

One way to achieve a total score of 8 is by breaking the string into the following subsequences:

A AC

One way to achieve a total score of 0 is by breaking the string into the following subsequences:

AA C

Sample Input 3

Copy
4
ABAB

Sample Output 3

Copy
4
-6
-3
0
3

Sample Input 4

Copy
4
JHVM

Sample Output 4

Copy
9
-489
-420
-384
-105
-69
0
36
315
351

Comments

There are no comments at the moment.