• 2018-09-08
• 11
• 0

# A. Equality

## Description:

You are given a string s of length n, which consists only of the first k letters of the Latin alphabet. All letters in string s are uppercase.
A subsequence of string s is a string that can be derived from s by deleting some of its symbols without changing the order of the remaining symbols. For example, “ADE” and “BD” are subsequences of “ABCDE”, but “DEA” is not.
A subsequence of s called good if the number of occurences of each of the first k letters of the alphabet is the same.
Find the length of the longest good subsequence of s.

## Input:

The first line of the input contains integers n (1\le n \le 10^5) and k (1 \le k \le 26).
The second line of the input contains the string s of length n. String s only contains uppercase letters from ‘A’ to the k-th letter of Latin alphabet.

## Output

Print the only integer — the length of the longest good subsequence of string s.

9 3
ACAABCCAB

6

9 4
ABCABCABC

0

# B. Non-Coprime Partition

## Description:

Find out if it is possible to partition the first n positive integers into two non-empty disjoint sets S_1 and S_2 such that:
\mathrm{gcd}(\mathrm{sum}(S_1), \mathrm{sum}(S_2)) > 1 Here \mathrm{sum}(S) denotes the sum of all elements present in set S and \mathrm{gcd} means thegreatest common divisor.
Every integer number from 1 to n should be present in exactly one of S_1 or S_2.

## Input:

The only line of the input contains a single integer n (1 \le n \le 45\,000)

## Output

If such partition doesn’t exist, print “No” (quotes for clarity).
Otherwise, print “Yes” (quotes for clarity), followed by two lines, describing S_1 and S_2 respectively.
Each set description starts with the set size, followed by the elements of the set in any order. Each set must be non-empty.
If there are multiple possible partitions — print any of them.

1

No

3

Yes
1 2
2 1 3