Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
英小文字からなる文字列 S が与えられます。S に最も多く出現する文字を求めてください。そのような文字が複数ある場合は、そのうちアルファベット順で最も早いものを答えてください。
制約
- 1 \leq |S| \leq 1000（|S| は文字列 S の長さ）
- S の各文字は英小文字である。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S に最も多く出現する文字のうちアルファベット順で最も早いものを出力せよ。
入力例 1
frequency
出力例 1
e
frequency には e が 2 回出現し、これは他のどの文字よりも多いため e を出力します。
入力例 2
atcoder
出力例 2
a
atcoder には a, t, c, o, d, e, r が 1 回ずつ出現するため、このうちアルファベット順で最も早い a を出力します。
入力例 3
pseudopseudohypoparathyroidism
出力例 3
o
Score: 200 points
Problem Statement
You are given a string S consisting of lowercase English letters. Find the character that appears most frequently in S. If multiple such characters exist, report the one that comes earliest in alphabetical order.
Constraints
- 1 \leq |S| \leq 1000 (|S| is the length of the string S.)
- Each character in S is a lowercase English letter.
Input
The input is given from Standard Input in the following format:
S
Output
Among the characters that appear most frequently in S, print the one that comes earliest in alphabetical order.
Sample Input 1
frequency
Sample Output 1
e
In frequency, the letter e appears twice, which is more than any other character, so you should print e.
Sample Input 2
atcoder
Sample Output 2
a
In atcoder, each of the letters a, t, c, o, d, e, and r appears once, so you should print the earliest in alphabetical order, which is a.
Sample Input 3
pseudopseudohypoparathyroidism
Sample Output 3
o
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
正整数 A,B が与えられます。
A+B を(十進法で)計算する時、繰り上がりが生じないなら Easy 、生じるなら Hard と出力してください。
制約
- A,B は整数
- 1 \le A,B \le 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
繰り上がりが生じないなら Easy 、生じるなら Hard と出力せよ。
入力例 1
229 390
出力例 1
Hard
229+390 を計算する際、十の位から百の位へと繰り上がりが発生します。よって、答えは Hard です。
入力例 2
123456789 9876543210
出力例 2
Easy
繰り上がりは発生しません。答えは Easy です。
また、入力が 32bit 整数に収まらないこともあります。
Score : 200 points
Problem Statement
You are given positive integers A and B.
Let us calculate A+B (in decimal). If it does not involve a carry, print Easy; if it does, print Hard.
Constraints
- A and B are integers.
- 1 \le A,B \le 10^{18}
Input
Input is given from Standard Input in the following format:
A B
Output
If the calculation does not involve a carry, print Easy; if it does, print Hard.
Sample Input 1
229 390
Sample Output 1
Hard
When calculating 229+390, we have a carry from the tens digit to the hundreds digit, so the answer is Hard.
Sample Input 2
123456789 9876543210
Sample Output 2
Easy
We do not have a carry here; the answer is Easy.
Note that the input may not fit into a 32-bit integer.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
英小文字のみからなる長さ N の文字列 S が与えられます。
S の文字を並び替えて得られる文字列（S 自身を含む）であって、長さ K の回文を部分文字列として 含まない ものの個数を求めてください。
ただし、長さ N の文字列 T が「長さ K の回文を部分文字列として含む」とは、
ある (N-K) 以下の非負整数 i が存在して、1 以上 K 以下の任意の整数 j について T_{i+j}=T_{i+K+1-j} が成り立つことをいいます。
ここで、T_k は文字列 T の k 文字目を表すものとします。
制約
- 2\leq K \leq N \leq 10
- N,K は整数
- S は英小文字のみからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N K S
出力
S の文字を並び替えて得られる文字列であって、長さ K の回文を部分文字列として含まないものの個数を出力せよ。
入力例 1
3 2 aab
出力例 1
1
aab を並び替えて得られる文字列は aab, aba, baa の 3 つであり、このうち aab および baa は長さ 2 の回文 aa を部分文字列として含んでいます。
よって、条件をみたす文字列は aba のみであり、1 を出力します。
入力例 2
5 3 zzyyx
出力例 2
16
zzyyx を並べて得られる文字列は 30 個ありますが、そのうち長さ 3 の回文を含まないようなものは 16 個です。よって、16 を出力します。
入力例 3
10 5 abcwxyzyxw
出力例 3
440640
Score : 300 points
Problem Statement
You are given a string S of length N consisting only of lowercase English letters.
Find the number of strings obtained by permuting the characters of S (including the string S itself) that do not contain a palindrome of length K as a substring.
Here, a string T of length N is said to "contain a palindrome of length K as a substring" if and only if there exists a non-negative integer i not greater than (N-K) such that T_{i+j} = T_{i+K+1-j} for every integer j with 1 \leq j \leq K.
Here, T_k denotes the k-th character of the string T.
Constraints
- 2 \leq K \leq N \leq 10
- N and K are integers.
- S is a string of length N consisting only of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N K S
Output
Print the number of strings obtained by permuting S that do not contain a palindrome of length K as a substring.
Sample Input 1
3 2 aab
Sample Output 1
1
The strings obtained by permuting aab are aab, aba, and baa. Among these, aab and baa contain the palindrome aa of length 2 as a substring.
Thus, the only string that satisfies the condition is aba, so print 1.
Sample Input 2
5 3 zzyyx
Sample Output 2
16
There are 30 strings obtained by permuting zzyyx, 16 of which do not contain a palindrome of length 3. Thus, print 16.
Sample Input 3
10 5 abcwxyzyxw
Sample Output 3
440640
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
十進法ですべての桁の数字が 1 である整数をレピュニットと呼びます。レピュニットを小さい順に並べると 1,11,111,\ldots です。
ちょうど 3 つのレピュニットの和として表せる整数のうち N 番目に小さいものを求めてください。
制約
- N は 1 以上 333 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
5
出力例 1
113
ちょうど 3 つのレピュニットの和として表せる整数を小さい順に並べると 3,13,23,33,113,\ldots です。例えば 113 は 113=1+1+111 と表せます。
3 つのレピュニットは相異ならなくてもよいことに注意してください。
入力例 2
19
出力例 2
2333
入力例 3
333
出力例 3
112222222233
Score : 300 points
Problem Statement
A repunit is an integer whose digits are all 1 in decimal representation. The repunits in ascending order are 1, 11, 111, \ldots.
Find the N-th smallest integer that can be expressed as the sum of exactly three repunits.
Constraints
- N is an integer between 1 and 333, inclusive.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
5
Sample Output 1
113
The integers that can be expressed as the sum of exactly three repunits are 3, 13, 23, 33, 113, \ldots in ascending order. For example, 113 can be expressed as 113 = 1 + 1 + 111.
Note that the three repunits do not have to be distinct.
Sample Input 2
19
Sample Output 2
2333
Sample Input 3
333
Sample Output 3
112222222233
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
2N 個のボールがあります。各ボールには 1 以上 N 以下の整数によって表される色が塗られており、各色で塗られたボールはちょうど 2 個ずつ存在します。
これらのボールが、底が地面と平行になるように置かれた M 本の筒に入れられています。はじめ、i \ (1 \leq i \leq M) 本目の筒には k_i 個のボールが入っており、上から j \ (1 \leq j \leq k_i) 番目のボールの色は a_{i, j} です。
あなたの目標は、以下の操作を繰り返すことで M 本の筒全てを空にすることです。
- 異なる 2 本の空でない筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。ここで、取り出して捨てた 2 つのボールは同じ色で塗られている必要がある。
目標が達成可能かを判定してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 2 \times 10^5
- 1 \leq k_i\ (1 \leq i \leq M)
- 1 \leq a_{i,j} \leq N\ (1 \leq i \leq M,1 \leq j \leq k_i)
- \sum_{i=1}^{M} k_i = 2N
- 全ての x\ (1 \leq x \leq N) について、1 \leq i \leq M かつ 1 \leq j \leq k_i かつ a_{i,j}=x なる整数の組 (i,j) はちょうど 2 つ存在する
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
k_1
a_{1,1} a_{1,2} \ldots a_{1,k_1}
k_2
a_{2,1} a_{2,2} \ldots a_{2,k_2}
\hspace{2.1cm}\vdots
k_M
a_{M,1} a_{M,2} \ldots a_{M,k_M}
出力
目標が達成可能なら Yes を、達成不可能なら No を出力せよ。
入力例 1
2 2 2 1 2 2 1 2
出力例 1
Yes
以下のように操作を行えばよいです。
- 1 つ目の筒と 2 つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に 1 であり等しいので、この操作は有効である。
- 1 つ目の筒と 2 つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に 2 であり等しいので、この操作は有効である。
入力例 2
2 2 2 1 2 2 2 1
出力例 2
No
そもそも一度も操作を行うことができないため、目標を達成する、すなわち M 本の筒全てを空にすることは不可能です。
Score : 400 points
Problem Statement
We have 2N balls. Each ball has a color represented by an integer between 1 and N (inclusive). For each of the N colors, there are exactly two balls of that color.
These balls are contained in M cylinders placed perpendicularly to the floor. Initially, the i-th cylinder (1 \leq i \leq M) contains k_i balls, the j-th of which from the top (1 \leq j \leq k_i) has the color a_{i, j}.
Your objective is to empty all M cylinders by repeating the following operation.
- Choose two different non-empty cylinders and remove the topmost ball from each of them. Here, the two balls removed must be of the same color.
Determine whether the objective is achievable.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 2 \times 10^5
- 1 \leq k_i\ (1 \leq i \leq M)
- 1 \leq a_{i,j} \leq N\ (1 \leq i \leq M,1 \leq j \leq k_i)
- \sum_{i=1}^{M} k_i = 2N
- For every x\ (1 \leq x \leq N), there exists exactly two pairs of integers (i,j) such that 1 \leq i \leq M, 1 \leq j \leq k_i, and a_{i,j}=x.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
k_1
a_{1,1} a_{1,2} \ldots a_{1,k_1}
k_2
a_{2,1} a_{2,2} \ldots a_{2,k_2}
\hspace{2.1cm}\vdots
k_M
a_{M,1} a_{M,2} \ldots a_{M,k_M}
Output
If the objective is achievable, print Yes; otherwise, print No.
Sample Input 1
2 2 2 1 2 2 1 2
Sample Output 1
Yes
The objective can be achieved as follows.
- Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 1.
- Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 2.
Sample Input 2
2 2 2 1 2 2 2 1
Sample Output 2
No
No operation can be done at all, which means it is impossible to achieve the objective of emptying the M cylinders.