実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
0 と 1 からなる長さ 64 の数列 A=(A_0,A_1,\dots,A_{63}) が与えられます。
A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} を求めてください。
制約
- A_i は 0 または 1
入力
入力は以下の形式で標準入力から与えられる。
A_0 A_1 \dots A_{63}
出力
答えを整数として出力せよ。
入力例 1
1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力例 1
13
A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13 です。
入力例 2
1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0
出力例 2
766067858140017173
Score : 200 points
Problem Statement
You are given a sequence A=(A_0,A_1,\dots,A_{63}) of length 64 consisting of 0 and 1.
Find A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63}.
Constraints
- A_i is 0 or 1.
Input
The input is given from Standard Input in the following format:
A_0 A_1 \dots A_{63}
Output
Print the answer as an integer.
Sample Input 1
1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample Output 1
13
A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13.
Sample Input 2
1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0
Sample Output 2
766067858140017173
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 150 点
問題文
2 以上の整数 X が与えられます。
N!=X を満たすような正の整数 N を求めてください。
ただし、N! は N の階乗を表し、そのような N がただ一つ存在することは保証されています。
制約
- 2 \leq X \leq 3 \times 10^{18}
- N!=X を満たすような正の整数 N がただ一つ存在する
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
X
出力
答えを出力せよ。
入力例 1
6
出力例 1
3
3!=3\times2\times1=6 より、3 を出力します。
入力例 2
2432902008176640000
出力例 2
20
20!=2432902008176640000 より、20 を出力します。
Score : 150 points
Problem Statement
You are given an integer X not less than 2.
Find the positive integer N such that N! = X.
Here, N! denotes the factorial of N, and it is guaranteed that there is exactly one such N.
Constraints
- 2 \leq X \leq 3 \times 10^{18}
- There is exactly one positive integer N such that N!=X.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
X
Output
Print the answer.
Sample Input 1
6
Sample Output 1
3
From 3!=3\times2\times1=6, print 3.
Sample Input 2
2432902008176640000
Sample Output 2
20
From 20!=2432902008176640000, print 20.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
正の整数 N が与えられます。
A\leq B\leq C かつ ABC\leq N であるような正の整数の組 (A,B,C) の個数を求めてください。
なお、制約の条件下で答えは 2^{63} 未満であることが保証されます。
制約
- 1 \leq N \leq 10^{11}
- N は整数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
4
出力例 1
5
条件を満たす組は (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2) の 5 つです。
入力例 2
100
出力例 2
323
入力例 3
100000000000
出力例 3
5745290566750
Score : 300 points
Problem Statement
You are given a positive integer N.
Find the number of triples of positive integers (A, B, C) such that A\leq B\leq C and ABC\leq N.
The Constraints guarantee that the answer is less than 2^{63}.
Constraints
- 1 \leq N \leq 10^{11}
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
4
Sample Output 1
5
There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).
Sample Input 2
100
Sample Output 2
323
Sample Input 3
100000000000
Sample Output 3
5745290566750
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
縦 N 行、横 N 列のマス目があり、上から i 行目、左から j 列目のマスには整数 N\times (i-1)+j が書かれています。
今から T ターンにわたって相異なる整数が宣言されます。i ターン目には A_i が宣言され、A_i が書かれたマスに印をつけます。初めてビンゴを達成するのは何ターン目か求めてください。ただし、T ターンの中でビンゴを達成しない場合は -1 を出力してください。
ここで、ビンゴを達成するとは以下のいずれかのうち少なくとも一つ満たされることを言います。
- マス目の横の列であって、列に含まれる N 個のマスすべてに印がついているものが存在する
- マス目の縦の列であって、列に含まれる N 個のマスすべてに印がついているものが存在する
- マス目の対角線の列であって、列に含まれる N 個のマスすべてに印がついているものが存在する
制約
- 2\leq N\leq 2\times 10^3
- 1\leq T\leq \min(N^2,2\times 10^5)
- 1\leq A_i\leq N^2
- i\neq j ならば A_i\neq A_j
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N T A_1 A_2 \ldots A_T
出力
T ターンの中でビンゴを達成するならば初めてビンゴを達成するターンを、そうでないならば -1 を出力せよ。
入力例 1
3 5 5 1 8 9 7
出力例 1
4
マス目の状態は以下のように変化します。初めてビンゴを達成するのは 4 ターン目です。
入力例 2
3 5 4 2 9 7 5
出力例 2
-1
5 ターンの中でビンゴを達成できないので -1 を出力してください。
入力例 3
4 12 13 9 6 5 2 7 16 14 8 3 10 11
出力例 3
9
Score : 300 points
Problem Statement
There is an N \times N grid, where the cell at the i-th row from the top and the j-th column from the left contains the integer N \times (i-1) + j.
Over T turns, integers will be announced. On Turn i, the integer A_i is announced, and the cell containing A_i is marked. Determine the turn on which Bingo is achieved for the first time. If Bingo is not achieved within T turns, print -1.
Here, achieving Bingo means satisfying at least one of the following conditions:
- There exists a row in which all N cells are marked.
- There exists a column in which all N cells are marked.
- There exists a diagonal line (from top-left to bottom-right or from top-right to bottom-left) in which all N cells are marked.
Constraints
- 2 \leq N \leq 2 \times 10^3
- 1 \leq T \leq \min(N^2, 2 \times 10^5)
- 1 \leq A_i \leq N^2
- A_i \neq A_j if i \neq j.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N T A_1 A_2 \ldots A_T
Output
If Bingo is achieved within T turns, print the turn number on which Bingo is achieved for the first time; otherwise, print -1.
Sample Input 1
3 5 5 1 8 9 7
Sample Output 1
4
The state of the grid changes as follows. Bingo is achieved for the first time on Turn 4.
Sample Input 2
3 5 4 2 9 7 5
Sample Output 2
-1
Bingo is not achieved within five turns, so print -1.
Sample Input 3
4 12 13 9 6 5 2 7 16 14 8 3 10 11
Sample Output 3
9
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
N \times N のマス目が与えられます。このうち上から i 行目、左から j 列目のマスを (i,j) と書きます。
各マスの状態を表す N 個の長さ N の文字列 S_1,S_2,\dots,S_N が以下の形式で与えられます。
- S_i の j 文字目が
oであるとき、 (i,j) にはoが書かれている。 - S_i の j 文字目が
xであるとき、 (i,j) にはxが書かれている。
以下の条件を全て満たすマスの三つ組の個数を求めてください。
- 組に含まれる 3 マスは相異なる。
- 3 マス全てに
oが書かれている。 - マスのうち、丁度 2 つが同じ行にある。
- マスのうち、丁度 2 つが同じ列にある。
但し、ふたつの三つ組は、丁度一方に含まれるマスが存在する場合のみ区別します。
制約
- N は 2 以上 2000 以下の整数
- S_i は長さ N の
oとxからなる文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを整数として出力せよ。
入力例 1
3 ooo oxx xxo
出力例 1
4
以下の 4 つの三つ組が条件を満たします。
- (1,1),(1,2),(2,1)
- (1,1),(1,3),(2,1)
- (1,1),(1,3),(3,3)
- (1,2),(1,3),(3,3)
入力例 2
4 oxxx xoxx xxox xxxo
出力例 2
0
入力例 3
15 xooxxooooxxxoox oxxoxoxxxoxoxxo oxxoxoxxxoxoxxx ooooxooooxxoxxx oxxoxoxxxoxoxxx oxxoxoxxxoxoxxo oxxoxooooxxxoox xxxxxxxxxxxxxxx xooxxxooxxxooox oxxoxoxxoxoxxxo xxxoxxxxoxoxxoo xooxxxooxxoxoxo xxxoxxxxoxooxxo oxxoxoxxoxoxxxo xooxxxooxxxooox
出力例 3
2960
Score : 400 points
Problem Statement
You are given an N \times N grid. Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.
The states of the cells are given by N strings of length N, S_1, S_2, \dots, S_N, in the following format:
- If the j-th character of S_i is
o, there is anowritten in cell (i,j). - If the j-th character of S_i is
x, there is anxwritten in cell (i,j).
Find the number of triples of cells that satisfy all of the following conditions:
- The three cells in the triple are distinct.
- All three cells have an
owritten in them. - Exactly two of the cells are in the same row.
- Exactly two of the cells are in the same column.
Here, two triples are considered different if and only if some cell is contained in exactly one of the triples.
Constraints
- N is an integer between 2 and 2000, inclusive.
- S_i is a string of length N consisting of
oandx.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the answer as an integer.
Sample Input 1
3 ooo oxx xxo
Sample Output 1
4
The following four triples satisfy the conditions:
- (1,1),(1,2),(2,1)
- (1,1),(1,3),(2,1)
- (1,1),(1,3),(3,3)
- (1,2),(1,3),(3,3)
Sample Input 2
4 oxxx xoxx xxox xxxo
Sample Output 2
0
Sample Input 3
15 xooxxooooxxxoox oxxoxoxxxoxoxxo oxxoxoxxxoxoxxx ooooxooooxxoxxx oxxoxoxxxoxoxxx oxxoxoxxxoxoxxo oxxoxooooxxxoox xxxxxxxxxxxxxxx xooxxxooxxxooox oxxoxoxxoxoxxxo xxxoxxxxoxoxxoo xooxxxooxxoxoxo xxxoxxxxoxooxxo oxxoxoxxoxoxxxo xooxxxooxxxooox
Sample Output 3
2960