実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
文字列 S が与えられるので、この文字列が Hello,World! と完全に一致するなら AC 、そうでないなら WA と出力してください。
「完全に一致する」とは？
文字列 A と B が完全に一致するとは、文字列 A と B の長さが等しく、かつ全ての 1 \le i \le |A| を満たす整数 i について A の先頭から i 文字目と B の先頭から i 文字目とが(英大文字か小文字かも含めて)一致することを指します。制約
- 1 \le |S| \le 15
- S は英大小文字,
,,!のみからなる
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
Hello,World!
出力例 1
AC
文字列 S は Hello,World! と完全に一致します。
入力例 2
Hello,world!
出力例 2
WA
先頭から 7 文字目の W が、 Hello,World! では大文字ですが S では小文字です。よって S は Hello,World! と一致しません。
入力例 3
Hello!World!
出力例 3
WA
Score : 100 points
Problem Statement
Given a string S, print AC if it perfectly matches Hello,World!; otherwise, print WA.
What is a perfect match?
Strings A is said to perfectly match B when the length of A is equal to that of B, and the i-th character of A is the same as the i-th character of B for every integer i such that 1 \le i \le |A|.Constraints
- 1 \le |S| \le 15
- S consists of English lowercase letters, English uppercase letters,
,, and!.
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
Hello,World!
Sample Output 1
AC
The string S perfectly matches Hello,World!.
Sample Input 2
Hello,world!
Sample Output 2
WA
The seventh character from the beginning should be an uppercase W in Hello,World!, but S has a lowercase w in that position. Thus, S does not match Hello,World!.
Sample Input 3
Hello!World!
Sample Output 3
WA
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
高橋くんはゲームで遊んでいます。 このゲームにはワールドが 8 つあり、それぞれのワールドにはステージが 8 つずつあります。 ステージには順番があり、最初のステージは 1 個めのワールドにある 1 個めのステージです。 i 個め (1\le i\le 8) のワールドにある j 個め (1\le j\le 8) のステージの次のステージは、以下のようになっています。
- j\lt8 のとき、次のステージは i 個めのワールドにある j+1 個めのステージです。
- i\lt8,j=8 のとき、次のステージは i+1 個めのワールドにある 1 個めのステージです。
- i=8,j=8 のとき、次のステージはありません。このステージが最後のステージです。
i 個め (1\le i\le 8) のワールドにある j 個め (1\le j\le 8) のステージの名前は i-j です。
たとえば、最初のステージ名は 1-1 で、最後のステージ名は 8-8 です。
高橋くんが現在遊んでいるステージのステージ名 S が与えられるので、次のステージのステージ名を出力してください。
制約
- S はいずれかのステージのステージ名である。
- S は
8-8ではない。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
次のステージのステージ名を出力せよ。
入力例 1
4-2
出力例 1
4-3
4 個めのワールドの 2 個めのステージの次のステージは、同じワールドの 3 個めのステージです。
入力例 2
1-8
出力例 2
2-1
1-8 は 1 個めのワールドの最後のステージなので、次のステージは 2 個めのワールドの 1 個めのステージです。
入力例 3
3-3
出力例 3
3-4
Score : 100 points
Problem Statement
Takahashi is playing a game. This game has eight worlds, and each world has eight stages. The stages have an order, and the first stage is the 1st stage in the 1st world. The next stage after the j-th stage (1\le j\le 8) in the i-th world (1\le i\le 8) is as follows:
- When j\lt8, the next stage is the (j+1)-th stage in the i-th world.
- When i\lt8,j=8, the next stage is the 1st stage in the (i+1)-th world.
- When i=8,j=8, there is no next stage. This stage is the last stage.
The name of the j-th stage (1\le j\le 8) in the i-th world (1\le i\le 8) is i-j.
For example, the name of the first stage is 1-1, and the name of the last stage is 8-8.
Given the stage name S of the stage Takahashi is currently playing, output the stage name of the next stage.
Constraints
- S is the stage name of one of the stages.
- S is not
8-8.
Input
The input is given from Standard Input in the following format:
S
Output
Output the stage name of the next stage.
Sample Input 1
4-2
Sample Output 1
4-3
The next stage after the 2nd stage in the 4th world is the 3rd stage in the same world.
Sample Input 2
1-8
Sample Output 2
2-1
1-8 is the last stage in the 1st world, so the next stage is the 1st stage in the 2nd world.
Sample Input 3
3-3
Sample Output 3
3-4
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
おもり 1, おもり 2, \dots, おもり N の N 個のおもりがあります。おもり i の重さは A_i です。
以下の条件を満たす正整数 n を 良い整数 と呼びます。
- \bf{3} 個以下 の異なるおもりを自由に選んで、選んだおもりの重さの和を n にすることができる。
W 以下の正整数のうち、良い整数は何個ありますか？
制約
- 1 \leq N \leq 300
- 1 \leq W \leq 10^6
- 1 \leq A_i \leq 10^6
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N W A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
2 10 1 3
出力例 1
3
おもり 1 のみを選ぶと重さの和は 1 になります。よって 1 は良い整数です。
おもり 2 のみを選ぶと重さの和は 3 になります。よって 3 は良い整数です。
おもり 1 とおもり 2 を選ぶと重さの和は 4 になります。よって 4 は良い整数です。
これら以外に良い整数は存在しません。また、1,3,4 のいずれも W 以下の整数です。よって答えは 3 個になります。
入力例 2
2 1 2 3
出力例 2
0
W 以下の良い整数は存在しません。
入力例 3
4 12 3 3 3 3
出力例 3
3
良い整数は 3,6,9 の 3 個です。
たとえばおもり 1, おもり 2, おもり 3 を選ぶと重さの和は 9 になるので、9 は良い整数です。
12 は良い整数 ではない ことに注意してください。
入力例 4
7 251 202 20 5 1 4 2 100
出力例 4
48
Score : 200 points
Problem Statement
There are N weights called Weight 1, Weight 2, \dots, Weight N. Weight i has a mass of A_i.
Let us say a positive integer n is a good integer if the following condition is satisfied:
- We can choose at most 3 different weights so that they have a total mass of n.
How many positive integers less than or equal to W are good integers?
Constraints
- 1 \leq N \leq 300
- 1 \leq W \leq 10^6
- 1 \leq A_i \leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N W A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
2 10 1 3
Sample Output 1
3
If we choose only Weight 1, it has a total mass of 1, so 1 is a good integer.
If we choose only Weight 2, it has a total mass of 3, so 3 is a good integer.
If we choose Weights 1 and 2, they have a total mass of 4, so 4 is a good integer.
No other integer is a good integer. Also, all of 1, 3, and 4 are integers less than or equal to W. Therefore, the answer is 3.
Sample Input 2
2 1 2 3
Sample Output 2
0
There are no good integers less than or equal to W.
Sample Input 3
4 12 3 3 3 3
Sample Output 3
3
There are 3 good integers: 3, 6, and 9.
For example, if we choose Weights 1, 2, and 3, they have a total mass of 9, so 9 is a good integer.
Note that 12 is not a good integer.
Sample Input 4
7 251 202 20 5 1 4 2 100
Sample Output 4
48
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君の家には N 本の麺からなるパスタがあり、i 本目の麺の長さは A_i です。
高橋君はこれから M 日間の食事計画を立てており、
i 日目にはパスタの麺のうち長さがちょうど B_i であるようなものを 1 本選び、食べようと考えています。
もし、1 日目から M 日目の間に 1 日でもそのような麺が無い日があれば、食事計画は失敗となります。
また、同じ麺を複数の日に食べることはできません。
高橋君が食事計画を最後まで実行することは可能ですか？
制約
- 1 \leq M \leq N \leq 1000
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
出力
高橋君が食事計画を最後まで実行できる場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
3 2 1 1 3 3 1
出力例 1
Yes
1 日目に 3 本目の麺を、2 日目に 1 本目の麺を食べれば良いので、高橋君の食事計画は実行可能です。
入力例 2
1 1 1000000000 1
出力例 2
No
長さがちょうど 1 の麺が存在する必要があります。
入力例 3
5 2 1 2 3 4 5 5 5
出力例 3
No
長さが 5 の麺は 1 本しか存在しないため、2 日目に食事をとる事が出来ません。
Score : 200 points
Problem Statement
There is pasta consisting of N noodles at Takahashi's home. The length of the i-th noodle is A_i.
Takahashi has a meal plan for the next M days.
On the i-th day, he is going to choose a pasta noodle of length exactly B_i and eat it.
If no such noodle is available on any day, his plan fails.
Additionally, he cannot eat the same noodle on multiple days.
Can Takahashi accomplish his meal plan?
Constraints
- 1 \leq M \leq N \leq 1000
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
Output
If Takahashi can accomplish his meal plan, print Yes; otherwise, print No.
Sample Input 1
3 2 1 1 3 3 1
Sample Output 1
Yes
He can eat the 3-rd noodle on the 1-st day and the 1-st noodle on the 2-nd day, so his meal plan is feasible.
Sample Input 2
1 1 1000000000 1
Sample Output 2
No
A noodle of length exactly 1 is needed.
Sample Input 3
5 2 1 2 3 4 5 5 5
Sample Output 3
No
Since there are only 1 noodle of length 5, he cannot have a meal on the 2-nd day.
実行時間制限: 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.