AtCoder Daily Training EASY 2024/05/23 18:30start

A - Good morning

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ある日、高橋君は A 時 B 分ちょうどに、青木君は C 時 D 分 1 秒に起きました。
高橋君の起床時刻が青木君より早いならば Takahashi を、そうでないならば Aoki を出力してください。

制約

0 \leq A \leq 23
0 \leq B \leq 59
0 \leq C \leq 23
0 \leq D \leq 59
入力はすべて整数である。

入力

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

A B C D

出力

高橋君の起床時刻が青木君より早いならば Takahashi を、そうでないならば Aoki を出力せよ。

入力例 1

7 0 6 30

出力例 1

Aoki

高橋君は 7 時ちょうどに、青木君は 6 時 30 分 1 秒に起きました。青木君の起床時刻の方が早いため、Aoki を出力します。

入力例 2

7 30 7 30

出力例 2

Takahashi

高橋君は 7 時 30 分ちょうどに、青木君は 7 時 30 分 1 秒に起きました。高橋君の起床時刻の方が 1 秒だけ早いため、Takahashi を出力します。

入力例 3

0 0 23 59

出力例 3

Takahashi

ある日の 0 時 0 分ちょうどはその日の 0 時 1 分の 1 分前であり、その日の 23 時 59 分の 1 分後、すなわちいわゆる 24 時ちょうどのことではありません。よって、高橋君の起床時刻の方が早く、Takahashi を出力します。

Score : 100 points

Problem Statement

One day, Takahashi got up at exactly B minutes past A o'clock (in 24-hour clock), and Aoki got up at exactly D minutes and 1 second past C o'clock.
If Takahashi got up earlier than Aoki, print Takahashi; otherwise, print Aoki.

Constraints

0 \leq A \leq 23
0 \leq B \leq 59
0 \leq C \leq 23
0 \leq D \leq 59
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

If Takahashi got up earlier than Aoki, print Takahashi; otherwise, print Aoki.

Sample Input 1

7 0 6 30

Sample Output 1

Aoki

Takahashi got up at 7 sharp, and Aoki got up at 30 minutes and 1 second past 6 o'clock. Aoki was the first to get up, so Aoki should be printed.

Sample Input 2

7 30 7 30

Sample Output 2

Takahashi

Takahashi got up at exactly half past 7, and Aoki got up at 30 minutes and 1 second past 7 o'clock. Just by one second, Takahashi was the first to get up, so Takahashi should be printed.

Sample Input 3

0 0 23 59

Sample Output 3

Takahashi

0:00 in a day is one minute before 0:01, not one minute past 23:59 ("24:00"). Thus, Takahashi was the first to get up, so Takahashi should be printed.

B - tcdr

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字からなる文字列 S が与えられます。
S から a, e, i, o, u をすべて取り除いて得られる文字列を出力してください。
なお、S は a, e, i, o, u 以外の文字を一つ以上含みます。

制約

S は英小文字からなる長さ 1 以上 100 以下の文字列
S は a, e, i, o, u 以外の文字を一つ以上含む

入力

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

出力

答えを出力せよ。

入力例 1

atcoder

出力例 1

tcdr

S = atcoder のとき、1, 4, 6 文字目を取り除いて tcdr を得ます。

入力例 2

xyz

出力例 2

xyz

入力例 3

aaaabbbbcccc

出力例 3

bbbbcccc

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters.
Remove all occurrences of a, e, i, o, u from S and print the resulting string.
S contains at least one character other than a, e, i, o, u.

Constraints

S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.
S contains at least one character other than a, e, i, o, u.

Input

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

Output

Print the answer.

Sample Input 1

atcoder

Sample Output 1

tcdr

For S = atcoder, remove the 1-st, 4-th, and 6-th characters to get tcdr.

Sample Input 2

xyz

Sample Output 2

xyz

Sample Input 3

aaaabbbbcccc

Sample Output 3

bbbbcccc

C - Foreign Exchange

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

1 から N までの番号がつけられた N 個の国があり、i = 1, 2, \ldots, N について、高橋君は国 i の通貨を A_i 単位持っています。

高橋君は、下記の操作を好きな回数（ 0 回でも良い）繰り返します。

まず、1 以上 N-1 以下の整数 i を選ぶ。
その後、国 i の通貨を S_i 単位以上持っているなら、下記の行動を 1 回行う。
- 国 i の通貨を S_i 単位だけ支払い、国 (i+1) の通貨を T_i 単位だけ獲得する。

最終的に高橋君が持っている国 N の通貨の単位数としてあり得る最大値を出力してください。

制約

入力される値はすべて整数
2 \leq N \leq 2 \times 10^5
0 \leq A_i \leq 10^9
1 \leq T_i \leq S_i \leq 10^9

入力

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

N
A_1 A_2 \ldots A_N
S_1 T_1
S_2 T_2
\vdots
S_{N-1} T_{N-1}

出力

答えを出力せよ。

入力例 1

出力例 1

以下の説明では、高橋君が持っている各国の通貨の単位数を、数列 A = (A_1, A_2, A_3, A_4) として表します。はじめ、A = (5, 7, 0, 3) です。

下記の通りに 4 回操作を行うことを考えます。

i = 2 を選び、国 2 の通貨 4 単位を支払って、国 3 の通貨 3 単位を獲得する。その結果、A = (5, 3, 3, 3) となる。
i = 1 を選び、国 1 の通貨 2 単位を支払って、国 2 の通貨 2 単位を獲得する。その結果、A = (3, 5, 3, 3) となる。
i = 2 を選び、国 2 の通貨 4 単位を支払って、国 3 の通貨 3 単位を獲得する。その結果、A = (3, 1, 6, 3) となる。
i = 3 を選び、国 3 の通貨 5 単位を支払って、国 4 の通貨 2 単位を獲得する。その結果、A = (3, 1, 1, 5) となる。

このとき、最終的に高橋君が持っている国 4 の通貨の単位数は 5 であり、これが考えられる最大値です。

入力例 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

出力例 2

Score: 150 points

Problem Statement

There are N countries numbered 1 to N. For each i = 1, 2, \ldots, N, Takahashi has A_i units of the currency of country i.

Takahashi can repeat the following operation any number of times, possibly zero:

First, choose an integer i between 1 and N-1, inclusive.
Then, if Takahashi has at least S_i units of the currency of country i, he performs the following action once:
- Pay S_i units of the currency of country i and gain T_i units of the currency of country (i+1).

Print the maximum possible number of units of the currency of country N that Takahashi could have in the end.

Constraints

All input values are integers.
2 \leq N \leq 2 \times 10^5
0 \leq A_i \leq 10^9
1 \leq T_i \leq S_i \leq 10^9

Input

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

N
A_1 A_2 \ldots A_N
S_1 T_1
S_2 T_2
\vdots
S_{N-1} T_{N-1}

Output

Print the answer.

Sample Input 1

Sample Output 1

In the following explanation, let the sequence A = (A_1, A_2, A_3, A_4) represent the numbers of units of the currencies of the countries Takahashi has. Initially, A = (5, 7, 0, 3).

Consider performing the operation four times as follows:

Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (5, 3, 3, 3).
Choose i = 1, pay two units of the currency of country 1, and gain two units of the currency of country 2. Now, A = (3, 5, 3, 3).
Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (3, 1, 6, 3).
Choose i = 3, pay five units of the currency of country 3, and gain two units of the currency of country 4. Now, A = (3, 1, 1, 5).

At this point, Takahashi has five units of the currency of country 4, which is the maximum possible number.

Sample Input 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

Sample Output 2

D - CTZ

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正の整数 X に対して、X を 2 進表記したときに末尾に連続する 0 の個数（の最大値）を \text{ctz}(X) で表します。
ただし、X を 2 進表記したとき末尾が 1 ならば \text{ctz}(X)=0 です。

正の整数 N が与えられるので、\text{ctz}(N) を出力してください。

制約

1\leq N\leq 10^9
N は整数

入力

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

出力

\text{ctz}(N) を出力せよ。

入力例 1

出力例 1

2024 を 2 進表記すると 11111101000 であり、末尾から 0 が 3 個連続しているため、\text{ctz}(2024)=3 です。
よって、3 を出力します。

入力例 2

出力例 2

18 を 2 進表記すると 10010 であるため、\text{ctz}(18)=1 です。
0 は末尾から連続する必要があることに注意してください。

入力例 3

出力例 3

Score: 200 points

Problem Statement

For a positive integer X, let \text{ctz}(X) be the (maximal) number of consecutive zeros at the end of the binary notation of X.
If the binary notation of X ends with a 1, then \text{ctz}(X)=0.

You are given a positive integer N. Print \text{ctz}(N).

Constraints

1\leq N\leq 10^9
N is an integer.

Input

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

Output

Print \text{ctz}(N).

Sample Input 1

Sample Output 1

2024 is 11111101000 in binary, with three consecutive 0s from the end, so \text{ctz}(2024)=3.
Thus, print 3.

Sample Input 2

Sample Output 2

18 is 10010 in binary, so \text{ctz}(18)=1.
Note that we count the trailing zeros.

Sample Input 3

Sample Output 3

E - One Time Swap

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

文字列 S が与えられます。次の操作を ちょうど 1 回 行った後の文字列としてあり得るものがいくつあるか求めてください。

S の長さを N とする。 1\leq i<j\leq N をみたす整数の組 (i,j) を選び、S の i 文字目と j 文字目を入れ替える。

なお、この問題の制約下で操作を必ず行うことができることが証明できます。

制約

S は英小文字からなる長さ 2 以上 10^6 以下の文字列

入力

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

出力

S に対して問題文中の操作をちょうど 1 回行った後の文字列としてあり得るものの個数を出力せよ。

入力例 1

abc

出力例 1

S の長さは 3 であるため、1\leq i<j\leq 3 をみたす整数の組 (i,j) としては、 (1,2), (1,3), (2,3) の 3 通りが考えられます。

S の 1 文字目と 2 文字目を入れ替えた時、S は bac となります。
S の 1 文字目と 3 文字目を入れ替えた時、S は cba となります。
S の 2 文字目と 3 文字目を入れ替えた時、S は acb となります。

よって、abc に対して操作を行った後の文字列としては、bac, cba, acb の 3 つがあり得るため、3 を出力します。

入力例 2

aaaaa

出力例 2

どの 2 つの文字を入れ替えても S は aaaaa のままです。よって、操作後の文字列としてあり得るものは 1 つです。

Points: 350 points

Problem Statement

You are given a string S. Find the number of strings that can result from performing the following operation exactly once.

Let N be the length of S. Choose a pair of integers (i,j) such that 1\leq i<j\leq N and swap the i-th and j-th characters of S.

It can be proved that you can always perform it under the constraints of this problem.

Constraints

S is a string of length between 2 and 10^6, inclusive, consisting of lowercase English letters.

Input

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

Output

Print the number of strings that can result from performing the operation in the problem statement exactly once on S.

Sample Input 1

abc

Sample Output 1

The length of S is 3, so 1\leq i<j\leq 3 is satisfied by three pairs of integers (i,j): (1,2), (1,3), and (2,3).

Swapping the 1-st and 2-nd characters of S results in S being bac.
Swapping the 1-st and 3-rd characters of S results in S being cba.
Swapping the 2-nd and 3-rd characters of S results in S being acb.

Therefore, the operation on abc results in one of the three strings: bac, cba, and acb, so print 3.

Sample Input 2

aaaaa

Sample Output 2

Swapping any two characters results in S remaining aaaaa. Thus, only one string can result from the operation.