実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
英小文字からなる N 個の文字列 W_1,W_2,\dots,W_N が与えられます。
これらのうち一つ以上が and, not, that, the, you のいずれかと一致するなら Yes 、そうでないなら No と出力してください。
制約
- N は 1 以上 100 以下の整数
- 1 \le |W_i| \le 50 ( |W_i| は文字列 W_i の長さ )
- W_i は英小文字からなる
入力
入力は以下の形式で標準入力から与えられる。
N W_1 W_2 \dots W_N
出力
答えを出力せよ。
入力例 1
10 in that case you should print yes and not no
出力例 1
Yes
例えば W_4= you なので、 Yes と出力します。
入力例 2
10 in diesem fall sollten sie no und nicht yes ausgeben
出力例 2
No
文字列 W_i はいずれも、 and, not, that, the, you のいずれとも一致しません。
Score : 100 points
Problem Statement
You are given N strings W_1,W_2,\dots,W_N consisting of lowercase English letters.
If one or more of these strings equal and, not, that, the, or you, then print Yes; otherwise, print No.
Constraints
- N is an integer between 1 and 100, inclusive.
- 1 \le |W_i| \le 50 (|W_i| is the length of W_i.)
- W_i consists of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N W_1 W_2 \dots W_N
Output
Print the answer.
Sample Input 1
10 in that case you should print yes and not no
Sample Output 1
Yes
We have, for instance, W_4= you, so you should print Yes.
Sample Input 2
10 in diesem fall sollten sie no und nicht yes ausgeben
Sample Output 2
No
None of the strings W_i equals any of and, not, that, the, and you.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
整数 a, b, c が与えられます。b がこれらの整数の中央値であるかどうか判定してください。
制約
- 1 \leq a, b, c \leq 100
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
a b c
出力
b が与えられた整数の中央値であるならば Yes、そうでないならば No と出力せよ。
入力例 1
5 3 2
出力例 1
Yes
与えられた整数を小さい順に並べると 2, 3, 5 となり、b はこれらの整数の中央値です。
入力例 2
2 5 3
出力例 2
No
b は与えられた整数の中央値ではありません。
入力例 3
100 100 100
出力例 3
Yes
Score : 100 points
Problem Statement
Given integers a, b, and c, determine if b is the median of these integers.
Constraints
- 1 \leq a, b, c \leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
a b c
Output
If b is the median of the given integers, then print Yes; otherwise, print No.
Sample Input 1
5 3 2
Sample Output 1
Yes
The given integers are 2, 3, 5 when sorted in ascending order, of which b is the median.
Sample Input 2
2 5 3
Sample Output 2
No
b is not the median of the given integers.
Sample Input 3
100 100 100
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は 2 次元コード TaK Code を考案しました。以下の条件を全て満たすものが TaK Code です。
- 縦 9 マス 横 9 マスの領域である
- 左上及び右下の縦 3 マス 横 3 マスの領域に含まれる計 18 マスは全て黒である
- 左上及び右下の縦 3 マス 横 3 マスの領域に八方位で隣接する計 14 マスは全て白である
TaK Code を回転させることはできません。
縦 N マス、横 M マスのグリッドがあります。
グリッドの状態は N 個の長さ M の文字列 S_1,\ldots,S_N で与えられ、上から i 行目左から j 列目のマスは S_i の j 文字目が # のとき黒、. のとき白です。
グリッドに完全に含まれる縦 9 マス横 9 マスの領域で、TaK Code の条件を満たす箇所を全て求めてください。
制約
- 9 \leq N,M \leq 100
- N,M は整数である
- S_i は
.および#のみからなる長さ M の文字列である
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 \vdots S_N
出力
上から i 行目左から j 列目のマスを左上とする縦 9 マス 横 9 マスの領域が TaK Code の条件を満たす (i,j) の組全てを辞書順の昇順で 1 行に 1 組ずつ、i,j をこの順に空白区切りで出力せよ。
(i,j) の組の辞書順の昇順とは、i の昇順、i が等しい組は j の昇順にすることである。
入力例 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
出力例 1
1 1 1 10 7 7 10 2
TaK Code は以下のものです。# が黒マス、. が白マス、? が白黒どちらでもよいマスを表します。
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
入力で与えられたグリッドの上から 10 マス目左から 2 列目のマスを左上とする縦 9 マス 横 9 マスの領域は以下のようになっており、TaK Code の条件を満たします。
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
入力例 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
出力例 2
1 1
入力例 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
出力例 3
TaK Code の条件を満たす箇所が 1 つもないこともあります。
Score : 200 points
Problem Statement
Takahashi invented Tak Code, a two-dimensional code. A TaK Code satisfies all of the following conditions:
- It is a region consisting of nine horizontal rows and nine vertical columns.
- All the 18 cells in the top-left and bottom-right three-by-three regions are black.
- All the 14 cells that are adjacent (horizontally, vertically, or diagonally) to the top-left or bottom-right three-by-three region are white.
It is not allowed to rotate a TaK Code.
You are given a grid with N horizontal rows and M vertical columns.
The state of the grid is described by N strings, S_1,\ldots, and S_N, each of length M. The cell at the i-th row from the top and j-th column from the left is black if the j-th character of S_i is #, and white if it is ..
Find all the nine-by-nine regions, completely contained in the grid, that satisfy the conditions of a TaK Code.
Constraints
- 9 \leq N,M \leq 100
- N and M are integers.
- S_i is a string of length M consisting of
.and#.
Input
The input is given from Standard Input in the following format:
N M S_1 \vdots S_N
Output
For all pairs (i,j) such that the nine-by-nine region, whose top-left cell is at the i-th row from the top and j-th columns from the left, satisfies the conditions of a TaK Code, print a line containing i, a space, and j in this order.
The pairs must be sorted in lexicographical ascending order; that is, i must be in ascending order, and within the same i, j must be in ascending order.
Sample Input 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
Sample Output 1
1 1 1 10 7 7 10 2
A TaK Code looks like the following, where # is a black cell, . is a white cell, and ? can be either black or white.
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
In the grid given by the input, the nine-by-nine region, whose top-left cell is at the 10-th row from the top and 2-nd column from the left, satisfies the conditions of a TaK Code, as shown below.
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
Sample Input 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
Sample Output 2
1 1
Sample Input 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
Sample Output 3
There may be no region that satisfies the conditions of TaK Code.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
縦 H 行、横 W 列のマス目があり、各マスには 1 つの整数が書かれています。 上から i 行目、左から j 列目のマスに書かれている整数は A_{i, j} です。
マス目が下記の条件を満たすかどうかを判定してください。
1 \leq i_1 < i_2 \leq H および 1 \leq j_1 < j_2 \leq W を満たすすべての整数の組 (i_1, i_2, j_1, j_2) について、A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} が成り立つ。
制約
- 2 \leq H, W \leq 50
- 1 \leq A_{i, j} \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}
出力
マス目が問題文中の条件を満たす場合は Yes と出力し、条件を満たさない場合は No と出力せよ。
入力例 1
3 3 2 1 4 3 1 3 6 4 1
出力例 1
Yes
1 \leq i_1 < i_2 \leq H および 1 \leq j_1 < j_2 \leq W を満たす整数の組 (i_1, i_2, j_1, j_2) は 9 個存在し、それらすべてについて A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} が成り立ちます。例えば、
- (i_1, i_2, j_1, j_2) = (1, 2, 1, 2) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}
- (i_1, i_2, j_1, j_2) = (1, 2, 1, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
- (i_1, i_2, j_1, j_2) = (1, 2, 2, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
- (i_1, i_2, j_1, j_2) = (1, 3, 1, 2) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}
- (i_1, i_2, j_1, j_2) = (1, 3, 1, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
が成り立ちます。残りの (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3) についても同様に確認できます。
よって、Yes を出力します。
入力例 2
2 4 4 3 2 1 5 6 7 8
出力例 2
No
問題文中の条件を満たさないので、No を出力します。
例えば、(i_1, i_2, j_1, j_2) = (1, 2, 1, 4) について、A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} です。
Score : 200 points
Problem Statement
We have a grid with H horizontal rows and W vertical columns, where each square contains an integer. The integer written on the square at the i-th row from the top and j-th column from the left is A_{i, j}.
Determine whether the grid satisfies the condition below.
A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds for every quadruple of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W.
Constraints
- 2 \leq H, W \leq 50
- 1 \leq A_{i, j} \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}
Output
If the grid satisfies the condition in the Problem Statement, print Yes; otherwise, print No.
Sample Input 1
3 3 2 1 4 3 1 3 6 4 1
Sample Output 1
Yes
There are nine quadruples of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W. For all of them, A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds. Some examples follow.
- For (i_1, i_2, j_1, j_2) = (1, 2, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
- For (i_1, i_2, j_1, j_2) = (1, 2, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
- For (i_1, i_2, j_1, j_2) = (1, 2, 2, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
- For (i_1, i_2, j_1, j_2) = (1, 3, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
- For (i_1, i_2, j_1, j_2) = (1, 3, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
We can also see that the property holds for the other quadruples: (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3).
Thus, we should print Yes.
Sample Input 2
2 4 4 3 2 1 5 6 7 8
Sample Output 2
No
We should print No because the condition is not satisfied.
This is because, for example, we have A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} for (i_1, i_2, j_1, j_2) = (1, 2, 1, 4).
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
非負整数 N が与えられるので、以下の条件を満たす非負整数 x を昇順に全て出力してください。
- x を 2 進数として表記した時に 1 となる位の集合が、 N を 2 進数として表記した時に 1 となる位の集合の部分集合となる。
- すなわち、全ての非負整数 k について、「 x の 2^k の位が 1 ならば、 N の 2^k の位は 1 」が成り立つ。
制約
- N は整数
- 0 \le N < 2^{60}
- N を 2 進数として表記した時、 1 となる位は 15 個以下である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを 1 行に 1 つずつ、10 進法の整数として昇順に出力せよ。
入力例 1
11
出力例 1
0 1 2 3 8 9 10 11
N = 11_{(10)} を 2 進数で表記すると、 1011_{(2)} となります。
条件を満たす非負整数 x は以下の通りです。
- 0000_{(2)}=0_{(10)}
- 0001_{(2)}=1_{(10)}
- 0010_{(2)}=2_{(10)}
- 0011_{(2)}=3_{(10)}
- 1000_{(2)}=8_{(10)}
- 1001_{(2)}=9_{(10)}
- 1010_{(2)}=10_{(10)}
- 1011_{(2)}=11_{(10)}
入力例 2
0
出力例 2
0
入力例 3
576461302059761664
出力例 3
0 524288 549755813888 549756338176 576460752303423488 576460752303947776 576461302059237376 576461302059761664
入力は 32bit 符号付き整数に収まらない可能性があります。
Score : 300 points
Problem Statement
You are given a non-negative integer N. Print all non-negative integers x that satisfy the following condition in ascending order.
- The set of the digit positions containing 1 in the binary representation of x is a subset of the set of the digit positions containing 1 in the binary representation of N.
- That is, the following holds for every non-negative integer k: if the digit in the "2^ks" place of x is 1, the digit in the 2^ks place of N is 1.
Constraints
- N is an integer.
- 0 \le N < 2^{60}
- In the binary representation of N, at most 15 digit positions contain 1.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer as decimal integers in ascending order, each in its own line.
Sample Input 1
11
Sample Output 1
0 1 2 3 8 9 10 11
The binary representation of N = 11_{(10)} is 1011_{(2)}.
The non-negative integers x that satisfy the condition are:
- 0000_{(2)}=0_{(10)}
- 0001_{(2)}=1_{(10)}
- 0010_{(2)}=2_{(10)}
- 0011_{(2)}=3_{(10)}
- 1000_{(2)}=8_{(10)}
- 1001_{(2)}=9_{(10)}
- 1010_{(2)}=10_{(10)}
- 1011_{(2)}=11_{(10)}
Sample Input 2
0
Sample Output 2
0
Sample Input 3
576461302059761664
Sample Output 3
0 524288 549755813888 549756338176 576460752303423488 576460752303947776 576461302059237376 576461302059761664
The input may not fit into a 32-bit signed integer.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
AtCoder 王国では、これから N 日間のお祭りが開催されます。そのうち、A_1 日目、A_2 日目、\dots、A_M 日目の M 日では花火が上がります。ここで、お祭りの最終日には花火が上がることが保証されます。(つまり、A_M=N が保証されます。)
i=1,2,\dots,N に対して、以下の問題を解いてください。
- i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後か？ただし、i 日目に花火が上がる場合 0 日後とする。
制約
- 1 \le M \le N \le 2 \times 10^5
- 1 \le A_1 < A_2 < \dots < A_M = N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_M
出力
N 行出力せよ。
i(1 \le i \le N) 行目には、i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後かを整数として出力せよ。
入力例 1
3 2 2 3
出力例 1
1 0 0
AtCoder 王国ではお祭りを 3 日間開催し、2,3 日目に花火が上がります。
- 1 日目以降で初めて花火が上がるのは 2 日目なので、1 日目から数えて 1 日後です。
- 2 日目以降で初めて花火が上がるのは 2 日目なので、2 日目から数えて 0 日後です。
- 3 日目以降で初めて花火が上がるのは 3 日目なので、3 日目から数えて 0 日後です。
入力例 2
8 5 1 3 4 7 8
出力例 2
0 1 0 0 2 1 0 0
Score : 250 points
Problem Statement
The AtCoder Kingdom holds a festival for N days. On M of these days, namely on the A_1-th, A_2-th, \dots, A_M-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, A_M=N is guaranteed.)
For each i=1,2,\dots,N, solve the following problem.
- How many days later from the i-th day will fireworks be launched for the first time on or after the i-th day? If fireworks are launched on the i-th day, it is considered to be 0 days later.
Constraints
- 1 \le M \le N \le 2 \times 10^5
- 1 \le A_1 < A_2 < \dots < A_M = N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_M
Output
Print N lines.
The i-th line (1 \le i \le N) should contain an integer representing the number of days from the i-th day until fireworks are launched for the first time on or after the i-th day.
Sample Input 1
3 2 2 3
Sample Output 1
1 0 0
The kingdom holds a festival for 3 days, and fireworks are launched on the 2-nd and 3-rd days.
- From the 1-st day, the first time fireworks are launched is the 2-nd day of the festival, which is 1 day later.
- From the 2-nd day, the first time fireworks are launched is the 2-nd day of the festival, which is 0 days later.
- From the 3-rd day, the first time fireworks are launched is the 3-rd day of the festival, which is 0 days later.
Sample Input 2
8 5 1 3 4 7 8
Sample Output 2
0 1 0 0 2 1 0 0
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
湖の周りに N 個の休憩所があります。
休憩所には時計回りに 1,2,\dots,N の番号が付いています。
休憩所 i から休憩所 i+1 まで時計回りに歩くには A_i 歩かかります ( 但し、休憩所 N+1 は休憩所 1 を指します ) 。
休憩所 s から休憩所 t ( s \neq t ) まで時計回りに歩くのにかかる最小の歩数は M の倍数でした。
(s,t) の組として考えられるものの数を求めてください。
制約
- 入力は全て整数
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 1 \le M \le 10^6
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
4 3 2 1 4 3
出力例 1
4
- 休憩所 1 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 2 歩で、これは 3 の倍数ではありません。
- 休憩所 1 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 3 歩で、これは 3 の倍数です。
- 休憩所 1 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 7 歩で、これは 3 の倍数ではありません。
- 休憩所 2 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 1 歩で、これは 3 の倍数ではありません。
- 休憩所 2 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 5 歩で、これは 3 の倍数ではありません。
- 休憩所 2 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 8 歩で、これは 3 の倍数ではありません。
- 休憩所 3 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 4 歩で、これは 3 の倍数ではありません。
- 休憩所 3 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 7 歩で、これは 3 の倍数ではありません。
- 休憩所 3 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 9 歩で、これは 3 の倍数です。
- 休憩所 4 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 3 歩で、これは 3 の倍数です。
- 休憩所 4 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 5 歩で、これは 3 の倍数ではありません。
- 休憩所 4 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 6 歩で、これは 3 の倍数です。
以上より、求めるべき (s,t) の組の数は 4 個です。
入力例 2
2 1000000 1 1
出力例 2
0
入力例 3
9 5 9 9 8 2 4 4 3 5 3
出力例 3
11
Score : 400 points
Problem Statement
There are N rest areas around a lake.
The rest areas are numbered 1, 2, ..., N in clockwise order.
It takes A_i steps to walk clockwise from rest area i to rest area i+1 (where rest area N+1 refers to rest area 1).
The minimum number of steps required to walk clockwise from rest area s to rest area t (s \neq t) is a multiple of M.
Find the number of possible pairs (s,t).
Constraints
- All input values are integers
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 1 \le M \le 10^6
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
4 3 2 1 4 3
Sample Output 1
4
- The minimum number of steps to walk clockwise from rest area 1 to rest area 2 is 2, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 1 to rest area 3 is 3, which is a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 1 to rest area 4 is 7, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 2 to rest area 3 is 1, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 2 to rest area 4 is 5, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 2 to rest area 1 is 8, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 3 to rest area 4 is 4, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 3 to rest area 1 is 7, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 3 to rest area 2 is 9, which is a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 4 to rest area 1 is 3, which is a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 4 to rest area 2 is 5, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 4 to rest area 3 is 6, which is a multiple of 3.
Therefore, there are four possible pairs (s,t).
Sample Input 2
2 1000000 1 1
Sample Output 2
0
Sample Input 3
9 5 9 9 8 2 4 4 3 5 3
Sample Output 3
11
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
N 頂点 M 辺の単純無向グラフが与えられます。このグラフの頂点には 1 から N の番号が付けられており、辺には 1 から M の番号が付けられています。辺 i は頂点 U_i と頂点 V_i の間を結んでいます。
整数 K, S, T, X が与えられます。以下の条件を満たす数列 A = (A_0, A_1, \dots, A_K) は何通りありますか？
- A_i は 1 以上 N 以下の整数
- A_0 = S
- A_K = T
- 頂点 A_i と頂点 A_{i + 1} の間を直接結ぶ辺が存在する
- 数列 A の中に整数 X\ (X≠S,X≠T) は偶数回出現する ( 0 回でも良い)
ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割ったあまりを求めてください。
制約
- 入力は全て整数
- 2≤N≤2000
- 1≤M≤2000
- 1≤K≤2000
- 1≤S,T,X≤N
- X≠S
- X≠T
- 1≤U_i<V_i≤N
- i≠j ならば (U_i, V_i)≠(U_j, V_j)
入力
入力は以下の形式で標準入力から与えられる。
N M K S T X U_1 V_1 U_2 V_2 \vdots U_M V_M
出力
答えを 998244353 で割ったあまりを出力せよ。
入力例 1
4 4 4 1 3 2 1 2 2 3 3 4 1 4
出力例 1
4
- (1, 2, 1, 2, 3)
- (1, 2, 3, 2, 3)
- (1, 4, 1, 4, 3)
- (1, 4, 3, 4, 3)
の 4 個が条件を満たします。(1, 2, 3, 4, 3) や (1, 4, 1, 2, 3) は 2 が奇数回出現するため、条件を満たしません。
入力例 2
6 5 10 1 2 3 2 3 2 4 4 6 3 6 1 5
出力例 2
0
グラフは連結であるとは限りません。
入力例 3
10 15 20 4 4 6 2 6 2 7 5 7 4 5 2 4 3 7 1 7 1 4 2 9 5 10 1 3 7 8 7 9 1 6 1 2
出力例 3
952504739
998244353 で割ったあまりを求めてください。
Score : 500 points
Problem Statement
You are given a simple undirected graph with N vertices and M edges. The vertices are numbered from 1 through N, and the edges are numbered from 1 through M. Edge i connects Vertex U_i and Vertex V_i.
You are given integers K, S, T, and X. How many sequences A = (A_0, A_1, \dots, A_K) are there satisfying the following conditions?
- A_i is an integer between 1 and N (inclusive).
- A_0 = S
- A_K = T
- There is an edge that directly connects Vertex A_i and Vertex A_{i+1}.
- Integer X\ (X≠S,X≠T) appears even number of times (possibly zero) in sequence A.
Since the answer can be very large, find the answer modulo 998244353.
Constraints
- All values in input are integers.
- 2≤N≤2000
- 1≤M≤2000
- 1≤K≤2000
- 1≤S,T,X≤N
- X≠S
- X≠T
- 1≤U_i<V_i≤N
- If i ≠ j, then (U_i, V_i) ≠ (U_j, V_j).
Input
Input is given from Standard Input in the following format:
N M K S T X U_1 V_1 U_2 V_2 \vdots U_M V_M
Output
Print the answer modulo 998244353.
Sample Input 1
4 4 4 1 3 2 1 2 2 3 3 4 1 4
Sample Output 1
4
The following 4 sequences satisfy the conditions:
- (1, 2, 1, 2, 3)
- (1, 2, 3, 2, 3)
- (1, 4, 1, 4, 3)
- (1, 4, 3, 4, 3)
On the other hand, (1, 2, 3, 4, 3) and (1, 4, 1, 2, 3) do not, since there are odd number of occurrences of 2.
Sample Input 2
6 5 10 1 2 3 2 3 2 4 4 6 3 6 1 5
Sample Output 2
0
The graph is not necessarily connected.
Sample Input 3
10 15 20 4 4 6 2 6 2 7 5 7 4 5 2 4 3 7 1 7 1 4 2 9 5 10 1 3 7 8 7 9 1 6 1 2
Sample Output 3
952504739
Find the answer modulo 998244353.
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
2 以上の整数 N が与えられます。下記の条件を満たす 2 以上の整数 b の個数を出力してください。
- N を b 進法で表記したとき、すべての桁について「その桁が 0 または 1 である」が成り立つ。
T 個の独立なテストケースについて答えを求めてください。
なお、本問題の制約下において、上記の「条件を満たす 2 以上の整数 b の個数」は有限であることが証明できます。
制約
- 1 \leq T \leq 1000
- 2 \leq N \leq 10^{18}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。ここで、\mathrm{test}_i は i 番目のテストケースを表す。
T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T
各テストケースは以下の形式で与えられる。
N
出力
T 行出力せよ。 i = 1, 2, \ldots, T について、i 行目には i 番目のテストケースに対する答えを出力せよ。
入力例 1
3 12 2 36
出力例 1
4 1 5
1 番目のテストケースについて、問題文中の条件を満たす b は、b = 2, 3, 11, 12 の 4 つです。 実際、N = 12 を 2, 3, 11, 12 進法で表すと、それぞれ 1100, 110, 11, 10 となります。
Score : 500 points
Problem Statement
Given an integer N not less than 2, find the number of integers b not less than 2 such that:
- when N is written in base b, every digit is 0 or 1.
Find the answer for T independent test cases.
It can be proved that there is a finite number of desired integers b not less than 2 under the constraints of this problem.
Constraints
- 1 \leq T \leq 1000
- 2 \leq N \leq 10^{18}
- All values in the input are integers.
Input
The input is given from Standard Input in the following format, where \mathrm{test}_i denotes the i-th test case:
T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T
Each test case is given in the following format:
N
Output
Print T lines. For i = 1, 2, \ldots, T, the i-th line should contain the answer to the i-th test case.
Sample Input 1
3 12 2 36
Sample Output 1
4 1 5
For the first test case, four b's satisfy the condition in the problem statement: b = 2, 3, 11, 12. Indeed, when N=12 is written in base 2, 3, 11, and 12, it becomes 1100, 110, 11 and 10, respectively.