実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
地上 x メートルの高さから見える水平線は \sqrt{x(12800000+x)} メートル先にあるとするとき、 地上 H メートルの高さから見える水平線が何メートル先にあるか求めてください。
制約
- 1 \leq H \leq 10^5
- H は整数である
入力
入力は以下の形式で標準入力から与えられる。
H
出力
答えを出力せよ。
なお、想定解との絶対誤差または相対誤差が 10^{-6} 以下であれば、正解として扱われる。
入力例 1
333
出力例 1
65287.907678222
\sqrt{333(12800000+333)} = 65287.9076782\ldots です。65287.91 などの出力でも正解となります。
入力例 2
634
出力例 2
90086.635834623
\sqrt{634(12800000+634)} = 90086.6358346\ldots です。
Score : 100 points
Problem Statement
Assuming that the horizon seen from a place x meters above the ground is \sqrt{x(12800000+x)} meters away, find how many meters away the horizon seen from a place H meters above the ground is.
Constraints
- 1 \leq H \leq 10^5
- H is an integer.
Input
Input is given from Standard Input in the following format:
H
Output
Print the answer.
Your answer will be considered correct when the absolute or relative error from the judge's answer is at most 10^{-6}.
Sample Input 1
333
Sample Output 1
65287.907678222
We have \sqrt{333(12800000+333)} = 65287.9076782\ldots. Outputs such as 65287.91 would also be accepted.
Sample Input 2
634
Sample Output 2
90086.635834623
We have \sqrt{634(12800000+634)} = 90086.6358346\ldots.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
N 個の整数の 2 つ組 (A_1, B_1), (A_2, B_2), \ldots, (A_N, B_N) が与えられます。 各 i = 1, 2, \ldots, N について、A_i + B_i を出力してください。
制約
- 1 \leq N \leq 1000
- -10^9 \leq A_i, B_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
N 行出力せよ。 i = 1, 2, \ldots, N について、i 行目には A_i+B_i を出力せよ。
入力例 1
4 3 5 2 -6 -5 0 314159265 123456789
出力例 1
8 -4 -5 437616054
- 1 行目には、A_1 + B_1 = 3 + 5 = 8 を、
- 2 行目には、A_2 + B_2 = 2 + (-6) = -4 を、
- 3 行目には、A_3 + B_3 = (-5) + 0 = -5 を、
- 4 行目には、A_4 + B_4 = 314159265 + 123456789 = 437616054 を出力します。
Score : 100 points
Problem Statement
You are given N pairs of integers: (A_1, B_1), (A_2, B_2), \ldots, (A_N, B_N). For each i = 1, 2, \ldots, N, print A_i + B_i.
Constraints
- 1 \leq N \leq 1000
- -10^9 \leq A_i, B_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print N lines. For i = 1, 2, \ldots, N, the i-th line should contain A_i+B_i.
Sample Input 1
4 3 5 2 -6 -5 0 314159265 123456789
Sample Output 1
8 -4 -5 437616054
- The first line should contain A_1 + B_1 = 3 + 5 = 8.
- The second line should contain A_2 + B_2 = 2 + (-6) = -4.
- The third line should contain A_3 + B_3 = (-5) + 0 = -5.
- The fourth line should contain A_4 + B_4 = 314159265 + 123456789 = 437616054.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
N 人の人があるコンテストに参加し、i 位の人のハンドルネームは S_i でした。
上位 K 人のハンドルネームを辞書順に出力してください。
辞書順とは？
辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。
以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。
- S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
- S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
- S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。
制約
- 1 \leq K \leq N \leq 100
- K, N は整数
- S_i は英小文字からなる長さ 10 以下の文字列
- i \neq j ならば S_i \neq S_j
入力
入力は以下の形式で標準入力から与えられる。
N K S_1 S_2 \vdots S_N
出力
答えを改行区切りで出力せよ。
入力例 1
5 3 abc aaaaa xyz a def
出力例 1
aaaaa abc xyz
このコンテストには 5 人が参加し、1 位の人のハンドルネームは abc 、2 位の人のハンドルネームは aaaaa 、3 位の人のハンドルネームは xyz 、4 位の人のハンドルネームは a 、5 位の人のハンドルネームは def でした。
上位 3 人のハンドルネームは abc、aaaaa、xyz であるため、これを辞書順に並べ替えて aaaaa 、abc 、xyz の順に出力します。
入力例 2
4 4 z zyx zzz rbg
出力例 2
rbg z zyx zzz
入力例 3
3 1 abc arc agc
出力例 3
abc
Score : 200 points
Problem Statement
There were N participants in a contest. The participant ranked i-th had the nickname S_i.
Print the nicknames of the top K participants in lexicographical order.
What is lexicographical order?
Simply put, the lexicographical order is the order of words in a dictionary. As a formal description, below is an algorithm to order distinct strings S and T.
Let S_i denote the i-th character of a string S. We write S \lt T if S is lexicographically smaller than T, and S \gt T if S is larger.
- Let L be the length of the shorter of S and T. For i=1,2,\dots,L, check whether S_i equals T_i.
- If there is an i such that S_i \neq T_i, let j be the smallest such i. Compare S_j and T_j. If S_j is alphabetically smaller than T_j, we get S \lt T; if S_j is larger, we get S \gt T.
- If there is no i such that S_i \neq T_i, compare the lengths of S and T. If S is shorter than T, we get S \lt T; if S is longer, we get S \gt T.
Constraints
- 1 \leq K \leq N \leq 100
- K and N are integers.
- S_i is a string of length 10 consisting of lowercase English letters.
- S_i \neq S_j if i \neq j.
Input
The input is given from Standard Input in the following format:
N K S_1 S_2 \vdots S_N
Output
Print the nicknames, separated by newlines.
Sample Input 1
5 3 abc aaaaa xyz a def
Sample Output 1
aaaaa abc xyz
This contest had five participants. The participants ranked first, second, third, fourth, and fifth had the nicknames abc, aaaaa, xyz, a, and def, respectively.
The nicknames of the top three participants were abc, aaaaa, xyz, so print these in lexicographical order: aaaaa, abc, xyz.
Sample Input 2
4 4 z zyx zzz rbg
Sample Output 2
rbg z zyx zzz
Sample Input 3
3 1 abc arc agc
Sample Output 3
abc
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は野球をモチーフにしたゲームを作ろうとしましたが、うまくコードが書けなくて困っています。
高橋君の代わりに次の問題を解くプログラムを作ってください。
マス 0, マス 1, マス 2, マス 3 の 4 つのマス目があります。はじめマスの上には何もありません。
また、整数 P があり、はじめ P = 0 です。
正の整数からなる数列 A = (A_1, A_2, \dots, A_N) が与えられるので、i = 1, 2, \dots, N について順番に次の操作を行います。
- マス 0 に駒を 1 個置く。
- マス上のすべての駒を番号が A_i 大きいマスに進める。言い換えると、駒がマス x にあればその駒をマス x + A_i に移動する。
ただし移動先のマスが存在しない (すなわち x + A_i が 4 以上になる) 駒たちに関しては、それらを取り除いて P に取り除いた個数を加算する。
すべての操作を行った後の P の値を出力してください。
制約
- 1 \leq N \leq 100
- 1 \leq A_i \leq 4
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
操作終了時点での P の値を出力せよ。
入力例 1
4 1 1 3 2
出力例 1
3
操作を説明すると次のようになり、操作終了時点での P の値は 3 になります。
- i=1 での操作
- マス 0 に駒を置く。この時点でマス 0 にコマが乗っている。
- すべての駒を 1 大きいマスに進める。移動を終えた時点でマス 1 に駒が乗っている。
- i=2 での操作
- マス 0 に駒を置く。この時点でマス 0, 1 にコマが乗っている。
- すべての駒を 1 大きいマスに進める。移動を終えた時点でマス 1, 2 に駒が乗っている。
- i=3 での操作
- マス 0 に駒を置く。この時点でマス 0, 1, 2 にコマが乗っている。
- すべての駒を 3 大きいマスに進める。
この時、マス 1,2 にある駒は移動先のマスが存在しないため (それぞれ 1+3=4,2+3=5 なので) 、盤上から取り除いて P に 2 を加算する。P の値は 2 になる。
移動を終えた時点でマス 3 に駒が乗っている。
- i=4 での操作
- マス 0 に駒を置く。この時点でマス 0, 3 にコマが乗っている。
- すべての駒を 2 大きいマスに進める。
この時、マス 3 にある駒は移動先のマスが存在しないため (3+2=5 なので) 、盤上から取り除いて P に 1 を加算する。P の値は 3 になる。
移動を終えた時点でマス 2 に駒が乗っている。
入力例 2
3 1 1 1
出力例 2
0
P の値が操作中に変化しない場合もあります。
入力例 3
10 2 2 4 1 1 1 4 2 2 1
出力例 3
8
Score : 200 points
Problem Statement
Takahashi is trying to create a game inspired by baseball, but he is having difficulty writing the code.
Write a program for Takahashi that solves the following problem.
There are 4 squares called Square 0, Square 1, Square 2, and Square 3. Initially, all squares are empty.
There is also an integer P; initially, P = 0.
Given a sequence of positive integers A = (A_1, A_2, \dots, A_N), perform the following operations for i = 1, 2, \dots, N in this order:
- Put a piece on Square 0.
- Advance every piece on the squares A_i squares ahead. In other words, if Square x has a piece, move the piece to Square (x + A_i).
If, however, the destination square does not exist (i.e. x + A_i is greater than or equal to 4) for a piece, remove it. Add to P the number of pieces that have been removed.
Print the value of P after all the operations have been performed.
Constraints
- 1 \leq N \leq 100
- 1 \leq A_i \leq 4
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the value of P after all the operations have been performed.
Sample Input 1
4 1 1 3 2
Sample Output 1
3
The operations are described below. After all the operations have been performed, P equals 3.
- The operations for i=1:
- Put a piece on Square 0. Now, Square 0 has a piece.
- Advance every piece on the squares 1 square ahead. After these moves, Square 1 has a piece.
- The operations for i=2:
- Put a piece on Square 0. Now, Squares 0 and 1 have a piece.
- Advance every piece on the squares 1 square ahead. After these moves, Squares 1 and 2 have a piece.
- The operations for i=3:
- Put a piece on Square 0. Now, Squares 0, 1, and 2 have a piece.
- Advance every piece on the squares 3 squares ahead.
Here, for the pieces on Squares 1 and 2, the destination squares do not exist (since 1+3=4 and 2+3=5), so remove these pieces and add 2 to P. P now equals 2. After these moves, Square 3 has a piece.
- The operations for i=4:
- Put a piece on Square 0. Now, Squares 0 and 3 have a piece.
- Advance every piece on the squares 2 squares ahead.
Here, for the piece on Square 3, the destination square does not exist (since 3+2=5), so remove this piece and add 1 to P. P now equals 3.
After these moves, Square 2 has a piece.
Sample Input 2
3 1 1 1
Sample Output 2
0
The value of P may not be updated by the operations.
Sample Input 3
10 2 2 4 1 1 1 4 2 2 1
Sample Output 3
8
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君と青木君は 2 人で次の対戦ゲームをします。
高橋君が先手でゲームを始め、ゲームが終了するまでの間、 2 人は交互に 1 以上 2N+1 以下の整数を 1 つずつ宣言します。 どちらかが一度でも宣言した整数は、それ以降どちらも二度と宣言することが出来ません。 先に整数を宣言することが出来なくなった方のプレイヤーの負けとなり、負けなかった方のプレイヤーの勝ちとなります。
このゲームでは必ず高橋君が勝ちます。 高橋君の立場で実際にゲームを行い、ゲームに勝ってください。
制約
- 1 \leq N \leq 1000
- N は整数
入出力
この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。
あなたのプログラムが高橋君の立場で、ジャッジプログラムが青木君の立場でゲームを行います。
まず、あなたのプログラムに標準入力から正の整数 N が与えられます。 その後、ゲームが終了するまで下記の手順を繰り返します。
- あなたのプログラムが、高橋君が宣言する整数として、1 以上 2N+1 以下の整数を標準出力に出力します。（どちらかのプレイヤーによってすでに宣言されている整数を出力することは出来ません。）
- ジャッジプログラムによって、青木君が宣言する整数があなたのプログラムに標準入力から与えられます。（どちらかのプレイヤーによってすでに宣言されている整数が入力されることはありません。） ただし、青木君が宣言できる整数が残っていない場合は、代わりに 0 が与えられ高橋君の勝ちでゲームが終了します。
注意点
- 出力を行うたびに標準出力をflushしてください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
- 高橋君の勝ちでゲームが終了したあと、あなたのプログラムは直ちに終了しなければなりません。そうしなかった場合、ジャッジ結果が AC とならない可能性があります。
- ゲームの途中で不正な出力を行った場合（例えば、すでにどちらかのプレイヤーによって宣言されている整数を出力した場合）は不正解となりますが、そのときのジャッジ結果は不定です。WA になるとは限りません。
入出力例
| 入力 | 出力 | 説明 |
|---|---|---|
| 2 | まず整数 N が与えられます。 | |
| 1 | 高橋君が 1 を宣言します。 | |
| 3 | 青木君が 3 を宣言します。 | |
| 2 | 高橋君が 2 を宣言します。 | |
| 4 | 青木君が 4 を宣言します。 | |
| 5 | 高橋君が 5 を宣言します。 | |
| 0 | 青木君が宣言できる整数が残っていないため、高橋君の勝ちでゲームが終了します。 |
Score : 300 points
Problem Statement
Takahashi and Aoki will play the following game against each other.
Starting from Takahashi, the two alternatingly declare an integer between 1 and 2N+1 (inclusive) until the game ends. Any integer declared by either player cannot be declared by either player again. The player who is no longer able to declare an integer loses; the player who didn't lose wins.
In this game, Takahashi will always win. Your task is to actually play the game on behalf of Takahashi and win the game.
Constraints
- 1 \leq N \leq 1000
- N is an integer.
Input and Output
This task is an interactive task (in which your program and the judge program interact with each other via inputs and outputs).
Your program plays the game on behalf of Takahashi, and the judge program plays the game on behalf of Aoki.
First, your program is given a positive integer N from Standard Input. Then, the following procedures are repeated until the game ends.
- Your program outputs an integer between 1 and 2N+1 (inclusive) to Standard Output, which defines the integer that Takahashi declares. (You cannot output an integer that is already declared by either player.)
- The integer that Aoki declares is given by the judge program to your program from Standard Input. (No integer that is already declared by either player will be given.) If Aoki has no more integer to declare, 0 is given instead, which means that the game ended and Takahashi won.
Notes
- After each output, you must flush Standard Output. Otherwise, you may get TLE.
- After the game ended and Takahashi won, the program must be terminated immediately. Otherwise, the judge does not necessarily give AC.
- If your program outputs something that violates the rules of the game (such as an integer that has already been declared by either player), your answer is considered incorrect. In such case, the verdict is indeterminate. It does not necessarily give WA.
Sample Input and Output
| Input | Output | Description |
|---|---|---|
| 2 | First, an integer N is given. | |
| 1 | Takahashi declares an integer 1. | |
| 3 | Aoki declares an integer 3. | |
| 2 | Takahashi declares an integer 2. | |
| 4 | Aoki declares an integer 4. | |
| 5 | Takahashi declares an integer 5. | |
| 0 | Aoki has no more integer to declare, so Takahashi wins, and the game ends. |