A - Scoreboard

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

チーム高橋とチーム青木が N 回の試合を行いました。 i 回め (1\leq i\leq N) の試合ではチーム高橋が X _ i 点、チーム青木が Y _ i 点を獲得しました。

N 回の試合で獲得した得点の合計がより多いチームの勝ちです。

どちらのチームが勝ったか出力してください。 ただし、獲得した得点の合計が等しい場合は引き分けとなります。

制約

  • 1\leq N\leq 100
  • 0\leq X _ i\leq 100\ (1\leq i\leq N)
  • 0\leq Y _ i\leq 100\ (1\leq i\leq N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
X _ 1 Y _ 1
X _ 2 Y _ 2
\vdots
X _ N Y _ N

出力

チーム高橋が勝った場合 Takahashi を、チーム青木が勝った場合 Aoki を、引き分けの場合 Draw を出力せよ。


入力例 1

4
10 2
10 1
10 2
3 2

出力例 1

Takahashi

4 回の試合で、チーム高橋は 33 点、チーム青木は 7 点を獲得しました。 チーム高橋が勝ったため、Takahashi を出力してください。


入力例 2

6
5 4
4 5
2 4
1 6
7 1
3 2

出力例 2

Draw

いずれのチームも 22 点を獲得しました。 引き分けなので、Draw を出力してください。


入力例 3

4
0 0
10 10
50 50
0 100

出力例 3

Aoki

一方もしくは両方のチームが、一試合のうちに 1 点も取れない場合もあります。

Score: 100 points

Problem Statement

Team Takahashi and Team Aoki played N matches. In the i-th match (1\leq i\leq N), Team Takahashi scored X _ i points, and Team Aoki scored Y _ i points.

The team with the higher total score from the N matches wins.

Print the winner. If the two teams have the same total score, it is a draw.

Constraints

  • 1\leq N\leq 100
  • 0\leq X _ i\leq 100\ (1\leq i\leq N)
  • 0\leq Y _ i\leq 100\ (1\leq i\leq N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
X _ 1 Y _ 1
X _ 2 Y _ 2
\vdots
X _ N Y _ N

Output

If Team Takahashi wins, print Takahashi; if Team Aoki wins, print Aoki; if it is a draw, print Draw.


Sample Input 1

4
10 2
10 1
10 2
3 2

Sample Output 1

Takahashi

In four matches, Team Takahashi scored 33 points, and Team Aoki scored 7 points. Team Takahashi wins, so print Takahashi.


Sample Input 2

6
5 4
4 5
2 4
1 6
7 1
3 2

Sample Output 2

Draw

Both teams scored 22 points. It is a draw, so print Draw.


Sample Input 3

4
0 0
10 10
50 50
0 100

Sample Output 3

Aoki

One or both teams may score no points in a match.

B - Shift

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。
あなたは次の操作をちょうど K 回行います。

  • A の先頭の要素を取り除き、A の末尾に 0 を挿入する。

操作を行った後の A の要素をすべて出力してください。

制約

  • 1 \leq N \leq 100
  • 1 \leq K \leq 100
  • 1 \leq A_i \leq 100
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \dots A_N

出力

操作を行った後の A の要素を空白区切りで 1 行に出力せよ。


入力例 1

3 2
2 7 8

出力例 1

8 0 0

操作を行う前は A = (2, 7, 8) です。
操作を 1 回行った時点では A = (7, 8, 0) です。
操作を 2 回行った時点では A = (8, 0, 0) です。
よって (8, 0, 0) が答えです。


入力例 2

3 4
9 9 9

出力例 2

0 0 0

入力例 3

9 5
1 2 3 4 5 6 7 8 9

出力例 3

6 7 8 9 0 0 0 0 0

Score : 100 points

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.
You perform the following operation exactly K times:

  • remove the initial element of A and append a 0 to the tail of A.

Print all the elements of A after the operations.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq K \leq 100
  • 1 \leq A_i \leq 100
  • All values in the input 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 elements of A after the operations in one line, separated by spaces.


Sample Input 1

3 2
2 7 8

Sample Output 1

8 0 0

Before the operations, A = (2, 7, 8).
After performing the operation once, A = (7, 8, 0).
After performing the operation twice, A = (8, 0, 0).
Thus, (8, 0, 0) is the answer.


Sample Input 2

3 4
9 9 9

Sample Output 2

0 0 0

Sample Input 3

9 5
1 2 3 4 5 6 7 8 9

Sample Output 3

6 7 8 9 0 0 0 0 0
C - Weak Password

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

4 桁の暗証番号 X_1X_2X_3X_4 が与えられます。 番号は先頭の桁が 0 であることもあり得ます。 暗証番号は以下のいずれかの条件をみたすとき弱い暗証番号と呼ばれます。

  • 4 桁とも同じ数字である。
  • 1\leq i\leq 3 をみたす任意の整数 i について、 X_{i+1} が、 X_i の次の数字である。 ただし、 0\leq j\leq 8 について j の次の数字は j+1 であり、 9 の次の数字は 0 である。

与えられた暗証番号が弱い暗証番号ならば Weak を、そうでないならば Strong を出力してください。

制約

  • 0 \leq X_1, X_2, X_3, X_4 \leq 9
  • X_1, X_2, X_3, X_4 は整数である。

入力

入力は以下の形式で標準入力から与えられる。

X_1X_2X_3X_4

出力

与えられた暗証番号が弱い暗証番号ならば Weak を、そうでないならば Strong を出力せよ。


入力例 1

7777

出力例 1

Weak

4 桁ともすべて 7 であるため、 1 つめの条件をみたしており、弱い暗証番号です。


入力例 2

0112

出力例 2

Strong

1 桁目と 2 桁目が異なっており、 3 桁目は 2 桁目の次の数字ではないため、どちらの条件もみたしていません。


入力例 3

9012

出力例 3

Weak

9 の次の数字が 0 であることに注意してください。

Score : 200 points

Problem Statement

You are given a 4-digit PIN: X_1X_2X_3X_4, which may begin with a 0. The PIN is said to be weak when it satisfies one of the following conditions:

  • All of the four digits are the same.
  • For each integer i such that 1\leq i\leq 3, X_{i+1} follows X_i. Here, j+1 follows j for each 0\leq j\leq 8, and 0 follows 9.

If the given PIN is weak, print Weak; otherwise, print Strong.

Constraints

  • 0 \leq X_1, X_2, X_3, X_4 \leq 9
  • X_1, X_2, X_3, and X_4 are integers.

Input

Input is given from Standard Input in the following format:

X_1X_2X_3X_4

Output

If the given PIN is weak, print Weak; otherwise, print Strong.


Sample Input 1

7777

Sample Output 1

Weak

All four digits are 7, satisfying the first condition, so this PIN is weak.


Sample Input 2

0112

Sample Output 2

Strong

The first and second digits differ, and the third digit does not follow the second digit, so neither condition is satisfied.


Sample Input 3

9012

Sample Output 3

Weak

Note that 0 follows 9.

D - TaK Code

Time Limit: 2 sec / Memory Limit: 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.

E - Adjacent Swaps

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 個のボールが左右一列に並んでいます。初め、左から i \, (1 \leq i \leq N) 番目のボールには整数 i が書かれています。

高橋君は Q 回の操作を行いました。 i \, (1 \leq i \leq Q) 回目に行われた操作は次のようなものです。

  • 整数 x_i が書かれているボールをその右隣のボールと入れ替える。ただし、整数 x_i が書かれているボールが元々右端にあった場合、代わりに左隣のボールと入れ替える。

操作後において左から i \, (1 \leq i \leq N) 番目のボールに書かれている整数を a_i とします。 a_1,\ldots,a_N を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq x_i \leq N
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
x_1
\vdots
x_Q

出力

a_1,\ldots,a_N を空白区切りで出力せよ。


入力例 1

5 5
1
2
3
4
5

出力例 1

1 2 3 5 4

操作は以下のように行われます。

  • 1 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 2,1,3,4,5 となる。
  • 2 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,4,5 となる。
  • 3 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,4,3,5 となる。
  • 4 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,4,5 となる。
  • 5 と書かれたボールは右端にあるので左隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,5,4 となる。

入力例 2

7 7
7
7
7
7
7
7
7

出力例 2

1 2 3 4 5 7 6

入力例 3

10 6
1
5
2
9
6
6

出力例 3

1 2 3 4 5 7 6 8 10 9

Score : 300 points

Problem Statement

N balls are lined up in a row from left to right. Initially, the i-th (1 \leq i \leq N) ball from the left has an integer i written on it.

Takahashi has performed Q operations. The i-th (1 \leq i \leq Q) operation was as follows.

  • Swap the ball with the integer x_i written on it with the next ball to the right. If the ball with the integer x_i written on it was originally the rightmost ball, swap it with the next ball to the left instead.

Let a_i be the integer written on the i-th (1 \leq i \leq N) ball after the operations. Find a_1,\ldots,a_N.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq x_i \leq N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
x_1
\vdots
x_Q

Output

Print a_1,\ldots,a_N, with spaces in between.


Sample Input 1

5 5
1
2
3
4
5

Sample Output 1

1 2 3 5 4

The operations are performed as follows.

  • Swap the ball with 1 written on it with the next ball to the right. Now, the balls have integers 2,1,3,4,5 written on them, from left to right.
  • Swap the ball with 2 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
  • Swap the ball with 3 written on it with the next ball to the right. Now, the balls have integers 1,2,4,3,5 written on them, from left to right.
  • Swap the ball with 4 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
  • Swap the ball with 5 written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers 1,2,3,5,4 written on them, from left to right.

Sample Input 2

7 7
7
7
7
7
7
7
7

Sample Output 2

1 2 3 4 5 7 6

Sample Input 3

10 6
1
5
2
9
6
6

Sample Output 3

1 2 3 4 5 7 6 8 10 9