Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
十進法表記でちょうど 4 桁の整数 N が与えられます．
N の十進法表記には何個の 2 が現れるかを求めてください．
制約
- 1000 \leq N \leq 9999
入力
入力は以下の形式で標準入力から与えられる．
N
出力
答えを出力せよ．
入力例 1
1222
出力例 1
3
このコンテストは日本時間で 12 月 22 日に開催されますが，1222 には 2 が 3 個現れます．
入力例 2
3456
出力例 2
0
入力例 3
9592
出力例 3
1
Score : 100 points
Problem Statement
You are given an integer N that has exactly four digits in base ten.
How many times does 2 occur in the base-ten representation of N?
Constraints
- 1000 \leq N \leq 9999
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
1222
Sample Output 1
3
2 occurs three times in 1222. By the way, this contest is held on December 22 (JST).
Sample Input 2
3456
Sample Output 2
0
Sample Input 3
9592
Sample Output 3
1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
AtCoder 合金と呼ばれる特殊な金属でできた，長方形の板状の素材が N 枚あります． i 番目の素材の縦の長さは A_i，横の長さは B_i です．
高橋君は，AtCoder 合金でできた，縦の長さがちょうど H，横の長さがちょうど W の長方形の板が欲しいです． そのため，N 枚の素材のうち 1 枚を選び，それを必要に応じて切断して，求める長方形の板を得ようとしています． 素材を切断する際には，長方形の辺に平行な線でしか切断することができません． また，素材には向きが定まっているので，回転させることはできません． そのため，例えば縦 5，横 3 の素材を，縦 3，横 5 の板として使うことはできません．
適切に切断することで，長さが縦 H，横 W の板が得られるような素材は N 枚中何枚あるでしょうか？
制約
- 1 \leq N \leq 1000
- 1 \leq H \leq 10^9
- 1 \leq W \leq 10^9
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N H W A_1 B_1 A_2 B_2 : A_N B_N
出力
答えを出力せよ．
入力例 1
3 5 2 10 3 5 2 2 5
出力例 1
2
高橋君は，縦 5，横 2 の大きさの板が欲しいです．
- 1 番目の素材は，縦 10，横 3 の大きさで，適切に切断すると縦 5，横 2 の大きさの板が得られます．
- 2 番目の素材は，縦 5，横 2 の大きさで，切断せずに縦 5，横 2 の大きさの板が得られます．
- 3 番目の素材は，縦 2，横 5 の大きさで，どのように切断しても 縦 5，横 2 の大きさの板は得られません．素材を回転させて縦 5，横 2 の大きさの板として使うことはできないことに注意してください．
入力例 2
10 587586158 185430194 894597290 708587790 680395892 306946994 590262034 785368612 922328576 106880540 847058850 326169610 936315062 193149191 702035777 223363392 11672949 146832978 779291680 334178158 615808191 701464268
出力例 2
8
Score : 200 points
Problem Statement
There are N rectangular plate materials made of special metal called AtCoder Alloy. The dimensions of the i-th material are A_i \times B_i (A_i vertically and B_i horizontally).
Takahashi wants a rectangular plate made of AtCoder Alloy whose dimensions are exactly H \times W. He is trying to obtain such a plate by choosing one of the N materials and cutting it if necessary. When cutting a material, the cuts must be parallel to one of the sides of the material. Also, the materials have fixed directions and cannot be rotated. For example, a 5 \times 3 material cannot be used as a 3 \times 5 plate.
Out of the N materials, how many can produce an H \times W plate if properly cut?
Constraints
- 1 \leq N \leq 1000
- 1 \leq H \leq 10^9
- 1 \leq W \leq 10^9
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N H W A_1 B_1 A_2 B_2 : A_N B_N
Output
Print the answer.
Sample Input 1
3 5 2 10 3 5 2 2 5
Sample Output 1
2
Takahashi wants a 5 \times 2 plate.
- The dimensions of the first material are 10 \times 3. We can obtain a 5 \times 2 plate by properly cutting it.
- The dimensions of the second material are 5 \times 2. We can obtain a 5 \times 2 plate without cutting it.
- The dimensions of the third material are 2 \times 5. We cannot obtain a 5 \times 2 plate, whatever cuts are made. Note that the material cannot be rotated and used as a 5 \times 2 plate.
Sample Input 2
10 587586158 185430194 894597290 708587790 680395892 306946994 590262034 785368612 922328576 106880540 847058850 326169610 936315062 193149191 702035777 223363392 11672949 146832978 779291680 334178158 615808191 701464268
Sample Output 2
8
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 個の 1 以上の整数 a_1, a_2, ..., a_N があります． a_1, a_2, ..., a_N の値はわかりませんが，a_1 \times a_2 \times ... \times a_N = P がわかっています．
a_1, a_2, ..., a_N の最大公約数として考えられるもののうち，最も大きいものを求めてください．
制約
- 1 \leq N \leq 10^{12}
- 1 \leq P \leq 10^{12}
入力
入力は以下の形式で標準入力から与えられる．
N P
出力
答えを出力せよ．
入力例 1
3 24
出力例 1
2
例えば a_1=2, a_2=6, a_3=2 の場合，最大公約数は 2 となります．
入力例 2
5 1
出力例 2
1
a_i は正の整数なので，a_1 = a_2 = a_3 = a_4 = a_5 = 1 以外にはありえません．
入力例 3
1 111
出力例 3
111
入力例 4
4 972439611840
出力例 4
206
Score : 300 points
Problem Statement
There are N integers a_1, a_2, ..., a_N not less than 1. The values of a_1, a_2, ..., a_N are not known, but it is known that a_1 \times a_2 \times ... \times a_N = P.
Find the maximum possible greatest common divisor of a_1, a_2, ..., a_N.
Constraints
- 1 \leq N \leq 10^{12}
- 1 \leq P \leq 10^{12}
Input
Input is given from Standard Input in the following format:
N P
Output
Print the answer.
Sample Input 1
3 24
Sample Output 1
2
The greatest common divisor would be 2 when, for example, a_1=2, a_2=6 and a_3=2.
Sample Input 2
5 1
Sample Output 2
1
As a_i are positive integers, the only possible case is a_1 = a_2 = a_3 = a_4 = a_5 = 1.
Sample Input 3
1 111
Sample Output 3
111
Sample Input 4
4 972439611840
Sample Output 4
206
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
一本のりんごの木があり、N 色のりんごが実っています。これらのりんごの N 種類の色には 1 から N までの番号が振られており、i 番の色のりんごは a_i 個あります。
あなたとダックスフンドのルンルンは、以下の行動を交互に行います (あなたから始めます)。
- 木から 1 個以上のりんごを選んで食べる。ただし、一度に選ぶりんごは全て異なる色でなければならない。
木から最後のりんごを食べた者を勝者とします。あなたとルンルンがともに最善を尽くすとき、どちらが勝つでしょうか？
制約
- 1 ≤ N ≤ 10^5
- 1 ≤ a_i ≤ 10^9
- 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 : a_N
出力
あなたが勝つなら first、ルンルンが勝つなら second と出力せよ。
入力例 1
2 1 2
出力例 1
first
1 番の色を赤、2 番の色を青とします。この例では、木には赤いりんご 1 個と青いりんご 2 個が実っています。
あなたは最初の手番で赤いりんごを食べるべきです。すると、ルンルンは青いりんごのうち片方を食べるほかなく、次の手番であなたがもう片方を食べて勝つことができます。
なお、あなたは最初の手番で両方の色のりんごを 1 個ずつ食べることもできます (勝ちには繋がりませんが)。
入力例 2
3 100000 30000 20000
出力例 2
second
Score : 500 points
Problem Statement
There is an apple tree that bears apples of N colors. The N colors of these apples are numbered 1 to N, and there are a_i apples of Color i.
You and Lunlun the dachshund alternately perform the following operation (starting from you):
- Choose one or more apples from the tree and eat them. Here, the apples chosen at the same time must all have different colors.
The one who eats the last apple from the tree will be declared winner. If both you and Lunlun play optimally, which will win?
Constraints
- 1 \leq N \leq 10^5
- 1 \leq a_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 a_2 : a_N
Output
If you will win, print first; if Lunlun will win, print second.
Sample Input 1
2 1 2
Sample Output 1
first
Let Color 1 be red, and Color 2 be blue. In this case, the tree bears one red apple and two blue apples.
You should eat the red apple in your first turn. Lunlun is then forced to eat one of the blue apples, and you can win by eating the other in your next turn.
Note that you are also allowed to eat two apples in your first turn, one red and one blue (not a winning move, though).
Sample Input 2
3 100000 30000 20000
Sample Output 2
second