Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
1,2,\ldots,N の番号のついた N 人の人に合計 K 枚のカードを配ります。
人 A から始めて 人 A,A+1,A+2,\ldots,N,1,2,\ldots の順に 1 枚ずつカードを配るとき、最後のカードは誰に配られるでしょうか?
厳密には、人 x(1 \leq x < N) の次には人 x+1 にカードを配り、人 N の次には人 1 にカードを配ります。
制約
- 1 \leq N,K \leq 1000
- 1 \leq A \leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A
出力
最後のカードが配られた人の番号を出力せよ。
入力例 1
3 3 2
出力例 1
1
人 2、人 3、人 1 の順にカードを配ります。
入力例 2
1 100 1
出力例 2
1
入力例 3
3 14 2
出力例 3
3
Score : 100 points
Problem Statement
We will hand out a total of K cards to N people numbered 1, 2, \ldots, N.
Beginning with Person A, we will give the cards one by one to the people in this order: A, A+1, A+2, \ldots, N, 1, 2, \ldots. Who will get the last card?
Formally, after Person x(1 \leq x < N) gets a card, Person x+1 will get a card. After Person N gets a card, Person 1 gets a card.
Constraints
- 1 \leq N,K \leq 1000
- 1 \leq A \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A
Output
Print a number representing the person who will get the last card.
Sample Input 1
3 3 2
Sample Output 1
1
The cards are given to Person 2, 3, 1 in this order.
Sample Input 2
1 100 1
Sample Output 2
1
Sample Input 3
3 14 2
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 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
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋君は英小文字からなる文字列 S をキーボードで入力しようとしました。
高橋君は画面を見ずにキーボードだけを見てタイピングをしていました。
誤って別の英小文字を入力してしまったときにはその直後にバックスペースキーを押しましたが、バックスペースキーが壊れていたため誤って入力された文字は消去されず、実際に入力された文字列は文字列 T となりました。
また、英小文字以外のキーを誤って押してしまうことはありませんでした。
T のうち高橋君が誤って入力した文字でないものを正しく入力された文字であると定めます。
正しく入力された文字が T の何文字目であるか答えてください。
制約
- S, T は長さ 1 以上 2 \times 10^5 以下の英小文字からなる文字列
- T は問題文中の手続きにより得られる文字列
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
S の長さを |S| として、正しく入力された文字が A_1, A_2, \ldots, A_{|S|} 文字目であるとき A_1, A_2, \ldots, A_{|S|} の値をこの順に空白区切りで出力せよ。
ただし、出力は昇順になるようにせよ。すなわち、各 1 \leq i \leq |S| - 1 に対して A_i < A_{i + 1} を満たすようにせよ。
入力例 1
abc axbxyc
出力例 1
1 3 6
高橋君のタイピングの一連の流れは以下のようになります。
aを入力する。bを入力しようとするが、誤ってxを入力してしまう。- バックスペースキーを押すが、文字の削除は行われない。
bを入力する。cを入力しようとするが、誤ってxを入力してしまう。- バックスペースキーを押すが、文字の削除は行われない。
cを入力しようとするが、誤ってyを入力してしまう。- バックスペースキーを押すが、文字の削除は行われない。
cを入力する。
正しく入力された文字は 1, 3, 6 文字目です。
入力例 2
aaaa bbbbaaaa
出力例 2
5 6 7 8
入力例 3
atcoder atcoder
出力例 3
1 2 3 4 5 6 7
高橋君が誤った文字を入力することはありませんでした。
Score: 200 points
Problem Statement
Takahashi tried to type a string S consisting of lowercase English letters using a keyboard.
He was typing while looking only at the keyboard, not the screen.
Whenever he mistakenly typed a different lowercase English letter, he immediately pressed the backspace key. However, the backspace key was broken, so the mistakenly typed letter was not deleted, and the actual string typed was T.
He did not mistakenly press any keys other than those for lowercase English letters.
The characters in T that were not mistakenly typed are called correctly typed characters.
Determine the positions in T of the correctly typed characters.
Constraints
- S and T are strings of lowercase English letters with lengths between 1 and 2 \times 10^5, inclusive.
- T is a string obtained by the procedure described in the problem statement.
Input
The input is given from Standard Input in the following format:
S T
Output
Let |S| be the length of S. If the correctly typed characters are the A_1-th, A_2-th, \ldots, A_{|S|}-th characters of T, print the values of A_1, A_2, \ldots, A_{|S|} in this order, separated by spaces.
Ensure that the output is in ascending order. That is, A_i < A_{i + 1} should hold for each 1 \leq i \leq |S| - 1.
Sample Input 1
abc axbxyc
Sample Output 1
1 3 6
The sequence of Takahashi's typing is as follows:
- Type
a. - Try to type
bbut mistakenly typex. - Press the backspace key, but the character is not deleted.
- Type
b. - Try to type
cbut mistakenly typex. - Press the backspace key, but the character is not deleted.
- Try to type
cbut mistakenly typey. - Press the backspace key, but the character is not deleted.
- Type
c.
The correctly typed characters are the first, third, and sixth characters.
Sample Input 2
aaaa bbbbaaaa
Sample Output 2
5 6 7 8
Sample Input 3
atcoder atcoder
Sample Output 3
1 2 3 4 5 6 7
Takahashi did not mistakenly type any characters.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
縦 H マス \times 横 W マスのマス目があり、各マスに 1 つずつ英小文字が書き込まれています。 上から i 行目かつ左から j 列目のマスを (i,j) で表します。
マス目に書き込まれている英小文字は H 個の長さ W の文字列 S_1,S_2,\ldots, S_H によって与えられ、 S_i の j 文字目が、(i, j) に書き込まれた英小文字を表します。
マス目の中に、s, n, u, k, e が
この順に(縦・横・ななめのいずれかの方向に) 連続して並んでいる
場所がただ 1 つ存在します。
そのような場所を見つけ、そのマスの位置を出力の形式に従って出力してください。
ただし、s, n, u, k, e が
この順に(縦・横・ななめのいずれかの方向に) 連続して並んでいる場所とは、
5 つのマスの組 (A_1,A_2,A_3,A_4,A_5) であって、次をすべてみたすものをさします。
- A_1,A_2,A_3,A_4,A_5 に書き込まれた英小文字はそれぞれ
s,n,u,k,eである。 - 1\leq i\leq 4 について、A_i と A_{i+1} は頂点または辺を共有している。
- A_1,A_2,A_3,A_4,A_5 の中心はこの順に一直線上に等間隔で並んでいる。
制約
- 5\leq H\leq 100
- 5\leq W\leq 100
- H,W は整数
- S_i は英小文字のみからなる長さ W の文字列
- 与えられるマス目の中に条件をみたす場所がただ 1 つ存在する
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H
出力
次の形式にしたがって、5 行出力せよ。
条件をみたす場所のうち s, n, u, k, e が書かれたマスがそれぞれ (R_1,C_1), (R_2,C_2)\ldots,(R_5,C_5) であるとき、
i 行目には R_i と C_i をこの順に空白区切りで出力せよ。
すなわち、以下のように出力せよ。
R_1 C_1 R_2 C_2 \vdots R_5 C_5
以下の入力例も参考にせよ。
入力例 1
6 6 vgxgpu amkxks zhkbpp hykink esnuke zplvfj
出力例 1
5 2 5 3 5 4 5 5 5 6
この時、(A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6)) とすると、
それぞれのマスに書き込まれた英小文字は s, n, u, k, e であり、
1\leq i\leq 4 について、A_i と A_{i+1} は辺を共有しており、
各マスの中心は一直線上に存在するため、条件をみたしています。

入力例 2
5 5 ezzzz zkzzz ezuzs zzznz zzzzs
出力例 2
5 5 4 4 3 3 2 2 1 1
(A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1)) が条件をみたしています。
例えば、(A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1)) は、1,2 つめの条件をみたしていますが、
マスの中心が一直線上に存在しないため、3 つめの条件をみたしていません。
入力例 3
10 10 kseeusenuk usesenesnn kskekeeses nesnusnkkn snenuuenke kukknkeuss neunnennue sknuessuku nksneekknk neeeuknenk
出力例 3
9 3 8 3 7 3 6 3 5 3
Score : 250 points
Problem Statement
There is a grid with H horizontal rows and W vertical columns. Each cell has a lowercase English letter written on it. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left.
The letters written on the grid are represented by H strings S_1,S_2,\ldots, S_H, each of length W. The j-th letter of S_i represents the letter written on (i, j).
There is a unique set of
contiguous cells (going vertically, horizontally, or diagonally) in the grid
with s, n, u, k, and e written on them in this order.
Find the positions of such cells and print them in the format specified in the Output section.
A tuple of five cells (A_1,A_2,A_3,A_4,A_5) is said to form
a set of contiguous cells (going vertically, horizontally, or diagonally) with s, n, u, k, and e written on them in this order
if and only if all of the following conditions are satisfied.
- A_1,A_2,A_3,A_4 and A_5 have letters
s,n,u,k, andewritten on them, respectively. - For all 1\leq i\leq 4, cells A_i and A_{i+1} share a corner or a side.
- The centers of A_1,A_2,A_3,A_4, and A_5 are on a common line at regular intervals.
Constraints
- 5\leq H\leq 100
- 5\leq W\leq 100
- H and W are integers.
- S_i is a string of length W consisting of lowercase English letters.
- The given grid has a unique conforming set of cells.
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
Output
Print five lines in the following format.
Let (R_1,C_1), (R_2,C_2)\ldots,(R_5,C_5) be the cells in the sought set with s, n, u, k, and e written on them, respectively.
The i-th line should contain R_i and C_i in this order, separated by a space.
In other words, print them in the following format:
R_1 C_1 R_2 C_2 \vdots R_5 C_5
See also Sample Inputs and Outputs below.
Sample Input 1
6 6 vgxgpu amkxks zhkbpp hykink esnuke zplvfj
Sample Output 1
5 2 5 3 5 4 5 5 5 6
Tuple (A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6)) satisfies the conditions.
Indeed, the letters written on them are s, n, u, k, and e;
for all 1\leq i\leq 4, cells A_i and A_{i+1} share a side;
and the centers of the cells are on a common line.

Sample Input 2
5 5 ezzzz zkzzz ezuzs zzznz zzzzs
Sample Output 2
5 5 4 4 3 3 2 2 1 1
Tuple (A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1)) satisfies the conditions.
However, for example, (A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1)) violates the third condition because the centers of the cells are not on a common line, although it satisfies the first and second conditions.
Sample Input 3
10 10 kseeusenuk usesenesnn kskekeeses nesnusnkkn snenuuenke kukknkeuss neunnennue sknuessuku nksneekknk neeeuknenk
Sample Output 3
9 3 8 3 7 3 6 3 5 3
Time Limit: 2 sec / Memory Limit: 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