実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
非負整数 x に対し定義される関数 f(x) は以下の条件を満たします。
- f(0) = 1
- 任意の正整数 k に対し f(k) = k \times f(k-1)
このとき、 f(N) を求めてください。
制約
- N は 0 \le N \le 10 を満たす整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
2
出力例 1
2
f(2) = 2 \times f(1) = 2 \times 1 \times f(0) = 2 \times 1 \times 1 = 2 です。
入力例 2
3
出力例 2
6
f(3) = 3 \times f(2) = 3 \times 2 = 6 です。
入力例 3
0
出力例 3
1
入力例 4
10
出力例 4
3628800
Score : 100 points
Problem Statement
A function f(x) defined for non-negative integer x satisfies the following conditions:
- f(0) = 1;
- f(k) = k \times f(k-1) for all positive integers k.
Find f(N).
Constraints
- N is an integer such that 0 \le N \le 10.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
2
Sample Output 1
2
We have f(2) = 2 \times f(1) = 2 \times 1 \times f(0) = 2 \times 1 \times 1 = 2.
Sample Input 2
3
Sample Output 2
6
We have f(3) = 3 \times f(2) = 3 \times 2 = 6.
Sample Input 3
0
Sample Output 3
1
Sample Input 4
10
Sample Output 4
3628800
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
ナオヒロ君はモンスターを飼っています。モンスターの現在の体力は H です。
また、ナオヒロ君は N 種類の傷薬を持っています。傷薬は効き目の弱い順に 1 から N までの番号がついています。
傷薬 n をモンスターに与えると、モンスターの体力が P_n 増加します。ここで、P_1 \lt P_2 \lt \dots \lt P_N が成り立ちます。
ナオヒロ君は傷薬を 1 つモンスターに与えることで、モンスターの体力を X 以上にしたいです。
目標を達成できる傷薬のうち最も効き目の弱いものの番号を出力してください。(制約下においてそのような傷薬が存在することが保証されています。)
制約
- 2 \leq N \leq 100
- 1 \leq H \lt X \leq 999
- 1 \leq P_1 \lt P_2 \lt \dots \lt P_N = 999
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N H X P_1 P_2 \dots P_N
出力
目標を達成できる傷薬のうち最も効き目の弱いものの番号を出力せよ。
入力例 1
3 100 200 50 200 999
出力例 1
2
それぞれの傷薬をモンスターに 1 つ与えたときのモンスターの体力の変化は以下の通りです。
- 傷薬 1 をモンスターに与えるとモンスターの体力は 100 + 50 = 150 になります。
- 傷薬 2 をモンスターに与えるとモンスターの体力は 100 + 200 = 300 になります。
- 傷薬 3 をモンスターに与えるとモンスターの体力は 100 + 999 = 1099 になります。
与えた後に体力が X = 200 以上になっている傷薬は、傷薬 2 と傷薬 3 です。このうち最も効き目の弱い傷薬である傷薬 2 が答えになります。
入力例 2
2 10 21 10 999
出力例 2
2
入力例 3
10 500 999 38 420 490 585 613 614 760 926 945 999
出力例 3
4
Score : 100 points
Problem Statement
Naohiro has a monster. The monster's current health is H.
He also has N kinds of potions, numbered from 1 to N in ascending order of effectiveness.
If you give the monster potion n, its health will increase by P_n. Here, P_1 \lt P_2 \lt \dots \lt P_N.
He wants to increase the monster's health to X or above by giving it one of the potions.
Print the number of the least effective potion that can achieve the purpose. (The constraints guarantee that such a potion exists.)
Constraints
- 2 \leq N \leq 100
- 1 \leq H \lt X \leq 999
- 1 \leq P_1 \lt P_2 \lt \dots \lt P_N = 999
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H X P_1 P_2 \dots P_N
Output
Print the number of the least effective potion that can achieve the purpose.
Sample Input 1
3 100 200 50 200 999
Sample Output 1
2
Below is the change in the monster's health when one of the potions is given to the monster.
- If potion 1 is given, the monster's health becomes 100 + 50 = 150.
- If potion 2 is given, the monster's health becomes 100 + 200 = 300.
- If potion 3 is given, the monster's health becomes 100 + 999 = 1099.
The potions that increase the monster's health to at least X = 200 are potions 2 and 3. The answer is the least effective of them, which is potion 2.
Sample Input 2
2 10 21 10 999
Sample Output 2
2
Sample Input 3
10 500 999 38 420 490 585 613 614 760 926 945 999
Sample Output 3
4
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
人 1 、人 2 、\ldots 、人 N と番号をつけられた N 人の人がいます。
N 人は、人 1 、人 2 、\ldots 、人 N の順番に下記の行動をちょうど 1 回ずつ行います。
- 人 i 自身がまだ一度も番号を呼ばれていないなら、人 A_i の番号を呼ぶ。
最後まで番号を一度も呼ばれない人全員の番号を昇順に列挙してください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- A_i \neq i
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
下記の形式にしたがって、最後まで番号を一度も呼ばれない人全員の番号を昇順に列挙せよ。
K X_1 X_2 \ldots X_K
すなわち、まず 1 行目に、最後まで番号を一度も呼ばれない人の人数 K を出力し、 2 行目に、最後まで番号を一度も呼ばれない人全員の番号を昇順に並べた列 (X_1, X_2, \ldots, X_K) を空白区切りで出力せよ。
入力例 1
5 3 1 4 5 4
出力例 1
2 2 4
5 人の行動は下記の通りです。
- 人 1 はまだ番号を一度も呼ばれていないので、人 1 は人 3 の番号を呼びます。
- 人 2 はまだ番号を一度も呼ばれていないので、人 2 は人 1 の番号を呼びます。
- 人 3 はすでに人 1 によって番号を呼ばれているので、何もしません。
- 人 4 はまだ番号を一度も呼ばれていないので、人 4 は人 5 の番号を呼びます。
- 人 5 はすでに人 4 によって番号を呼ばれているので、何もしません。
よって、最後まで番号を一度も呼ばれないのは人 2 と人 4 です。
入力例 2
20 9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12
出力例 2
10 1 2 5 6 8 11 14 17 18 20
Score : 200 points
Problem Statement
There are N people whose IDs are 1, 2, \ldots, and N.
Each of person 1, person 2, \ldots, and person N performs the following action once in this order:
- If person i's ID has not been called out yet, call out person A_i's ID.
Enumerate the IDs of all the people whose IDs are never called out until the end in ascending order.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- A_i \neq i
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Enumerate the IDs of all the people whose IDs are not called out until the end in ascending order in the following format:
K X_1 X_2 \ldots X_K
In other words, the first line should contain the number of people, K, whose IDs are never called out until the end; the second line should contain the sequence (X_1, X_2, \ldots, X_K) of IDs of such people in ascending order, with spaces in between.
Sample Input 1
5 3 1 4 5 4
Sample Output 1
2 2 4
The five people's actions are as follows.
- Person 1's ID has not been called out yet, so person 1 calls out person 3's ID.
- Person 2's ID has not been called out yet, so person 2 calls out person 1's ID.
- Person 3's ID has already been called out by person 1, so nothing happens.
- Person 4's ID has not been called out yet, so person 4 calls out person 5's ID.
- Person 5's ID has already been called out by person 4, so nothing happens.
Therefore, person 2 and 4's IDs are not called out until the end.
Sample Input 2
20 9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12
Sample Output 2
10 1 2 5 6 8 11 14 17 18 20
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
英大文字および数字からなる 2 文字の文字列が N 個与えられます。i 個目の文字列は S_i です。
以下の 3 つの条件をすべて満たすか判定してください。
・すべての文字列に対して、1 文字目は H , D , C , S のどれかである。
・すべての文字列に対して、2 文字目は A , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , T , J , Q , K のどれかである。
・すべての文字列は相異なる。つまり、i \neq j ならば S_i \neq S_j である。
制約
- 1 \leq N \leq 52
- S_i は英大文字および数字からなる 2 文字の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
3 つの条件をすべて満たす場合は Yes、そうでない場合は No を出力せよ。
入力例 1
4 H3 DA D3 SK
出力例 1
Yes
このとき 3 つの条件をすべて満たすことが確認できます。
入力例 2
5 H3 DA CK H3 S7
出力例 2
No
S_1 と S_4 がともに H3 となってしまっているため、3 番目の条件に反します。
入力例 3
4 3H AD 3D KS
出力例 3
No
入力例 4
5 00 AA XX YY ZZ
出力例 4
No
Score : 200 points
Problem Statement
You are given N strings, each of length 2, consisting of uppercase English letters and digits. The i-th string is S_i.
Determine whether the following three conditions are all satisfied.
・For every string, the first character is one of H, D, C, and S.
・For every string, the second character is one of A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K.
・All strings are pairwise different. That is, if i \neq j, then S_i \neq S_j.
Constraints
- 1 \leq N \leq 52
- S_i is a string of length 2 consisting of uppercase English letters and digits.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
If the three conditions are all satisfied, print Yes; otherwise, print No.
Sample Input 1
4 H3 DA D3 SK
Sample Output 1
Yes
One can verify that the three conditions are all satisfied.
Sample Input 2
5 H3 DA CK H3 S7
Sample Output 2
No
Both S_1 and S_4 are H3, violating the third condition.
Sample Input 3
4 3H AD 3D KS
Sample Output 3
No
Sample Input 4
5 00 AA XX YY ZZ
Sample Output 4
No
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は、レジ打ちの仕事をしています。
レジの機械には 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 の 11 個のボタンがあります。
レジの機械には、はじめ 0 が表示されています。
ボタン 00 を押すと、表示されている数が 100 倍されます。
それ以外のボタンを押すと、表示されている数が 10 倍されたあとに、押されたボタンに書かれている数が加算されます。
高橋君は、レジに整数 S を表示させたいです。 レジに S が表示されている状態にするためには、少なくとも何回ボタンを押す必要があるか求めてください。
制約
- 1\leq S\leq 10^{100000}
- S は整数
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを 1 行で出力せよ。
入力例 1
40004
出力例 1
4
例えば、次のように操作することでボタンを 4 回押して 40004 を表示させることができます。 はじめ、レジには 0 が表示されています。
- ボタン
4を押す。レジに表示されている数は 4 となる。 - ボタン
00を押す。レジに表示されている数は 400 となる。 - ボタン
0を押す。レジに表示されている数は 4000 となる。 - ボタン
4を押す。レジに表示されている数は 40004 となる。
3 回までボタンを押すことでレジに 40004 を表示させることはできないので、出力すべき値は 4 です。
入力例 2
1355506027
出力例 2
10
入力例 3
10888869450418352160768000001
出力例 3
27
S は 64\operatorname{bit} 整数に収まらない場合があることに注意してください。
Score : 300 points
Problem Statement
Takahashi is a cashier.
There is a cash register with 11 keys: 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.
The cash register initially displays 0.
Whenever he types the key 00, the displayed number is multiplied by 100;
whenever he types one of the others, the displayed number is multiplied by 10, and then added by the number written on the key.
Takahashi wants the cash register to display an integer S. At least how many keystrokes are required to make it display S?
Constraints
- 1\leq S\leq 10^{100000}
- S is an integer.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer in a line.
Sample Input 1
40004
Sample Output 1
4
For example, the following four keystrokes make the cash register display 40004. Initially, the cash register displays 0.
- Type the key
4. It now displays 4. - Type the key
00. It now displays 400. - Type the key
0. It now displays 4000. - Type the key
4. It now displays 40004.
He cannot make it display 40004 with three or fewer keystrokes, so 4 should be printed.
Sample Input 2
1355506027
Sample Output 2
10
Sample Input 3
10888869450418352160768000001
Sample Output 3
27
Note that S may not fit into a 64-\operatorname{bit} integer type.