実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
ある星では 1 年が D 日あり、7 日ごとにコンテストが開催されています。コンテストが日をまたいで開催されることはありません。
ある年の最初のコンテストは 1 年のうち F 日目に開催されました。その次の年の最初のコンテストは 1 年のうち何日目に開催されますか？
なお、この問題の制約のもとでは、次の年にコンテストが 1 回以上開催されることが保証されます。
制約
- 10 \leq D \leq 366
- 1 \leq F \leq 7
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
D F
出力
答えを出力せよ。
入力例 1
365 4
出力例 1
3
ある年の最初のコンテストの開催が 1 年のうち 4 日目だったとき、次の年の最初のコンテストの開催は 1 年のうち 3 日目になります。
入力例 2
10 5
出力例 2
2
Score : 100 points
Problem Statement
On a certain planet, a year has D days, and contests are held every 7 days. Contests never span across days.
The first contest of a certain year was held on the F-th day of the year. On what day of the next year will the first contest of the next year be held?
The constraints of this problem guarantee that at least one contest will be held in the next year.
Constraints
- 10 \leq D \leq 366
- 1 \leq F \leq 7
- All input values are integers.
Input
The input is given from Standard Input in the following format:
D F
Output
Print the integer N such that the next contest is held on the N-th day of the year.
Sample Input 1
365 4
Sample Output 1
3
If the first contest of a certain year was held on the 4th day of the year, the first contest of the next year will be held on the 3rd day of the year.
Sample Input 2
10 5
Sample Output 2
2
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
数直線があり、高橋君はこれを赤色と青色で次のように塗りました。
- X=L_1 から X=R_1 までをすべて赤色で塗る。
- X=L_2 から X=R_2 までをすべて青色で塗る。
数直線のうち、赤色と青色の両方で塗られている部分の長さを求めてください。
制約
- 0\leq L_1<R_1\leq 100
- 0\leq L_2<R_2\leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
L_1 R_1 L_2 R_2
出力
両方の色で塗られている部分の長さを整数で出力せよ。
入力例 1
0 3 1 5
出力例 1
2
X=0 から X=3 までが赤く、 X=1 から X=5 までが青く塗られています。
よって、両方の色で塗られている部分は X=1 から X=3 までであり、その長さは 2 となります。
入力例 2
0 1 4 5
出力例 2
0
両方の色で塗られている部分はありません。
入力例 3
0 3 3 7
出力例 3
0
赤色と青色で塗られている部分が接している場合でも、 両方の色で塗られている部分の長さは 0 となります。
Score : 100 points
Problem Statement
We have a number line. Takahashi painted some parts of this line, as follows:
- First, he painted the part from X=L_1 to X=R_1 red.
- Next, he painted the part from X=L_2 to X=R_2 blue.
Find the length of the part of the line painted both red and blue.
Constraints
- 0\leq L_1<R_1\leq 100
- 0\leq L_2<R_2\leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
L_1 R_1 L_2 R_2
Output
Print the length of the part of the line painted both red and blue, as an integer.
Sample Input 1
0 3 1 5
Sample Output 1
2
The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.
Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.
Sample Input 2
0 1 4 5
Sample Output 2
0
No part is painted both red and blue.
Sample Input 3
0 3 3 7
Sample Output 3
0
If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は歯が左右一列に N 本生えています。現在の高橋君の歯の状態はある文字列 S によって表されます。
S の i 文字目が O のとき、左から i 番目の歯が丈夫であることを表します。S の i 文字目が X のとき、左から i 番目の歯が虫歯にかかっていることを表します。丈夫である歯は虫歯にかかっていません。
高橋君はある連続する K 本の歯が丈夫であるとき、その K 本の歯を使ってイチゴを 1 個食べることができます。イチゴを食べると、その K 本の歯が虫歯にかかり丈夫でなくなります。
このとき、高橋君は最大で何個のイチゴを食べることができるか求めてください。
制約
- 1 \leq K \leq N \leq 100
- N,K は整数
- S は
OとXからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N K S
出力
答えを出力せよ。
入力例 1
7 3 OOXOOOO
出力例 1
1
左から 4 本目の歯から左から 6 本目の歯までの連続する 3 本の丈夫な歯を使ってイチゴを 1 個食べることができます。これ以降、イチゴを食べることができません。また、他にどのような方法でイチゴを食べても 1 個以下しか食べることができません。よって、1 を出力します。
入力例 2
12 2 OXXOOOXOOOOX
出力例 2
3
入力例 3
22 5 XXOOOOOOOOXXOOOOOXXXXX
出力例 3
2
Score : 200 points
Problem Statement
Takahashi has N teeth arranged in a single row from left to right. The current condition of his teeth is represented by a string S.
If the i-th character of S is O, it means that the i-th tooth from the left is healthy. If it is X, it means that the i-th tooth has a cavity. Healthy teeth do not have cavities.
When he has K consecutive healthy teeth, he can eat one strawberry using those K teeth. After eating a strawberry, those K teeth develop cavities and become unhealthy.
Find the maximum number of strawberries he can eat.
Constraints
- 1 \leq K \leq N \leq 100
- N and K are integers.
- S is a string of length N consisting of
OandX.
Input
The input is given from Standard Input in the following format:
N K S
Output
Print the answer.
Sample Input 1
7 3 OOXOOOO
Sample Output 1
1
He can eat one strawberry by using the three consecutive healthy teeth from the 4th to 6th tooth from the left. After this, he cannot eat any more strawberries. Besides, there is no way for him to eat more than one strawberry. Therefore, print 1.
Sample Input 2
12 2 OXXOOOXOOOOX
Sample Output 2
3
Sample Input 3
22 5 XXOOOOOOOOXXOOOOOXXXXX
Sample Output 3
2
実行時間制限: 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
配点 : 300 点
問題文
整数 N が与えられるので、以下の条件を全て満たす整数 X の個数を 998244353 で割った余りを求めてください。
- N 桁の正整数である。
- X の各桁を上の位から順に X_1,X_2,\dots,X_N とする。このとき以下の条件を全て満たす。
- 全ての整数 1 \le i \le N に対して、 1 \le X_i \le 9
- 全ての整数 1 \le i \le N-1 に対して、 |X_i-X_{i+1}| \le 1
制約
- N は整数
- 2 \le N \le 10^6
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
4
出力例 1
203
4 桁の整数として、例えば 1111,1234,7878,6545 が問題文中の条件を満たします。
入力例 2
2
出力例 2
25
入力例 3
1000000
出力例 3
248860093
998244353 で割った余りを求めることに注意してください。
Score : 300 points
Problem Statement
Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.
- X is an N-digit positive integer.
- Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
- 1 \le X_i \le 9 for all integers 1 \le i \le N;
- |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.
Constraints
- N is an integer.
- 2 \le N \le 10^6
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
4
Sample Output 1
203
Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.
Sample Input 2
2
Sample Output 2
25
Sample Input 3
1000000
Sample Output 3
248860093
Be sure to find the count modulo 998244353.