実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 100 点
問題文
いろはちゃんは、人気の日本製ゲーム「ÅtCoder」で遊びたい猫のすぬけ君のために日本語を教えることにしました。
日本語で鉛筆を数えるときには、助数詞として数の後ろに「本」がつきます。この助数詞はどんな数につくかで異なる読み方をします。具体的には、999 以下の正の整数 N について、「N 本」と言うときの「本」の読みは
- N の 1 の位が 2, 4, 5, 7, 9 のとき
hon
- N の 1 の位が 0, 1, 6, 8 のとき
pon
- N の 1 の位が 3 のとき
bon
です。
N が与えられるので、「N 本」と言うときの「本」の読みを出力してください。
制約
- N は 999 以下の正の整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
16
出力例 1
pon
16 の 1 の位は 6 なので、「本」の読みは pon
です。
入力例 2
2
出力例 2
hon
入力例 3
183
出力例 3
bon
Score: 100 points
Problem Statement
The cat Snuke wants to play a popular Japanese game called ÅtCoder, so Iroha has decided to teach him Japanese.
When counting pencils in Japanese, the counter word "本" follows the number. The pronunciation of this word varies depending on the number. Specifically, the pronunciation of "本" in the phrase "N 本" for a positive integer N not exceeding 999 is as follows:
hon
when the digit in the one's place of N is 2, 4, 5, 7, or 9;pon
when the digit in the one's place of N is 0, 1, 6 or 8;bon
when the digit in the one's place of N is 3.
Given N, print the pronunciation of "本" in the phrase "N 本".
Constraints
- N is a positive integer not exceeding 999.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
16
Sample Output 1
pon
The digit in the one's place of 16 is 6, so the "本" in "16 本" is pronounced pon
.
Sample Input 2
2
Sample Output 2
hon
Sample Input 3
183
Sample Output 3
bon
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 200 点
問題文
英小文字からなる文字列 S があります。
S の長さが K 以下であれば、S をそのまま出力してください。
S の長さが K を上回っているならば、先頭 K 文字だけを切り出し、末尾に ...
を付加して出力してください。
制約
- K は 1 以上 100 以下の整数
- S は英小文字からなる文字列
- S の長さは 1 以上 100 以下
入力
入力は以下の形式で標準入力から与えられる。
K S
出力
問題文の通りに出力せよ。
入力例 1
7 nikoandsolstice
出力例 1
nikoand...
nikoandsolstice
の長さは 15 であり、K=7 を上回っています。
この先頭 7 文字を切り出して末尾に ...
を付加した文字列 nikoand...
を出力します。
入力例 2
40 ferelibenterhominesidquodvoluntcredunt
出力例 2
ferelibenterhominesidquodvoluntcredunt
ガイウス・ユリウス・カエサルの名言です。
Score: 200 points
Problem Statement
We have a string S consisting of lowercase English letters.
If the length of S is at most K, print S without change.
If the length of S exceeds K, extract the first K characters in S, append ...
to the end of them, and print the result.
Constraints
- K is an integer between 1 and 100 (inclusive).
- S is a string consisting of lowercase English letters.
- The length of S is between 1 and 100 (inclusive).
Input
Input is given from Standard Input in the following format:
K S
Output
Print a string as stated in Problem Statement.
Sample Input 1
7 nikoandsolstice
Sample Output 1
nikoand...
nikoandsolstice
has a length of 15, which exceeds K=7.
We should extract the first 7 characters in this string, append ...
to the end of them, and print the result nikoand...
.
Sample Input 2
40 ferelibenterhominesidquodvoluntcredunt
Sample Output 2
ferelibenterhominesidquodvoluntcredunt
The famous quote from Gaius Julius Caesar.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 300 点
問題文
時針と分針の長さがそれぞれ A センチメートル、B センチメートルであるアナログ時計を考えます。
時針と分針それぞれの片方の端点は同じ定点に固定されており、この点を中心としてそれぞれの針は一定の角速度で時計回りに回転します。時針は 12 時間で、分針は 1 時間で 1 周します。
0 時ちょうどに時針と分針は重なっていました。ちょうど H 時 M 分になったとき、2 本の針の固定されていない方の端点は何センチメートル離れているでしょうか。
制約
- 入力はすべて整数
- 1 \leq A, B \leq 1000
- 0 \leq H \leq 11
- 0 \leq M \leq 59
入力
入力は以下の形式で標準入力から与えられる。
A B H M
出力
答えを、単位を除いて出力せよ。正しい値との絶対誤差または相対誤差が 10^{-9} 以下であれば正解とみなされる。
入力例 1
3 4 9 0
出力例 1
5.00000000000000000000
2 本の針は図のようになるので、答えは 5 センチメートルです。
入力例 2
3 4 10 40
出力例 2
4.56425719433005567605
2 本の針は図のようになります。各針は常に一定の角速度で回ることに注意してください。
Score: 300 points
Problem Statement
Consider an analog clock whose hour and minute hands are A and B centimeters long, respectively.
An endpoint of the hour hand and an endpoint of the minute hand are fixed at the same point, around which each hand rotates clockwise at constant angular velocity. It takes the hour and minute hands 12 hours and 1 hour to make one full rotation, respectively.
At 0 o'clock, the two hands overlap each other. H hours and M minutes later, what is the distance in centimeters between the unfixed endpoints of the hands?
Constraints
- All values in input are integers.
- 1 \leq A, B \leq 1000
- 0 \leq H \leq 11
- 0 \leq M \leq 59
Input
Input is given from Standard Input in the following format:
A B H M
Output
Print the answer without units. Your output will be accepted when its absolute or relative error from the correct value is at most 10^{-9}.
Sample Input 1
3 4 9 0
Sample Output 1
5.00000000000000000000
The two hands will be in the positions shown in the figure below, so the answer is 5 centimeters.
Sample Input 2
3 4 10 40
Sample Output 2
4.56425719433005567605
The two hands will be in the positions shown in the figure below. Note that each hand always rotates at constant angular velocity.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 400 点
問題文
あるところに、洞窟があります。
洞窟には N 個の部屋と M 本の通路があり、部屋には 1 から N の、通路には 1 から M の番号がついています。通路 i は部屋 A_i と部屋 B_i を双方向につないでいます。どの 2 部屋間も、通路をいくつか通って行き来できます。部屋 1 は洞窟の入り口がある特別な部屋です。
洞窟の中は薄暗いので、部屋 1 以外の各部屋に 1 つずつ道しるべを設けることにしました。各部屋の道しるべは、その部屋と通路で直接つながっている部屋の 1 つを指すように置きます。
洞窟の中は危険なので、部屋 1 以外のどの部屋についても以下の条件を満たすことが目標です。
- その部屋から出発し、「いまいる部屋にある道しるべを見て、それが指す部屋に移動する」ことを繰り返すと、部屋 1 に最小の移動回数でたどり着く。
目標を達成できる道しるべの配置が存在するか判定し、存在するならばそのような配置を 1 つ出力してください。
制約
- 入力はすべて整数
- 2 \leq N \leq 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)
- A_i \neq B_i\ (1 \leq i \leq M)
- どの 2 部屋間も、通路をいくつか通って行き来できる
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 : A_M B_M
出力
目標を達成できる道しるべの配置が存在しなければ No
を出力せよ。
存在する場合、N 行出力せよ。1 行目には Yes
を、i\ (2 \leq i \leq N) 行目には部屋 i の道しるべが指す部屋の番号を出力せよ。
入力例 1
4 4 1 2 2 3 3 4 4 2
出力例 1
Yes 1 2 2
出力例のように道しるべを置いたとき、
- 部屋 2 から出発した場合 (2) \to 1 と 1 回移動することになり、これが最小です。
- 部屋 3 から出発した場合 (3) \to 2 \to 1 と 2 回移動することになり、これが最小です。
- 部屋 4 から出発した場合 (4) \to 2 \to 1 と 2 回移動することになり、これが最小です。
したがって、出力例のように道しるべを置けば目標を達成できます。
入力例 2
6 9 3 4 6 1 2 4 5 3 4 6 1 5 6 2 4 5 5 6
出力例 2
Yes 6 5 5 1 1
答えが複数あり得る場合、どれを出力してもかまいません。
Score: 400 points
Problem Statement
There is a cave.
The cave has N rooms and M passages. The rooms are numbered 1 to N, and the passages are numbered 1 to M. Passage i connects Room A_i and Room B_i bidirectionally. One can travel between any two rooms by traversing passages. Room 1 is a special room with an entrance from the outside.
It is dark in the cave, so we have decided to place a signpost in each room except Room 1. The signpost in each room will point to one of the rooms directly connected to that room with a passage.
Since it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room 1.
- If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible.
Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists.
Constraints
- All values in input are integers.
- 2 \leq N \leq 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)
- A_i \neq B_i\ (1 \leq i \leq M)
- One can travel between any two rooms by traversing passages.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 : A_M B_M
Output
If there is no way to place signposts satisfying the objective, print No
.
Otherwise, print N lines. The first line should contain Yes
, and the i-th line (2 \leq i \leq N) should contain the integer representing the room indicated by the signpost in Room i.
Sample Input 1
4 4 1 2 2 3 3 4 4 2
Sample Output 1
Yes 1 2 2
If we place the signposts as described in the sample output, the following happens:
- Starting in Room 2, you will reach Room 1 after traversing one passage: (2) \to 1. This is the minimum number of passages possible.
- Starting in Room 3, you will reach Room 1 after traversing two passages: (3) \to 2 \to 1. This is the minimum number of passages possible.
- Starting in Room 4, you will reach Room 1 after traversing two passages: (4) \to 2 \to 1. This is the minimum number of passages possible.
Thus, the objective is satisfied.
Sample Input 2
6 9 3 4 6 1 2 4 5 3 4 6 1 5 6 2 4 5 5 6
Sample Output 2
Yes 6 5 5 1 1
If there are multiple solutions, any of them will be accepted.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 500 点
問題文
N 匹のイワシが釣れました。i 匹目のイワシの美味しさは A_i、香り高さは B_i です。
この中から 1 匹以上のイワシを選んで同じクーラーボックスに入れますが、互いに仲が悪い 2 匹を同時に選ぶことはできません。
i 匹目と j (\neq i) 匹目のイワシは、A_i \cdot A_j + B_i \cdot B_j = 0 を満たすとき(また、その時に限り)仲が悪いです。
イワシの選び方は何通りあるでしょう?答えは非常に大きくなる可能性があるので、1000000007 で割ったあまりを出力してください。
制約
- 入力はすべて整数
- 1 \leq N \leq 2 \times 10^5
- -10^{18} \leq A_i, B_i \leq 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 : A_N B_N
出力
答えを 1000000007 で割ったあまりを出力せよ。
入力例 1
3 1 2 -1 1 2 -1
出力例 1
5
条件を満たす選び方は以下の 5 通りです。
- 1 匹目
- 1, 2 匹目
- 2 匹目
- 2, 3 匹目
- 3 匹目
入力例 2
10 3 2 3 2 -1 1 2 -1 -3 -9 -8 12 7 7 8 1 8 2 8 4
出力例 2
479
Score: 500 points
Problem Statement
We have caught N sardines. The deliciousness and fragrantness of the i-th sardine is A_i and B_i, respectively.
We will choose one or more of these sardines and put them into a cooler. However, two sardines on bad terms cannot be chosen at the same time.
The i-th and j-th sardines (i \neq j) are on bad terms if and only if A_i \cdot A_j + B_i \cdot B_j = 0.
In how many ways can we choose the set of sardines to put into the cooler? Since the count can be enormous, print it modulo 1000000007.
Constraints
- All values in input are integers.
- 1 \leq N \leq 2 \times 10^5
- -10^{18} \leq A_i, B_i \leq 10^{18}
Input
Input is given from Standard Input in the following format:
N A_1 B_1 : A_N B_N
Output
Print the count modulo 1000000007.
Sample Input 1
3 1 2 -1 1 2 -1
Sample Output 1
5
There are five ways to choose the set of sardines, as follows:
- The 1-st
- The 1-st and 2-nd
- The 2-nd
- The 2-nd and 3-rd
- The 3-rd
Sample Input 2
10 3 2 3 2 -1 1 2 -1 -3 -9 -8 12 7 7 8 1 8 2 8 4
Sample Output 2
479
実行時間制限: 3 sec / メモリ制限: 1024 MB
配点: 600 点
問題文
無限に広がる草原があります。
この草原上に、大きさが無視できるほど小さい 1 頭の牛がいます。牛の今いる点から南に x\ \mathrm{cm}、東に y\ \mathrm{cm} 移動した点を (x, y) と表します。牛自身のいる点は (0, 0) です。
また、草原には N 本の縦線と M 本の横線が引かれています。i 本目の縦線は点 (A_i, C_i) と点 (B_i, C_i) とを結ぶ線分、j 本目の横線は点 (D_j, E_j) と点 (D_j, F_j) とを結ぶ線分です。
牛が線分を(端点を含め)通らない限り自由に動き回れるとき、牛が動き回れる範囲の面積は何 \mathrm{cm^2} でしょうか。この範囲の面積が無限大である場合は代わりに INF
と出力してください。
制約
- 入力はすべて -10^9 以上 10^9 以下の整数
- 1 \leq N, M \leq 1000
- A_i < B_i\ (1 \leq i \leq N)
- E_j < F_j\ (1 \leq j \leq M)
- 点 (0, 0) はどの与えられた線分上にも位置しない
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 C_1 : A_N B_N C_N D_1 E_1 F_1 : D_M E_M F_M
出力
牛が動き回れる範囲の面積が無限大ならば INF
を、そうでなければその面積を表す整数 (単位: \mathrm{cm^2}) を出力せよ。
(この問題の制約下で、牛が動き回れる範囲の面積が有限である場合、その面積は必ず整数であることが示せる。)
入力例 1
5 6 1 2 0 0 1 1 0 2 2 -3 4 -1 -2 6 3 1 0 1 0 1 2 2 0 2 -1 -4 5 3 -2 4 1 2 4
出力例 1
13
牛が動き回れる範囲の面積は 13\ \mathrm{cm^2} です。
入力例 2
6 1 -3 -1 -2 -3 -1 1 -2 -1 2 1 4 -2 1 4 -1 1 4 1 3 1 4
出力例 2
INF
牛が動き回れる範囲の面積は無限大です。
Score: 600 points
Problem Statement
There is a grass field that stretches infinitely.
In this field, there is a negligibly small cow. Let (x, y) denote the point that is x\ \mathrm{cm} south and y\ \mathrm{cm} east of the point where the cow stands now. The cow itself is standing at (0, 0).
There are also N north-south lines and M east-west lines drawn on the field. The i-th north-south line is the segment connecting the points (A_i, C_i) and (B_i, C_i), and the j-th east-west line is the segment connecting the points (D_j, E_j) and (D_j, F_j).
What is the area of the region the cow can reach when it can move around as long as it does not cross the segments (including the endpoints)? If this area is infinite, print INF
instead.
Constraints
- All values in input are integers between -10^9 and 10^9 (inclusive).
- 1 \leq N, M \leq 1000
- A_i < B_i\ (1 \leq i \leq N)
- E_j < F_j\ (1 \leq j \leq M)
- The point (0, 0) does not lie on any of the given segments.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 C_1 : A_N B_N C_N D_1 E_1 F_1 : D_M E_M F_M
Output
If the area of the region the cow can reach is infinite, print INF
; otherwise, print an integer representing the area in \mathrm{cm^2}.
(Under the constraints, it can be proved that the area of the region is always an integer if it is not infinite.)
Sample Input 1
5 6 1 2 0 0 1 1 0 2 2 -3 4 -1 -2 6 3 1 0 1 0 1 2 2 0 2 -1 -4 5 3 -2 4 1 2 4
Sample Output 1
13
The area of the region the cow can reach is 13\ \mathrm{cm^2}.
Sample Input 2
6 1 -3 -1 -2 -3 -1 1 -2 -1 2 1 4 -2 1 4 -1 1 4 1 3 1 4
Sample Output 2
INF
The area of the region the cow can reach is infinite.