## Yet Another Contest 1 P4 - No More Searching

View as PDF

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 , he wants to break it into any number of subsequences. Each character in should belong to exactly one subsequence.

The -th letter in the English alphabet is assigned the value (e.g. A, B, ..., Z).

For each subsequence, let and be the value of the first and last characters. Then, the score of the subsequence is equal to . Note that scores can be negative. For example, the sequence HELLO will have a score of .

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

only consists of uppercase letters A...Z.

only consists of uppercase letters A and B.

#### Input Specification

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

The second line contains the string .

#### Output Specification

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

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

#### Sample Input 1

3
ADB

#### Sample Output 1

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 .

AB D

The total score for the second arrangement is .

A D B

The total score for the third arrangement is .

A DB

The total score for the fourth arrangement is .

ADB

The total score for the fifth arrangement is , which results in the same total score as the second arrangement.

#### Sample Input 2

3
AAC

#### Sample Output 2

2
-8
0

#### Explanation for Sample Output 2

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

A AC

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

AA C

#### Sample Input 3

4
ABAB

#### Sample Output 3

4
-6
-3
0
3

#### Sample Input 4

4
JHVM

#### Sample Output 4

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