実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
英小文字からなる文字列 S が与えられます。 S の長さは 1 以上かつ 3 以下です。
S を繰り返して得られる文字列であって、長さが 6 のものを出力してください。
本問題の制約下で、そのような文字列はただ一つ存在することが示せます。
制約
- S は英小文字からなる長さ 1 以上 3 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えとなる長さ 6 の文字列を出力せよ。
入力例 1
abc
出力例 1
abcabc
S = abc を繰り返してできる文字列として、abc 、abcabc 、abcabcabc 、abcabcabcabc などがあります。
そのうち、長さが 6 のものは abcabc です。よって、abcabc と出力します。
入力例 2
zz
出力例 2
zzzzzz
Score : 100 points
Problem Statement
You are given a string S consisting of lowercase English characters. The length of S is between 1 and 3, inclusive.
Print the string of length 6 that is a repetition of S.
It can be shown that there uniquely exists such a string under the Constraints of this problem.
Constraints
- S is a string consisting of lowercase English characters of length between 1 and 3, inclusive.
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer string, which is of length 6.
Sample Input 1
abc
Sample Output 1
abcabc
These are strings that are repetitions of S = abc: abc, abcabc, abcabcabc, abcabcabcabc, and so on.
Among them, abcabc has the length of 6, so abcabc should be printed.
Sample Input 2
zz
Sample Output 2
zzzzzz
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
N が与えられます。2^N を出力してください。
制約
- 0 \leq N \leq 30
- N は整数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
3
出力例 1
8
2^3=8 です。
入力例 2
30
出力例 2
1073741824
Score : 100 points
Problem Statement
Given N, print 2^N.
Constraints
- 0 \leq N \leq 30
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
3
Sample Output 1
8
We have 2^3=8.
Sample Input 2
30
Sample Output 2
1073741824
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
長さ N の整数列 A=(A_1,\ldots,A_N) が与えられます。ここで A_1,A_2,\ldots,A_N は相異なります。
A の中で二番目に大きい要素は A の何番目の要素でしょうか。
制約
- 2\leq N\leq 100
- 1\leq A_i \leq 10^9
- A_1,A_2,\ldots,A_N は相異なる
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \ldots A_{N}
出力
A の中で二番目に大きい要素が A の X 番目であるとき、X を整数として出力せよ。
入力例 1
4 8 2 5 1
出力例 1
3
A の中で二番目に大きい要素は A_3 なので 3 を出力してください。
入力例 2
8 1 2 3 4 5 10 9 11
出力例 2
6
Score : 200 points
Problem Statement
You are given an integer sequence A=(A_1,\ldots,A_N) of length N. Here, A_1, A_2, \ldots, A_N are all distinct.
Which element in A is the second largest?
Constraints
- 2 \leq N \leq 100
- 1 \leq A_i \leq 10^9
- A_1, A_2, \ldots, A_N are all distinct.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_{N}
Output
Print the integer X such that the X-th element in A is the second largest.
Sample Input 1
4 8 2 5 1
Sample Output 1
3
The second largest element in A is A_3, so print 3.
Sample Input 2
8 1 2 3 4 5 10 9 11
Sample Output 2
6
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
xy 平面上に N 人の人 1,2,\dots,N がおり、人 i は座標 (X_i,Y_i) にいます。
このうち、 K 人の人 A_1,A_2,\dots,A_K に同じ強さの明かりを持たせます。
座標 (x,y) にいる人が強さ R の明かりを持っている時、その明かりによって中心 (x,y) 、半径 R の円の内部全体(境界を含む)が照らされます。
すべての人が少なくとも 1 つの明かりによって照らされるために必要な明かりの強さの最小値を求めてください。
制約
- 入力は全て整数
- 1 \le K < N \le 1000
- 1 \le A_1 < A_2 < \dots < A_K \le N
- |X_i|,|Y_i| \le 10^5
- i \neq j ならば (X_i,Y_i) \neq (X_j,Y_j)
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_K X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
答えを実数として出力せよ。
出力された解と想定解との絶対誤差または相対誤差が 10^{-5} 以下であるならば、出力は正しいと見なされる。
入力例 1
4 2 2 3 0 0 0 1 1 2 2 0
出力例 1
2.23606797749978969
この入力では人が 4 人おり、そのうち人 2,3 が明かりを持ちます。
R \ge \sqrt{5} \approx 2.236068 である時、すべての人が少なくとも 1 つの明かりによって照らされます。
入力例 2
2 1 2 -100000 -100000 100000 100000
出力例 2
282842.712474619009
入力例 3
8 3 2 6 8 -17683 17993 93038 47074 58079 -57520 -41515 -89802 -72739 68805 24324 -73073 71049 72103 47863 19268
出力例 3
130379.280458974768
Score : 200 points
Problem Statement
There are N people numbered 1, 2, \dots, N in the xy-plane. Person i is at the coordinates (X_i, Y_i).
K of these people, Persons A_1, A_2, \dots, A_K, will receive lights of the same strength.
When a person at coordinates (x, y) has a light of strength R, it lights up the interior of a circle of radius R centered at (x, y) (including the boundary).
Find the minimum strength of the lights needed for every person to be lit by at least one light.
Constraints
- All values in input are integers.
- 1 \le K < N \le 1000
- 1 \le A_1 < A_2 < \dots < A_K \le N
- |X_i|,|Y_i| \le 10^5
- (X_i,Y_i) \neq (X_j,Y_j), if i \neq j.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_K X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Print the answer as a real number.
Your output will be considered correct if its absolute or relative error from the judge's output is at most 10^{-5}.
Sample Input 1
4 2 2 3 0 0 0 1 1 2 2 0
Sample Output 1
2.23606797749978969
This input contains four people. Among them, Persons 2 and 3 will have lights.
Every person will be lit by at least one light if R \ge \sqrt{5} \approx 2.236068.
Sample Input 2
2 1 2 -100000 -100000 100000 100000
Sample Output 2
282842.712474619009
Sample Input 3
8 3 2 6 8 -17683 17993 93038 47074 58079 -57520 -41515 -89802 -72739 68805 24324 -73073 71049 72103 47863 19268
Sample Output 3
130379.280458974768
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
3\times3 のマス目に 1 から 9 までの数字が書き込まれており、上から i 行目、左から j 列目 (1\leq i\leq3,1\leq j\leq3) に書き込まれている数字は c _ {i,j} です。
異なるマスに同じ数字が書き込まれている場合もありますが、同じ数字が縦・横・斜めに 3 つ連続して書き込まれていることはありません。 より厳密には、c _ {i,j} について次の条件のすべてが成り立っていることが保証されます。
- どの 1\leq i\leq3 についても、c _ {i,1}=c _ {i,2}=c _ {i,3} ではない
- どの 1\leq j\leq3 についても、c _ {1,j}=c _ {2,j}=c _ {3,j} ではない
- c _ {1,1}=c _ {2,2}=c _ {3,3} ではない
- c _ {3,1}=c _ {2,2}=c _ {1,3} ではない
高橋くんは、それぞれのマスに書かれている数字をランダムな順番で知ります。 高橋くんは、縦・横・斜めの列のうちの 1 つでも次の条件を満たしたときがっかりします。
- はじめに知ったほうの 2 マスに書かれた数字が同じであり、最後に知ったマスに書かれた数字がそれと異なる。
高橋くんががっかりせずにすべてのマスに書かれた数字を知る確率を求めてください。
制約
- c _ {i,j}\in\lbrace1,2,3,4,5,6,7,8,9\rbrace\ (1\leq i\leq3,1\leq j\leq3)
- c _ {i,1}=c _ {i,2}=c _ {i,3} ではない (1\leq i\leq3)
- c _ {1,j}=c _ {2,j}=c _ {3,j} ではない (1\leq j\leq3)
- c _ {1,1}=c _ {2,2}=c _ {3,3} ではない
- c _ {1,3}=c _ {2,2}=c _ {3,1} ではない
入力
入力は以下の形式で標準入力から与えられる。
c _ {1,1} c _ {1,2} c _ {1,3}
c _ {2,1} c _ {2,2} c _ {2,3}
c _ {3,1} c _ {3,2} c _ {3,3}
出力
高橋くんががっかりせずにすべてのマスに書かれた数字を知る確率を 1 行で出力せよ。 真の値からの絶対誤差が 10 ^ {-8} 以下であるとき、正答と判定される。
入力例 1
3 1 9 2 5 6 2 7 1
出力例 1
0.666666666666666666666666666667
例えば、高橋くんが c _ {3,1}=2,c _ {2,1}=2,c _ {1,1}=3 の順に知った場合、高橋くんはがっかりしてしまいます。
対して、高橋くんが c _ {1,1},c _ {1,2},c _ {1,3},c _ {2,1},c _ {2,2},c _ {2,3},c _ {3,1},c _ {3,2},c _ {3,3} の順に数字を知った場合、がっかりすることなくすべての数字を知ることができます。
高橋くんががっかりすることなくすべての数字を知ることができる確率は \dfrac 23 です。 絶対誤差が 10 ^ {-8} 以下であれば正答と判定されるため、0.666666657 や 0.666666676 のように出力しても正解になります。
入力例 2
7 7 6 8 6 8 7 7 6
出力例 2
0.004982363315696649029982363316
入力例 3
3 6 7 1 9 7 5 7 5
出力例 3
0.4
Score : 300 points
Problem Statement
There is a 3\times3 grid with numbers between 1 and 9, inclusive, written in each square. The square at the i-th row from the top and j-th column from the left (1\leq i\leq3,1\leq j\leq3) contains the number c _ {i,j}.
The same number may be written in different squares, but not in three consecutive cells vertically, horizontally, or diagonally. More precisely, it is guaranteed that c _ {i,j} satisfies all of the following conditions.
- c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
- c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
- c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
- c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.
Takahashi will see the numbers written in each cell in random order. He will get disappointed when there is a line (vertical, horizontal, or diagonal) that satisfies the following condition.
- The first two squares he sees contain the same number, but the last square contains a different number.
Find the probability that Takahashi sees the numbers in all the squares without getting disappointed.
Constraints
- c _ {i,j}\in\lbrace1,2,3,4,5,6,7,8,9\rbrace\ (1\leq i\leq3,1\leq j\leq3)
- c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
- c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
- c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
- c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.
Input
The input is given from Standard Input in the following format:
c _ {1,1} c _ {1,2} c _ {1,3}
c _ {2,1} c _ {2,2} c _ {2,3}
c _ {3,1} c _ {3,2} c _ {3,3}
Output
Print one line containing the probability that Takahashi sees the numbers in all the squares without getting disappointed. Your answer will be considered correct if the absolute error from the true value is at most 10 ^ {-8}.
Sample Input 1
3 1 9 2 5 6 2 7 1
Sample Output 1
0.666666666666666666666666666667
For example, if Takahashi sees c _ {3,1}=2,c _ {2,1}=2,c _ {1,1}=3 in this order, he will get disappointed.
On the other hand, if Takahashi sees c _ {1,1},c _ {1,2},c _ {1,3},c _ {2,1},c _ {2,2},c _ {2,3},c _ {3,1},c _ {3,2},c _ {3,3} in this order, he will see all numbers without getting disappointed.
The probability that Takahashi sees all the numbers without getting disappointed is \dfrac 23. Your answer will be considered correct if the absolute error from the true value is at most 10 ^ {-8}, so outputs such as 0.666666657 and 0.666666676 would also be accepted.
Sample Input 2
7 7 6 8 6 8 7 7 6
Sample Output 2
0.004982363315696649029982363316
Sample Input 3
3 6 7 1 9 7 5 7 5
Sample Output 3
0.4