Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
(1,2,…,N) を並び替えた数列 P と整数 X が与えられます。 数列 P の i 番目の項の値は P_i です。 P_k = X を満たす k を出力してください。
制約
- 1 \leq N \leq 100
- 1 \leq X \leq N
- P は (1,2,…,N) を並び替えてできる数列
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X P_1 P_2 \ldots P_N
出力
答えを出力せよ。
入力例 1
4 3 2 3 1 4
出力例 1
2
P = (2,3,1,4) なので、P_2 = 3 です。したがって、2 を出力します。
入力例 2
5 2 3 5 1 4 2
出力例 2
5
入力例 3
6 6 1 2 3 4 5 6
出力例 3
6
Score : 100 points
Problem Statement
You are given a sequence P that is a permutation of (1,2,…,N), and an integer X. The i-th term of P has a value of P_i. Print k such that P_k = X.
Constraints
- 1 \leq N \leq 100
- 1 \leq X \leq N
- P is a permutation of (1,2,…,N).
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N X P_1 P_2 \ldots P_N
Output
Print the answer.
Sample Input 1
4 3 2 3 1 4
Sample Output 1
2
We have P = (2,3,1,4), so P_2 = 3. Thus, you should print 2.
Sample Input 2
5 2 3 5 1 4 2
Sample Output 2
5
Sample Input 3
6 6 1 2 3 4 5 6
Sample Output 3
6
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
3 つの数字 x,y,z をこの順に並べてできる 3 桁の整数を xyz と表すことにします。
どの桁も 0 でない 3 桁の整数 abc が与えられるので、abc+bca+cab を求めてください。
制約
- abc は どの桁も 0 でない 3 桁の整数
入力
入力は以下の形式で標準入力から与えられる。
abc
出力
答えを出力せよ。
入力例 1
123
出力例 1
666
123+231+312=666 となります。
入力例 2
999
出力例 2
2997
999+999+999=2997 となります。
Score : 100 points
Problem Statement
Let xyz denote the 3-digit integer whose digits are x, y, z from left to right.
Given a 3-digit integer abc none of whose digits is 0, find abc+bca+cab.
Constraints
- abc is a 3-digit integer abc none of whose digits is 0.
Input
Input is given from Standard Input in the following format:
abc
Output
Print the answer.
Sample Input 1
123
Sample Output 1
666
We have 123+231+312=666.
Sample Input 2
999
Sample Output 2
2997
We have 999+999+999=2997.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
1,2,3,4,5,6 の 6 種類の目が出るサイコロを 2 つ振ったときに、次の 2 つの条件の少なくとも一方を満たす確率を求めてください。
- 2 つの出目の合計が X 以上である。
- 2 つの出目の差の絶対値が Y 以上である。
ここで、どちらのサイコロについても 6 種類のどの目が出るかは同様に確からしく、それぞれのサイコロの出目は独立であるとします。
制約
- 2\leq X\leq13
- 0\leq Y\leq6
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
X Y
出力
2 つのサイコロの出目が 2 つの条件の少なくとも一方を満たす確率を出力せよ。 出力された値と真の値との絶対誤差が 10 ^ {-9} 以下のとき、正答と判定される。
入力例 1
9 3
出力例 1
0.555555555555555555555555555555
2 つのサイコロの出目がそれぞれ x と y であることを (x,y) で表すことにすると、それぞれの条件を満たすのは次の場合です。
- 2 つのサイコロの出目の和が 9 以上になるのは、(3,6),(4,5),(4,6),(5,4),(5,5),(5,6),(6,3),(6,4),(6,5),(6,6) のとき
- 2 つのサイコロの出目の差が 3 以上になるのは、(1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(5,1),(5,2),(6,1),(6,2),(6,3) のとき
これらの条件の少なくとも一方を満たすのは (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(4,5),(4,6),(5,1),(5,2),(5,4),(5,5),(5,6),(6,1),(6,2),(6,3),(6,4),(6,5),(6,6) の 20 通りのいずれかのときです。
よって、求める答えは \dfrac{20}{36}=\dfrac59=0.5555555555\ldots です。
絶対誤差が 10 ^ {-9} 以下のとき正答と判定されるので、0.5555555565 や 0.55555555456789 などと出力しても正解となります。
入力例 2
13 6
出力例 2
0
2 つのサイコロの出目の和が 13 以上になることも、差が 6 以上になることもありません。
よって、求める答えは 0 です。
入力例 3
10 3
出力例 3
0.5
Score : 250 points
Problem Statement
Two dice, each with six faces 1,2,3,4,5,6, are rolled. Find the probability that at least one of the following two conditions holds:
- The sum of the two outcomes is at least X.
- The absolute difference of the two outcomes is at least Y.
Each face of each die is equally likely, and the two dice are independent.
Constraints
- 2 \le X \le 13
- 0 \le Y \le 6
- All input values are integers.
Input
The input is given from Standard Input in the following format:
X Y
Output
Output the probability that the two outcomes satisfy at least one of the two conditions. Your answer is accepted if its absolute error from the true value is at most 10^{-9}.
Sample Input 1
9 3
Sample Output 1
0.555555555555555555555555555555
Let (x,y) denote the event that the dice show x and y.
- The sum is at least 9 for (3,6),(4,5),(4,6),(5,4),(5,5),(5,6),(6,3),(6,4),(6,5),(6,6).
- The difference is at least 3 for (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(5,1),(5,2),(6,1),(6,2),(6,3).
At least one of these conditions holds for the following 20 pairs: (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(4,5),(4,6),(5,1),(5,2),(5,4),(5,5),(5,6),(6,1),(6,2),(6,3),(6,4),(6,5),(6,6).
Thus, the answer is \dfrac{20}{36}=\dfrac59=0.5555555555\ldots.
Because an absolute error of at most 10^{-9} is allowed, outputs such as 0.5555555565 or 0.55555555456789 are accepted.
Sample Input 2
13 6
Sample Output 2
0
Neither the sum of two dice can be 13 or greater, nor can their difference be 6 or greater.
Thus, the answer is 0.
Sample Input 3
10 3
Sample Output 3
0.5
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
1,2,\ldots,N と番号づけられた N 人が M 回、一列に並んで集合写真を撮りました。i 番目の撮影で左から j 番目に並んだ人の番号は a_{i,j} です。
ある二人組は M 回の撮影で一度も連続して並ばなかった場合、不仲である可能性があります。
不仲である可能性がある二人組の個数を求めてください。なお、人 x と人 y からなる二人組と人 y と人 x からなる二人組は区別しません。
制約
- 2 \leq N \leq 50
- 1 \leq M \leq 50
- 1 \leq a_{i,j} \leq N
- a_{i,1},\ldots,a_{i,N} には 1,\ldots,N が 1 回ずつ現れる
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
a_{1,1} \ldots a_{1,N}
\vdots
a_{M,1} \ldots a_{M,N}
出力
答えを出力せよ。
入力例 1
4 2 1 2 3 4 4 3 1 2
出力例 1
2
人 1 と人 4 からなる二人組と、人 2 と人 4 からなる二人組がそれぞれ不仲である可能性があります。
入力例 2
3 3 1 2 3 3 1 2 1 2 3
出力例 2
0
入力例 3
10 10 4 10 7 2 8 3 9 1 6 5 3 6 2 9 1 8 10 7 4 5 9 3 4 5 7 10 1 8 2 6 7 3 1 8 4 9 5 6 2 10 5 2 1 4 10 7 9 8 3 6 5 8 1 6 9 3 2 4 7 10 8 10 3 4 5 7 2 9 6 1 3 10 2 7 8 5 1 4 9 6 10 6 1 5 4 2 3 8 9 7 4 5 9 1 8 2 7 6 3 10
出力例 3
6
Score : 200 points
Problem Statement
N people numbered 1,2,\ldots,N were in M photos. In each of the photos, they stood in a single line. In the i-th photo, the j-th person from the left is person a_{i,j}.
Two people who did not stand next to each other in any of the photos may be in a bad mood.
How many pairs of people may be in a bad mood? Here, we do not distinguish a pair of person x and person y, and a pair of person y and person x.
Constraints
- 2 \leq N \leq 50
- 1 \leq M \leq 50
- 1 \leq a_{i,j} \leq N
- a_{i,1},\ldots,a_{i,N} contain each of 1,\ldots,N exactly once.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M
a_{1,1} \ldots a_{1,N}
\vdots
a_{M,1} \ldots a_{M,N}
Output
Print the answer.
Sample Input 1
4 2 1 2 3 4 4 3 1 2
Sample Output 1
2
The pair of person 1 and person 4, and the pair of person 2 and person 4, may be in a bad mood.
Sample Input 2
3 3 1 2 3 3 1 2 1 2 3
Sample Output 2
0
Sample Input 3
10 10 4 10 7 2 8 3 9 1 6 5 3 6 2 9 1 8 10 7 4 5 9 3 4 5 7 10 1 8 2 6 7 3 1 8 4 9 5 6 2 10 5 2 1 4 10 7 9 8 3 6 5 8 1 6 9 3 2 4 7 10 8 10 3 4 5 7 2 9 6 1 3 10 2 7 8 5 1 4 9 6 10 6 1 5 4 2 3 8 9 7 4 5 9 1 8 2 7 6 3 10
Sample Output 3
6
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) および正整数 K が与えられます。
1 以上 K 以下の整数のうち、A の中に一度も現れないものの総和を求めてください。
制約
- 1\leq N \leq 2\times 10^5
- 1\leq K \leq 2\times 10^9
- 1\leq A_i \leq 2\times 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
4 5 1 6 3 1
出力例 1
11
1 以上 5 以下の整数のうち、A の中に一度も現れないものは 2,4,5 の 3 つです。
よって、それらの総和である 2+4+5=11 を出力します。
入力例 2
1 3 346
出力例 2
6
入力例 3
10 158260522 877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739
出力例 3
12523196466007058
Score: 250 points
Problem Statement
You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N and a positive integer K.
Find the sum of the integers between 1 and K, inclusive, that do not appear in the sequence A.
Constraints
- 1\leq N \leq 2\times 10^5
- 1\leq K \leq 2\times 10^9
- 1\leq A_i \leq 2\times 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
4 5 1 6 3 1
Sample Output 1
11
Among the integers between 1 and 5, three numbers, 2, 4, and 5, do not appear in A.
Thus, print their sum: 2+4+5=11.
Sample Input 2
1 3 346
Sample Output 2
6
Sample Input 3
10 158260522 877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739
Sample Output 3
12523196466007058