A - When?

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

AtCoder Beginner Contest は通常、日本標準時で 21 時ちょうどに始まり 100 分間にわたって行われます。

0 以上 100 以下の整数 K が与えられます。21 時ちょうどから K 分後の時刻を HH:MM の形式で出力してください。ただし、HH は 24 時間制での時間を、MM は分を表します。時間または分が 1 桁のときは、先頭に 0 を追加して 2 桁の整数として表してください。

制約

  • K は 0 以上 100 以下の整数

入力

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

K

出力

21 時ちょうどから K 分後の時刻を問題文中の形式に従って出力せよ。


入力例 1

63

出力例 1

22:03

21 時ちょうどから 63 分後の時刻は 22 時 3 分なので、22:03 と出力します。

以下のような出力は不正解となります。

  • 10:03
  • 22:3

入力例 2

45

出力例 2

21:45

入力例 3

100

出力例 3

22:40

Score : 100 points

Problem Statement

AtCoder Beginner Contest usually starts at 21:00 JST and lasts for 100 minutes.

You are given an integer K between 0 and 100 (inclusive). Print the time K minutes after 21:00 in the HH:MM format, where HH denotes the hour on the 24-hour clock and MM denotes the minute. If the hour or the minute has just one digit, append a 0 to the beginning to represent it as a 2-digit integer.

Constraints

  • K is an integer between 0 and 100 (inclusive).

Input

Input is given from Standard Input in the following format:

K

Output

Print the time K minutes after 21:00 in the format specified in the Problem Statement.


Sample Input 1

63

Sample Output 1

22:03

63 minutes after 21:00, it will be 22:03, so 22:03 should be printed.

The following outputs would be judged incorrect:

  • 10:03
  • 22:3

Sample Input 2

45

Sample Output 2

21:45

Sample Input 3

100

Sample Output 3

22:40
B - Balloon Trip

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

整数 W,B が与えられるので、以下の問題を解いてください。

高橋君の体重は W {\rm [kg]} です。 (単位が {\rm kg} であることに注意してください)
風船を n 個付けられた物体は、物体の質量が nB {\rm [g]} 未満 である時、またその時に限り、空に飛び立ちます。
高橋君を空に飛ばすためには、最低何個の風船を付ける必要がありますか?

制約

  • 1 \le W \le 100
  • 1 \le B \le 100
  • 入力される値は全て整数

入力

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

W B

出力

答えを出力せよ。


入力例 1

80 5

出力例 1

16001

高橋君の体重は 80 {\rm kg} = 80000 {\rm g} です。
高橋君に風船を 16001 個付けると、高橋君の質量は 16001 \times 5=80005 {\rm g} 未満であるため、空に飛び立ちます。
16000 個では不十分であることに注意してください。


入力例 2

70 6

出力例 2

11667

入力例 3

100 100

出力例 3

1001

Score : 100 points

Problem Statement

Given integers W and B, solve the following problem.

Takahashi's weight is W {\rm [kg]}. (Note that the unit is {\rm kg}.)
An object attached with n balloons will fly into the sky if and only if the mass of the object is strictly less than nB {\rm [g]}.
What is the minimum number of balloons needed to make Takahashi fly into the sky?

Constraints

  • 1 \le W \le 100
  • 1 \le B \le 100
  • All input values are integers.

Input

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

W B

Output

Output the answer.


Sample Input 1

80 5

Sample Output 1

16001

Takahashi's weight is 80 {\rm kg} = 80000 {\rm g}.
If he is attached with 16001 balloons, his mass is less than 16001 \times 5=80005 {\rm g}, so he will fly into the sky.
Note that 16000 balloons are not sufficient.


Sample Input 2

70 6

Sample Output 2

11667

Sample Input 3

100 100

Sample Output 3

1001
C - Grid Rotation

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 250 点

問題文

縦 N 行 横 N 列からなる 2 つのグリッド S,T があります。グリッドの上から i 行目、左から j 列目のマスをマス (i,j) と表します。

グリッド S,T の各マスは白または黒のいずれかに塗られています。S_{i,j} が . のとき S のマス (i,j) は白く、S_{i,j} が # のとき S のマス (i,j) は黒く塗られています。T についても同様です。

次の 2 種類の操作を好きな順序で好きな回数行うとき、グリッド S をグリッド T と一致させるために必要な操作回数の最小値を求めてください。

  • グリッド S のマスを 1 つ選び、色を変更する
  • グリッド S 全体を 90 度右に回転する

制約

  • 1\leq N \leq 100
  • N は整数
  • S_{i,j},T_{i,j} は . または #

入力

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

N
S_{1,1}S_{1,2}\dots S_{1,N}
\vdots
S_{N,1}S_{N,2}\dots S_{N,N}
T_{1,1}T_{1,2}\dots T_{1,N}
\vdots
T_{N,1}T_{N,2}\dots T_{N,N}

出力

答えを出力せよ。


入力例 1

4
###.
..#.
..#.
..#.
...#
...#
###.
....

出力例 1

2

下図のようにして 2 回の操作で S を T と一致させることができます。

図


入力例 2

13
.#..###..##..
#.#.#..#.#.#.
#.#.###..#...
###.#..#.#.#.
#.#.###..##..
.............
..#...#....#.
.##..#.#..##.
#.#..#.#.#.#.
####.#.#.####
..#..#.#...#.
..#...#....#.
.............
.............
.#....#...#..
.#...#.#..#..
####.#.#.####
.#.#.###..#.#
.##....#..##.
.#....#...#..
.............
..##..###.#.#
.#.#.#..#.###
.#.#..###.#.#
.#.#.#..#.#.#
..##..###..#.

出力例 2

5

Score : 250 points

Problem Statement

There are two grids S and T, each with N rows and N columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

Each cell of grids S and T is colored either white or black. Cell (i,j) of S is white if S_{i,j} is ., and black if S_{i,j} is #. The same applies to T.

You may perform the following two types of operations any number of times in any order. Find the minimum number of operations required to make grid S identical to grid T.

  • Choose one cell of grid S and change its color.
  • Rotate the entire grid S 90 degrees clockwise.

Constraints

  • 1 \le N \le 100
  • N is an integer.
  • Each of S_{i,j} and T_{i,j} is . or #.

Input

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

N
S_{1,1}S_{1,2}\dots S_{1,N}
\vdots
S_{N,1}S_{N,2}\dots S_{N,N}
T_{1,1}T_{1,2}\dots T_{1,N}
\vdots
T_{N,1}T_{N,2}\dots T_{N,N}

Output

Output the minimum number of operations required.


Sample Input 1

4
###.
..#.
..#.
..#.
...#
...#
###.
....

Sample Output 1

2

You can match S to T in two operations as shown below.

Figure


Sample Input 2

13
.#..###..##..
#.#.#..#.#.#.
#.#.###..#...
###.#..#.#.#.
#.#.###..##..
.............
..#...#....#.
.##..#.#..##.
#.#..#.#.#.#.
####.#.#.####
..#..#.#...#.
..#...#....#.
.............
.............
.#....#...#..
.#...#.#..#..
####.#.#.####
.#.#.###..#.#
.##....#..##.
.#....#...#..
.............
..##..###.#.#
.#.#.#..#.###
.#.#..###.#.#
.#.#.#..#.#.#
..##..###..#.

Sample Output 2

5
D - Trick Taking

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

プレイヤー 1 、プレイヤー 2 、\ldots 、プレイヤー N と番号がつけられた N 人のプレイヤーがカードゲームで対戦します。
各プレイヤーはカードを 1 枚場に出します。

各カードは色と値の 2 つの属性を持ち、どちらの属性も正整数で表されます。
i = 1, 2, \ldots, N について、プレイヤー i が場に出したカードの色は C_i であり、値は R_i です。 R_1, R_2, \ldots, R_N はすべて異なります。

N 人のプレイヤーの中から 1 人の勝者を下記の方法で決めます。

  • 色が T であるカードが 1 枚以上場に出された場合、色が T であるカードのうち値が最大のものを出したプレイヤーが勝者である。
  • 色が T であるカードが場に 1 枚も出されなかった場合、プレイヤー 1 が出したカードと同じ色のカードのうち値が最大のものを出したプレイヤーが勝者である。(プレイヤー 1 自身も勝者となり得ることに注意してください。)

勝者となるプレイヤーの番号を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 1 \leq C_i \leq 10^9
  • 1 \leq R_i \leq 10^9
  • i \neq j \implies R_i \neq R_j
  • 入力はすべて整数

入力

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

N T
C_1 C_2 \ldots C_N
R_1 R_2 \ldots R_N

出力

答えを出力せよ。


入力例 1

4 2
1 2 1 2
6 3 4 5

出力例 1

4

色が 2 であるカードが 1 枚以上場に出されています。 よって、色が 2 であるカードのうち値が最大の 5 のカードを出した、プレイヤー 4 が勝者です。


入力例 2

4 2
1 3 1 4
6 3 4 5

出力例 2

1

色が 2 であるカードが 1 枚も場に出されていません。 よって、プレイヤー 1 が出したカードの色と同じ色(すなわち色 1 )のカードのうち値が最大の 6 のカードを出した、プレイヤー 1 が勝者です。


入力例 3

2 1000000000
1000000000 1
1 1000000000

出力例 3

1

Score : 200 points

Problem Statement

N players with ID numbers 1, 2, \ldots, N are playing a card game.
Each player plays one card.

Each card has two parameters: color and rank, both of which are represented by positive integers.
For i = 1, 2, \ldots, N, the card played by player i has a color C_i and a rank R_i. All of R_1, R_2, \ldots, R_N are different.

Among the N players, one winner is decided as follows.

  • If one or more cards with the color T are played, the player who has played the card with the greatest rank among those cards is the winner.
  • If no card with the color T is played, the player who has played the card with the greatest rank among the cards with the color of the card played by player 1 is the winner. (Note that player 1 may win.)

Print the ID number of the winner.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 1 \leq C_i \leq 10^9
  • 1 \leq R_i \leq 10^9
  • i \neq j \implies R_i \neq R_j
  • All values in the input are integers.

Input

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

N T
C_1 C_2 \ldots C_N
R_1 R_2 \ldots R_N

Output

Print the answer.


Sample Input 1

4 2
1 2 1 2
6 3 4 5

Sample Output 1

4

Cards with the color 2 are played. Thus, the winner is player 4, who has played the card with the greatest rank, 5, among those cards.


Sample Input 2

4 2
1 3 1 4
6 3 4 5

Sample Output 2

1

No card with the color 2 is played. Thus, the winner is player 1, who has played the card with the greatest rank, 6, among the cards with the color of the card played by player 1 (color 1).


Sample Input 3

2 1000000000
1000000000 1
1 1000000000

Sample Output 3

1
E - Even Digits

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

非負整数 n が次の条件を満たすとき、n を 良い整数 と呼びます。

  • n を 10 進法で表したときに、偶数の数字 (0, 2, 4, 6, 8) のみが登場する。

例えば 0、68 および 2024 は良い整数です。

整数 N が与えられます。良い整数のうち小さい方から N 番目の整数を求めてください。

制約

  • 1 \leq N \leq 10^{12}
  • N は整数

入力

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

N

出力

小さい方から N 番目の良い整数を出力せよ。


入力例 1

8

出力例 1

24

良い整数を小さい方から順に並べると 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots となります。
小さい方から 8 番目の良い整数は 24 なので、これを出力します。


入力例 2

133

出力例 2

2024

入力例 3

31415926535

出力例 3

2006628868244228

Score: 300 points

Problem Statement

A non-negative integer n is called a good integer when it satisfies the following condition:

  • All digits in the decimal notation of n are even numbers (0, 2, 4, 6, and 8).

For example, 0, 68, and 2024 are good integers.

You are given an integer N. Find the N-th smallest good integer.

Constraints

  • 1 \leq N \leq 10^{12}
  • N is an integer.

Input

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

N

Output

Print the N-th smallest good integer.


Sample Input 1

8

Sample Output 1

24

The good integers in ascending order are 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots.
The eighth smallest is 24, which should be printed.


Sample Input 2

133

Sample Output 2

2024

Sample Input 3

31415926535

Sample Output 3

2006628868244228