AtCoder Daily Training EASY 2024/11/19 15:30start

A - Jogging

実行時間制限: 2 sec / メモリ制限: 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

実行時間制限: 2 sec / メモリ制限: 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

実行時間制限: 2 sec / メモリ制限: 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

この入力は 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

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

実行時間制限: 2 sec / メモリ制限: 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

実行時間制限: 2 sec / メモリ制限: 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

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 ラウンド目では人 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

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

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.