AtCoder Daily Training MEDIUM 2025/03/26 20:00start

ログインしてください。

C - Misjudge the Time

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

配点 : 200 点

問題文

高橋君は置き時計を買いました。
この時計は、現在の時刻が 24 時制で \mathrm{AB} 時 \mathrm{CD} 分であるときに図 1 のように時刻を表します。
例えば図 2 では、時計は 7 時 58 分を示しています。

時刻の表示方法をより形式的に説明すると次のようになります。
現在の時刻が 24 時制で h 時 m 分であるとします。ここで 24 時制とは、時間を 0 以上 23 以下の整数で、分を 0 以上 59 以下の整数で表す時刻の表現方法を言います。
h の 10 の位を A, 1 の位を B, m の 10 の位を C, 1 の位を D とします。(ただし h, m が 1 桁である場合は先行ゼロを追加して考えます。)
このとき時計は左上に A を、左下に B を、右上に C を、右下に D を表示します。

高橋君は、次の条件を満たす時刻を 見間違えやすい時刻 と呼ぶことにしました。

時計の表示の右上と左下を入れ替えても、それに対応する 24 時制の時刻が存在する。

例えば図 3 は 20 時 13 分を示していますが、時計の表示の右上と左下を入れ替えると 21 時 3 分を意味する表示になります。よって 20 時 13 分は見間違えやすい時刻です。

今、時計は H 時 M 分を示しています。
(現時点も含めて)以降はじめて訪れる見間違えやすい時刻を 24 時制で答えてください。

制約

0 \leq H \leq 23
0 \leq M \leq 59
H, M は整数

入力

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

H M

出力

答えを h 時 m 分とする。ここで h, m は 0 \leq h \leq 23, 0 \leq m \leq 59 である必要がある。
このとき h, m を以下の形式で出力せよ。

h m

なお、h, m を 2 桁に揃えるために先行ゼロをつけた形式で出力しても正答と見なされる。

入力例 1

1 23

出力例 1

1 23

1 時 23 分は見間違えやすい時刻です。なぜならば、時計の表示の右上と左下を入れ替えると 2 時 13 分を意味する表示になるからです。
よって答えは 1 時 23 分です。
なお、01 23 のように先行ゼロをつけた形式で出力しても正答として扱われます。

入力例 2

19 57

出力例 2

20 0

19 時 57 分以降ではじめて訪れる見間違えやすい時刻は 20 時 0 分です。

入力例 3

20 40

出力例 3

21 0

24 時制では 24 時 0 分という表記は合法でないのに注意してください。

Score : 200 points

Problem Statement

Takahashi bought a table clock.
The clock shows the time as shown in Figure 1 at \mathrm{AB}:\mathrm{CD} in the 24-hour system.
For example, the clock in Figure 2 shows 7:58.

The format of the time is formally described as follows.
Suppose that the current time is m minutes past h in the 24-hour system. Here, the 24-hour system represents the hour by an integer between 0 and 23 (inclusive), and the minute by an integer between 0 and 59 (inclusive).
Let A be the tens digit of h, B be the ones digit of h, C be the tens digit of m, and D be the ones digit of m. (Here, if h has only one digit, we consider that it has a leading zero; the same applies to m.)
Then, the clock shows A in its top-left, B in its bottom-left, C in its top-right, and D in its bottom-right.

Takahashi has decided to call a time a confusing time if it satisfies the following condition:

after swapping the top-right and bottom-left digits on the clock, it still reads a valid time in the 24-hour system.

For example, the clock in Figure 3 shows 20:13. After swapping its top-right and bottom-left digits, it reads 21:03. Thus, 20:13 is a confusing time.

The clock now shows H:M.
Find the next confusing time (including now) in the 24-hour system.

Constraints

0 \leq H \leq 23
0 \leq M \leq 59
H and M are integers.

Input

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

H M

Output

Let h:m be the answer, where h and m must satisfy 0 \leq h \leq 23 and 0 \leq m \leq 59.
Print h and m in the following format:

h m

Your answer is considered correct even if h contains a leading zero to represent it as a 2-digit integer; the same applies to m.

Sample Input 1

1 23

Sample Output 1

1 23

1:23 is a confusing time because, after swapping its top-right and bottom-left digits on the clock, it reads 2:13.
Thus, the answer is 1:23.
Your answer is considered correct even if you print 01 23 with a leading zero.

Sample Input 2

19 57

Sample Output 2

20 0

The next confusing time after 19:57 is 20:00.

Sample Input 3

20 40

Sample Output 3

21 0

Note that 24:00 is an invalid notation in the 24-hour system.

D - Counting Arrays

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

配点 : 200 点

問題文

1 から N までの番号がついた N 個の数列が与えられます。
数列 i は、長さが L_i で j (1 \leq j \leq L_i) 番目の要素が a_{i,j} であるような数列です。

数列 i と数列 j は、 L_i = L_j かつすべての k (1 \leq k \leq L_i) に対して a_{i,k} = a_{j,k} が成り立つ時に同じであるとみなします。
同じ数列は 1 種類として数えるとき、数列 1 から数列 N の中に全部で何種類の数列がありますか？

制約

1 \leq N \leq 2 \times 10^5
1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
すべての数列の要素の個数の和、すなわち \sum_{i=1}^N L_i は 2 \times 10^5 を超えない。
入力はすべて整数である。

入力

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

N
L_1 a_{1,1} a_{1,2} \dots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \dots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \dots a_{N,L_N}

出力

数列の種類数を出力せよ。

入力例 1

出力例 1

入力例 1 で与えられている数列は以下の 4 個です。

数列 1 : (1, 2)
数列 2 : (1, 1)
数列 3 : (2, 1)
数列 4 : (1, 2)

このうち数列 1 と数列 4 は同じ数列で、それ以外は互いに異なる数列なので全部で 3 種類の数列があります。

入力例 2

出力例 2

入力例 2 で与えられている数列は以下の 5 個です。

数列 1 : (1)
数列 2 : (1)
数列 3 : (2)
数列 4 : (1, 1)
数列 5 : (1, 1, 1)

入力例 3

1
1 1

出力例 3

Score : 200 points

Problem Statement

You are given N sequences numbered 1 to N.
Sequence i has a length of L_i and its j-th element (1 \leq j \leq L_i) is a_{i,j}.

Sequence i and Sequence j are considered the same when L_i = L_j and a_{i,k} = a_{j,k} for every k (1 \leq k \leq L_i).
How many different sequences are there among Sequence 1 through Sequence N?

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
The total number of elements in the sequences, \sum_{i=1}^N L_i, does not exceed 2 \times 10^5.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
L_1 a_{1,1} a_{1,2} \dots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \dots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \dots a_{N,L_N}

Output

Print the number of different sequences.

Sample Input 1

Sample Output 1

Sample Input 1 contains four sequences:

Sequence 1 : (1, 2)
Sequence 2 : (1, 1)
Sequence 3 : (2, 1)
Sequence 4 : (1, 2)

Except that Sequence 1 and Sequence 4 are the same, these sequences are pairwise different, so we have three different sequences.

Sample Input 2

Sample Output 2

Sample Input 2 contains five sequences:

Sequence 1 : (1)
Sequence 2 : (1)
Sequence 3 : (2)
Sequence 4 : (1, 1)
Sequence 5 : (1, 1, 1)

Sample Input 3

1
1 1

Sample Output 3

E - Ideal Holidays

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

配点 : 350 点

問題文

AtCoder 王国の 1 週間は A+B 日からなり、1 日目から A 日目が休日で、A+1 日目から A+B 日目が平日です。

高橋くんは N 個の予定があり、i 番目の予定は今日から D_i 日後です。

高橋くんは今日が 1 週間の何日目かを忘れてしまいました。高橋くんの N 個の予定が全て休日である可能性があるかを判定してください。

制約

1\leq N\leq 2\times 10^5
1\leq A,B\leq 10^9
1\leq D_1<D_2<\ldots<D_N\leq 10^9

入力

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

N A B
D_1 D_2 \ldots D_N

出力

高橋くんの N 個の予定が全て休日である可能性がある場合は Yes を、そうでない場合は No を一行に出力せよ。

入力例 1

3 2 5
1 2 9

出力例 1

Yes

入力では 1 週間は 7 日からなり、1 日目から 2 日目が休日、3 日目から 7 日目が平日です。

今日が 1 週間の 7 日目だとします。このとき、1 日後は 1 週間の 1 日目、2 日後は 1 週間の 2 日目、9 日後は 1 週間の 2 日目となり、全ての予定が休日となります。そのため、高橋くんの N 個の予定が全て休日である可能性があります。

入力例 2

2 5 10
10 15

出力例 2

No

入力例 3

4 347 347
347 700 705 710

出力例 3

Yes

Score: 350 points

Problem Statement

In the Kingdom of AtCoder, a week consists of A+B days, with the first through A-th days being holidays and the (A+1)-th through (A+B)-th being weekdays.

Takahashi has N plans, and the i-th plan is scheduled D_i days later.

He has forgotten what day of the week it is today. Determine if it is possible for all of his N plans to be scheduled on holidays.

Constraints

1\leq N\leq 2\times 10^5
1\leq A,B\leq 10^9
1\leq D_1<D_2<\ldots<D_N\leq 10^9

Input

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

N A B
D_1 D_2 \ldots D_N

Output

Print Yes in a single line if it is possible for all of Takahashi's N plans to be scheduled on holidays, and No otherwise.

Sample Input 1

3 2 5
1 2 9

Sample Output 1

Yes

In this input, a week consists of seven days, with the first through second days being holidays and the third through seventh days being weekdays.

Let us assume today is the seventh day of the week. In this case, one day later would be the first day of the week, two days later would be the second day of the week, and nine days later would also be the second day of the week, making all plans scheduled on holidays. Therefore, it is possible for all of Takahashi's N plans to be scheduled on holidays.

Sample Input 2

2 5 10
10 15

Sample Output 2

No

Sample Input 3

4 347 347
347 700 705 710

Sample Output 3

Yes

F - 321-like Searcher

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

配点 : 300 点

問題文

以下の条件を満たす正整数 x を 321-like Number と呼びます。 この定義は A 問題と同様です。

x の各桁を上から見ると狭義単調減少になっている。
すなわち、x が d 桁の整数だとすると、 1 \le i < d を満たす全ての整数 i について以下の条件を満たす。
- ( x の上から i 桁目 ) > ( x の上から i+1 桁目 )

なお、 1 桁の正整数は必ず 321-like Number であることに注意してください。

例えば、 321,96410,1 は 321-like Number ですが、 123,2109,86411 は 321-like Number ではありません。

K 番目に小さい 321-like Number を求めてください。

制約

入力は全て整数
1 \le K
321-like Number は K 個以上存在する

入力

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

出力

K 番目に小さい 321-like Number を整数として出力せよ。

入力例 1

出力例 1

321-like Number は小さいものから順に (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) です。
このうち 15 番目に小さいものは 32 です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.

The digits of x are strictly decreasing from top to bottom.
In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
- (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

Find the K-th smallest 321-like Number.

Constraints

All input values are integers.
1 \le K
At least K 321-like Numbers exist.

Input

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

Output

Print the K-th smallest 321-like Number as an integer.

Sample Input 1

Sample Output 1

The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

G - Pedometer

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

配点 : 400 点

問題文

湖の周りに N 個の休憩所があります。
休憩所には時計回りに 1,2,\dots,N の番号が付いています。
休憩所 i から休憩所 i+1 まで時計回りに歩くには A_i 歩かかります ( 但し、休憩所 N+1 は休憩所 1 を指します ) 。
休憩所 s から休憩所 t ( s \neq t ) まで時計回りに歩くのにかかる最小の歩数は M の倍数でした。
(s,t) の組として考えられるものの数を求めてください。

制約

入力は全て整数
2 \le N \le 2 \times 10^5
1 \le A_i \le 10^9
1 \le M \le 10^6

入力

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

N M
A_1 A_2 \dots A_N

出力

答えを整数として出力せよ。

入力例 1

4 3
2 1 4 3

出力例 1

休憩所 1 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 2 歩で、これは 3 の倍数ではありません。
休憩所 1 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 3 歩で、これは 3 の倍数です。
休憩所 1 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 7 歩で、これは 3 の倍数ではありません。
休憩所 2 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 1 歩で、これは 3 の倍数ではありません。
休憩所 2 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 5 歩で、これは 3 の倍数ではありません。
休憩所 2 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 8 歩で、これは 3 の倍数ではありません。
休憩所 3 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 4 歩で、これは 3 の倍数ではありません。
休憩所 3 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 7 歩で、これは 3 の倍数ではありません。
休憩所 3 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 9 歩で、これは 3 の倍数です。
休憩所 4 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 3 歩で、これは 3 の倍数です。
休憩所 4 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 5 歩で、これは 3 の倍数ではありません。
休憩所 4 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 6 歩で、これは 3 の倍数です。

以上より、求めるべき (s,t) の組の数は 4 個です。

入力例 2

2 1000000
1 1

出力例 2

入力例 3

9 5
9 9 8 2 4 4 3 5 3

出力例 3

Score : 400 points

Problem Statement

There are N rest areas around a lake.
The rest areas are numbered 1, 2, ..., N in clockwise order.
It takes A_i steps to walk clockwise from rest area i to rest area i+1 (where rest area N+1 refers to rest area 1).
The minimum number of steps required to walk clockwise from rest area s to rest area t (s \neq t) is a multiple of M.
Find the number of possible pairs (s,t).

Constraints

All input values are integers
2 \le N \le 2 \times 10^5
1 \le A_i \le 10^9
1 \le M \le 10^6

Input

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

N M
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

4 3
2 1 4 3

Sample Output 1

The minimum number of steps to walk clockwise from rest area 1 to rest area 2 is 2, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 1 to rest area 3 is 3, which is a multiple of 3.
The minimum number of steps to walk clockwise from rest area 1 to rest area 4 is 7, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 2 to rest area 3 is 1, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 2 to rest area 4 is 5, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 2 to rest area 1 is 8, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 3 to rest area 4 is 4, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 3 to rest area 1 is 7, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 3 to rest area 2 is 9, which is a multiple of 3.
The minimum number of steps to walk clockwise from rest area 4 to rest area 1 is 3, which is a multiple of 3.
The minimum number of steps to walk clockwise from rest area 4 to rest area 2 is 5, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 4 to rest area 3 is 6, which is a multiple of 3.

Therefore, there are four possible pairs (s,t).

Sample Input 2

2 1000000
1 1

Sample Output 2

Sample Input 3

9 5
9 9 8 2 4 4 3 5 3