A - Jogging

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君と青木君はジョギングをすることにしました。
高橋君は「A 秒間秒速 B メートルで歩き、C 秒間休む」ことを繰り返します。
青木君は「D 秒間秒速 E メートルで歩き、F 秒間休む」ことを繰り返します。
二人が同時にジョギングを始めてから X 秒後、高橋君と青木君のうちどちらが長い距離を進んでいますか？

制約

  • 1 \leq A, B, C, D, E, F, X \leq 100
  • 入力は全て整数

入力

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

A B C D E F X

出力

二人が同時にジョギングを始めてから X 秒後時点で、高橋君の方が青木君よりも長い距離を進んでいるならば Takahashi、青木君の方が高橋君よりも長い距離を進んでいるならば Aoki、二人が同じ距離を進んでいるならば Draw と出力せよ。

入力例 1

4 3 3 6 2 5 10

出力例 1

Takahashi

二人はジョギングを始めてから 10 秒間の間、以下のように行動します。

  • 高橋君は 4 秒間歩き、3 秒間休んだ後、再び 3 秒間歩く。合計 (4 + 3) \times 3 = 21 メートル歩く。
  • 青木君は 6 秒間歩き、4 秒間休む。合計 6 \times 2 = 12 メートル歩く。

高橋君の方が長い距離を進んでいるので、Takahashi と出力します。

入力例 2

3 1 4 1 5 9 2

出力例 2

Aoki

入力例 3

1 1 1 1 1 1 1

出力例 3

Draw

Score : 100 points

Problem Statement

Takahashi and Aoki decided to jog.
Takahashi repeats the following: "walk at B meters a second for A seconds and take a rest for C seconds."
Aoki repeats the following: "walk at E meters a second for D seconds and take a rest for F seconds."
When X seconds have passed since they simultaneously started to jog, which of Takahashi and Aoki goes ahead?

Constraints

  • 1 \leq A, B, C, D, E, F, X \leq 100
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D E F X

Output

When X seconds have passed since they simultaneously started to jog, if Takahashi goes ahead of Aoki, print Takahashi; if Aoki goes ahead of Takahashi, print Aoki; if they have advanced the same distance, print Draw.

Sample Input 1

4 3 3 6 2 5 10

Sample Output 1

Takahashi

During the first 10 seconds after they started to jog, they move as follows.

  • Takahashi walks for 4 seconds, takes a rest for 3 seconds, and walks again for 3 seconds. As a result, he advances a total of (4 + 3) \times 3 = 21 meters.
  • Aoki walks for 6 seconds and takes a rest for 4 seconds. As a result, he advances a total of 6 \times 2 = 12 meters.

Since Takahashi goes ahead, Takahashi should be printed.

Sample Input 2

3 1 4 1 5 9 2

Sample Output 2

Aoki

Sample Input 3

1 1 1 1 1 1 1

Sample Output 3

Draw
B - Christmas Present

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

野球少年の高橋君は今年とても良い子にしていたので、サンタさんはバットかグローブのうち値段が高い方を高橋君にプレゼントすることにしました。

バットの値段が B 円、グローブの値段が G 円 (B\neq G) のとき、サンタさんが高橋君にプレゼントするのはどちらですか？

制約

  • B,G は 1 以上 1000 以下の相異なる整数

入力

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

B G

出力

サンタさんが高橋君にプレゼントするのがバットであるとき Bat を、グローブであるとき Glove を出力せよ。

入力例 1

300 100

出力例 1

Bat

バットの方がグローブより値段が高いので、サンタさんは高橋君にバットをプレゼントします。

入力例 2

334 343

出力例 2

Glove

グローブの方がバットより値段が高いので、サンタさんは高橋君にグローブをプレゼントします。

Score : 100 points

Problem Statement

Takahashi, a young baseball enthusiast, has been a very good boy this year, so Santa has decided to give him a bat or a glove, whichever is more expensive.

If a bat costs B yen and a glove costs G yen (B\neq G), which one will Santa give to Takahashi?

Constraints

  • B and G are different integers between 1 and 1000, inclusive.

Input

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

B G

Output

If Santa gives Takahashi a bat, print Bat; if Santa gives him a glove, print Glove.

Sample Input 1

300 100

Sample Output 1

Bat

The bat is more expensive than the glove, so Santa will give Takahashi the bat.

Sample Input 2

334 343

Sample Output 2

Glove

The glove is more expensive than the bat, so Santa will give Takahashi the glove.
C - Multi Test Cases

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

この問題は 1 つの入力ファイルに複数のテストケースが含まれる問題です。
はじめに整数 T が与えられます。T 個のテストケースについて次の問題を解いてください。

  • N 個の正整数 A_1, A_2, ..., A_N があります。このうち奇数は何個ありますか？

制約

  • 1 \leq T \leq 100
  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 10^9
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで \text{test}_i は i 番目のテストケースを意味する。

T
\text{test}_1
\text{test}_2
\vdots
\text{test}_T

各テストケースは以下の形式で与えられる。

N
A_1 A_2 \dots A_N

出力

T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。

入力例 1

4
3
1 2 3
2
20 23
10
6 10 4 1 5 9 8 6 5 1
1
1000000000

出力例 1

2
1
5
0

この入力は 4 個のテストケースが含まれています。

入力の 2 行目と 3 行目が 1 番目のテストケースに対応する入力で、N = 3, A_1 = 1, A_2 = 2, A_3 = 3 になります。
A_1, A_2, A_3 のうち奇数は全部で 2 個なので 1 行目に 2 を出力します。

Score : 200 points

Problem Statement

In this problem, an input file contains multiple test cases.
You are first given an integer T. Solve the following problem for T test cases.

  • We have N positive integers A_1, A_2, ..., A_N. How many of them are odd?

Constraints

  • 1 \leq T \leq 100
  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 10^9
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format, where \text{test}_i represents the i-th test case:

T
\text{test}_1
\text{test}_2
\vdots
\text{test}_T

Each test case is in the following format:

N
A_1 A_2 \dots A_N

Output

Print T lines. The i-th line should contain the answer for the i-th test case.

Sample Input 1

4
3
1 2 3
2
20 23
10
6 10 4 1 5 9 8 6 5 1
1
1000000000

Sample Output 1

2
1
5
0

This input contains four test cases.

The second and third lines correspond to the first test case, where N = 3, A_1 = 1, A_2 = 2, A_3 = 3.
We have two odd numbers in A_1, A_2, and A_3, so the first line should contain 2.
D - Caesar Cipher

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は英小文字からなる文字列 S を持っています。

高橋君は文字列 S に対して、下記の操作をちょうど 1 回行います。

  • まず、非負整数 K を選ぶ。
  • その後、S の各文字を K 個後ろの英小文字に変更する。

ただし、

  • a の 1 個後ろの英小文字は b であり、
  • b の 1 個後ろの英小文字は c であり、
  • c の 1 個後ろの英小文字は d であり、
  • \cdots
  • y の 1 個後ろの英小文字は z であり、
  • z の 1 個後ろの英小文字は a です。

例えば、b の 4 個後ろの英小文字は f であり、y の 3 個後ろの英小文字は b です。

文字列 T が与えられます。 高橋君が上記の操作によって S を T に一致させることができるかを判定してください。

制約

  • S と T はそれぞれ英小文字からなる長さ 1 以上 10^5 以下の文字列
  • S の長さと T の長さは等しい

入力

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

S
T

出力

高橋君が S を T に一致させることができる場合は Yes と出力し、 できない場合は No と出力せよ。

入力例 1

abc
ijk

出力例 1

Yes

高橋君が K=8 を選ぶと、

  • a は 8 個後ろの i に
  • b は 8 個後ろの j に
  • c は 8 個後ろの k に

それぞれ変更され、S と T が一致します。
高橋君が S を T に一致させることができるため Yes と出力します。

入力例 2

z
a

出力例 2

Yes

高橋君が K=1 を選ぶと S と T が一致します。
z の 1 個後ろの英小文字は a であることに注意してください。

入力例 3

ppq
qqp

出力例 3

No

高橋君は非負整数 K をどのように選んでも S を T に一致させることができません。 よって、No と出力します。

入力例 4

atcoder
atcoder

出力例 4

Yes

高橋君が K=0 を選ぶと S と T が一致します。

Score : 200 points

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

  • First, choose a non-negative integer K.
  • Then, shift each character of S to the right by K (see below).

Here,

  • a shifted to the right by 1 is b;
  • b shifted to the right by 1 is c;
  • c shifted to the right by 1 is d;
  • \cdots
  • y shifted to the right by 1 is z;
  • z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

  • Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
  • The lengths of S and T are equal.

Input

Input is given from Standard Input in the following format:

S
T

Output

If Takahashi can make S equal T, print Yes; if not, print No.

Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

  • a is shifted to the right by 8 and becomes i,
  • b is shifted to the right by 8 and becomes j,
  • c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.

Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.

Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.

Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

E - Swiss-System Tournament

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

1 から 2N の番号がついた 2N 人でじゃんけん大会をします。

大会は M ラウンドからなり、各ラウンドは、全ての人が 1 度ずつ参加するような 1 対 1 の N 試合からなります。

i=0,1,\ldots,M について、i ラウンド目の終了時点での順位を次のように決めます。

  • i ラウンド目までの勝数が多い方が上位
  • i ラウンド目までの勝数が同じときは、番号が小さい方が上位

また、i=1,\ldots,M について、i ラウンド目の各試合の組み合わせを次のように決めます。

  • 各 k=1,2,\ldots,N について、i-1 ラウンド目終了時点の順位が 2k-1 位の人と 2k 位の人が試合をする

各試合では、対戦する 2 人がそれぞれ 1 度だけ手を出し、勝ち・負け・引き分けのいずれかの結果が発生します。

未来予知ができる高橋君は、人 i が j ラウンド目の試合で出す手が A_{i,j} であることを知っています。
A_{i,j} は G, C, P のいずれかであり、それぞれグー、チョキ、パーを表します。

M ラウンド目終了時点の順位を求めてください。

じゃんけんのルール じゃんけんの結果は、2 人の出した手に応じて次のように決まります。
  • 一方がグーで他方がチョキのとき、グーを出した人が勝ち、チョキを出した人は負け
  • 一方がチョキで他方がパーのとき、チョキを出した人が勝ち、パーを出した人は負け
  • 一方がパーで他方がグーのとき、パーを出した人が勝ち、グーを出した人は負け
  • 両者が同じ手を出したとき、引き分け

制約

  • 1 \leq N \leq 50
  • 1 \leq M \leq 100
  • A_{i,j} は G, C, P のいずれか

入力

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

N M
A_{1,1}A_{1,2}\ldots A_{1,M}
A_{2,1}A_{2,2}\ldots A_{2,M}
\vdots
A_{2N,1}A_{2N,2}\ldots A_{2N,M}

出力

2N 行出力せよ。

i 行目には、M ラウンド目終了時点での順位が i 位である人の番号を出力せよ。

入力例 1

2 3
GCP
PPP
CCC
PPC

出力例 1

3
1
2
4

1 ラウンド目では人 1 と 2、3 と 4 がそれぞれ試合をし、前者の試合は人 2 が、後者の試合は人 3 が勝ちます。
2 ラウンド目では人 2 と 3、1 と 4 がそれぞれ試合をし、前者の試合は人 3 が、後者の試合は人 1 が勝ちます。
3 ラウンド目では人 3 と 1、2 と 4 がそれぞれ試合をし、前者の試合は人 3 が、後者の試合は人 4 が勝ちます。
よって最終的な順位は、上位から順に人 3,1,2,4 となります。

入力例 2

2 2
GC
PG
CG
PP

出力例 2

1
2
3
4

1 ラウンド目では人 1 と 2、3 と 4 がそれぞれ試合をし、前者の試合は人 2 が、後者の試合は人 3 が勝ちます。
2 ラウンド目では人 2 と 3、1 と 4 がそれぞれ試合をし、前者の試合は引き分け、後者の試合は人 1 が勝ちます。
よって最終的な順位は、上位から順に人 1,2,3,4 となります。

Score : 300 points

Problem Statement

2N players, with ID numbers 1 through 2N, will participate in a rock-scissors-paper contest.

The contest has M rounds. Each round has N one-on-one matches, where each player plays in one of them.

For each i=0, 1, \ldots, M, the players' ranks at the end of the i-th round are determined as follows.

  • A player with more wins in the first i rounds ranks higher.
  • Ties are broken by ID numbers: a player with a smaller ID number ranks higher.

Additionally, for each i=1, \ldots, M, the matches in the i-th round are arranged as follows.

  • For each k=1, 2, \ldots, N, a match is played between the players who rank (2k-1)-th and 2k-th at the end of the (i-1)-th round.

In each match, the two players play a hand just once, resulting in one player's win and the other's loss, or a draw.

Takahashi, who can foresee the future, knows that Player i will play A_{i, j} in their match in the j-th round, where A_{i,j} is G, C, or P.
Here, G stands for rock, C stands for scissors, and P stands for paper. (These derive from Japanese.)

Find the players' ranks at the end of the M-th round.

Rules of rock-scissors-paper The result of a rock-scissors-paper match is determined as follows, based on the hands played by the two players.
  • If one player plays rock (G) and the other plays scissors (C), the player playing rock (G) wins.
  • If one player plays scissors (C) and the other plays paper (P), the player playing scissors (C) wins.
  • If one player plays paper (P) and the other plays rock (G), the player playing paper (P) wins.
  • If the players play the same hand, the match is drawn.

Constraints

  • 1 \leq N \leq 50
  • 1 \leq M \leq 100
  • A_{i,j} is G, C, or P.

Input

Input is given from Standard Input in the following format:

N M
A_{1,1}A_{1,2}\ldots A_{1,M}
A_{2,1}A_{2,2}\ldots A_{2,M}
\vdots
A_{2N,1}A_{2N,2}\ldots A_{2N,M}

Output

Print 2N lines.

The i-th line should contain the ID number of the player who ranks i-th at the end of the M-th round.

Sample Input 1

2 3
GCP
PPP
CCC
PPC

Sample Output 1

3
1
2
4

In the first round, matches are played between Players 1 and 2, and between Players 3 and 4. Player 2 wins the former, and Player 3 wins the latter.
In the second round, matches are played between Players 2 and 3, and between Players 1 and 4. Player 3 wins the former, and Player 1 wins the latter.
In the third round, matches are played between Players 3 and 1, and between Players 2 and 4. Player 3 wins the former, and Player 4 wins the latter.
Therefore, in the end, the players are ranked in the following order: 3,1,2,4, from highest to lowest.

Sample Input 2

2 2
GC
PG
CG
PP

Sample Output 2

1
2
3
4

In the first round, matches are played between Players 1 and 2, and between Players 3 and 4. Player 2 wins the former, and Player 3 wins the latter.
In the second round, matches are played between Players 2 and 3, and between Players 1 and 4. The former is drawn, and Player 1 wins the latter.
Therefore, in the end, the players are ranked in the following order: 1,2,3,4, from highest to lowest.