AtCoder Daily Training EASY 2025/04/09 18:00start

A - Raise Both Hands

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

配点 : 100 点

問題文

高橋君はたこ焼きを作ってすぬけ君に振る舞うことにしました。高橋君はすぬけ君に、たこ焼きを食べたいならば左手のみを挙げて、そうでないならば右手のみを挙げるよう指示しました。

すぬけ君が挙げた手の情報は整数 L, R によって与えられます。すぬけ君は L = 1 のとき、またそのときに限り左手を挙げており、R = 1 のとき、またそのときに限り右手を挙げています。すぬけ君は指示に従わず、両手を挙げることも手を挙げないこともあります。

すぬけ君が片方の手のみを挙げている場合、すぬけ君がたこ焼きを食べたいならば Yes を、そうでないならば No を出力してください。すぬけ君が両手を挙げているか、手を挙げていないときは Invalid と出力してください。

ただし、すぬけ君が片方の手のみを挙げている場合は必ず指示に従った行動を取っているものとします。

制約

L, R は 0 または 1

入力

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

L R

出力

問題文の指示に従って Yes, No, Invalid のいずれかを出力せよ。

入力例 1

1 0

出力例 1

Yes

すぬけ君はたこ焼きを食べたいので左手のみを挙げています。

入力例 2

1 1

出力例 2

Invalid

すぬけ君は両手を挙げています。

Score : 100 points

Problem Statement

Takahashi decided to make takoyaki (octopus balls) and serve it to Snuke. Takahashi instructed Snuke to raise only his left hand if he wants to eat takoyaki, and only his right hand otherwise.

You are given the information about which hand Snuke is raising as two integers L and R. He is raising his left hand if and only if L = 1, and raising his right hand if and only if R = 1. He might not follow the instructions and could raise both hands or not raise any hand at all.

If Snuke is raising only one hand, print Yes if he wants to eat takoyaki, and No if he does not. If he is raising both hands or not raising any hand, print Invalid.

Assume that if Snuke is raising only one hand, he is always following the instructions.

Constraints

Each of L and R is 0 or 1.

Input

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

L R

Output

Print Yes, No, or Invalid according to the instructions in the problem statement.

Sample Input 1

1 0

Sample Output 1

Yes

Snuke wants to eat takoyaki, so he is raising only his left hand.

Sample Input 2

1 1

Sample Output 2

Invalid

Snuke is raising both hands.

B - Growth Record

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

配点 : 100 点

問題文

高橋君は N 歳の誕生日を迎えました。この時の彼の身長は T cmです。
また、以下のことが分かっています。

高橋君は 0 歳の誕生日(生まれた当日)から X 歳の誕生日までの間、毎年身長が D cmずつ伸びた。より厳密に書くと、i=1,2,\ldots,X それぞれに対し、i-1 歳の誕生日から i 歳の誕生日までの間に身長が D cm伸びた。
高橋君は X 歳の誕生日から N 歳の誕生日までの間、身長が変化していない。

高橋君の M 歳の誕生日の時の身長が何cmだったかを求めてください。

制約

0 \leq M \lt N \leq 100
1 \leq X \leq N
1 \leq T \leq 200
1 \leq D \leq 100
高橋君の 0 歳の誕生日の時の身長は 1 cm以上である
入力はすべて整数

入力

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

N M X T D

出力

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

入力例 1

38 20 17 168 3

出力例 1

この例では、高橋君の 38 歳の誕生日の時の身長が 168 cmです。また、17 歳の誕生日から 38 歳の誕生日までの間、身長が変化していません。
このことから、20 歳の誕生日の時の身長は 168 cmだったと言え、これが答えになります。

入力例 2

1 0 1 3 2

出力例 2

この例において、高橋君は 0(=M) 歳の誕生日の時の身長が 1 cmで、1(=N) 歳の誕生日の時の身長が 3(=T) cmです。

入力例 3

100 10 100 180 1

出力例 3

Score : 100 points

Problem Statement

Takahashi had his N-th birthday, when he was T centimeters tall.
Additionally, we know the following facts:

In each year between Takahashi's birth (0-th birthday) and his X-th birthday, his height increased by D centimeters. More formally, for each i = 1, 2, \ldots, X, his height increased by D centimeters between his (i-1)-th birthday and his i-th birthday.
Between Takahashi's X-th birthday and his N-th birthday, his height did not change.

Find Takahashi's height on his M-th birthday, in centimeters.

Constraints

0 \leq M \lt N \leq 100
1 \leq X \leq N
1 \leq T \leq 200
1 \leq D \leq 100
Takahashi was at least 1 centimeter tall at his birth.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M X T D

Output

Print the answer as an integer.

Sample Input 1

38 20 17 168 3

Sample Output 1

In this sample, Takahashi was 168 centimeters tall on his 38-th birthday. Also, his height did not change between his 17-th birthday and 38-th birthday.
From these facts, we find that he was 168 centimeters tall on his 20-th birthday, so the answer is 168.

Sample Input 2

1 0 1 3 2

Sample Output 2

In this sample, Takahashi was 1 centimeter tall on his 0(=M)-th birthday and 3(=T) centimeters tall on his 1(=N)-st birthday.

Sample Input 3

100 10 100 180 1

Sample Output 3

C - Cat

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

配点 : 200 点

問題文

長さ N の文字列 S が与えられます。

S に連続して含まれる na を全て nya に置き換えて得られる文字列を答えてください。

制約

N は 1 以上 1000 以下の整数
S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。

入力例 1

4
naan

出力例 1

nyaan

naan に連続して含まれる na を全て nya に置き換えて得られる文字列は nyaan です。

入力例 2

4
near

出力例 2

near

S に na が連続して含まれないこともあります。

入力例 3

8
national

出力例 3

nyationyal

Score : 200 points

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

N is an integer between 1 and 1000, inclusive.
S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

Print the answer.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal

D - Tetrahedral Number

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

配点 : 150 点

問題文

整数 N が与えられます。

非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを辞書順で小さい方から順に全て出力してください。

非負整数の組の辞書順とは？

非負整数の組 (x,y,z) が (x',y',z') より辞書順で小さいとは、下記のいずれかが成り立つことを言います。

x < x' である
x=x' かつ y< y' である
x=x' かつ y=y' かつ z< z' である

制約

0 \leq N \leq 21
N は整数である

入力

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

出力

非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを、1 行に 1 組ずつ x,y,z を空白区切りで、辞書順で小さい方から順に全て出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

Score : 150 points

Problem Statement

You are given an integer N.

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order.

What is lexicographical order for non-negative integer triples?

A triple of non-negative integers (x,y,z) is said to be lexicographically smaller than (x',y',z') if and only if one of the following holds:

x < x';
x=x' and y< y';
x=x' and y=y' and z< z'.

Constraints

0 \leq N \leq 21
N is an integer.

Input

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

Output

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order, with x,y,z separated by spaces, one triple per line.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

E - Shortest Duplicate Subarray

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

配点 : 300 点

問題文

正整数 N と、長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

A の空でない連続部分列であって、同じ値を複数個含むようなものが存在するか判定してください。存在するならばそのようなもののうち最も短いものの長さを求めてください。

制約

1\leq N\leq 2\times 10^5
1\leq A_i\leq 10^6 (1\leq i\leq N)
入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N

出力

問題文中の条件を満たす連続部分列が存在しないならば -1 と出力せよ。存在するならば、そのようなもののうち最も短いものの長さを出力せよ。

入力例 1

5
3 9 5 3 1

出力例 1

(3,9,5,3) と (3,9,5,3,1) が条件を満たします。短いのは (3,9,5,3) で、その長さは 4 です。

入力例 2

4
2 5 3 1

出力例 2

-1

条件を満たす連続部分列は存在しません。

入力例 3

10
1 1 2 3 5 8 13 21 34 55

出力例 3

Score : 300 points

Problem Statement

You are given a positive integer N and an integer sequence A = (A_1,A_2,\dots,A_N) of length N.

Determine whether there exists a non-empty (contiguous) subarray of A that has a repeated value, occurring multiple times in A. If such a subarray exists, find the length of the shortest such subarray.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^6 \ (1 \leq i \leq N)
All input values are integers.

Input

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

N
A_1 A_2 \dots A_N

Output

If there is no (contiguous) subarray satisfying the condition in the problem statement, print -1. Otherwise, print the length of the shortest such subarray.

Sample Input 1

5
3 9 5 3 1

Sample Output 1

(3,9,5,3) and (3,9,5,3,1) satisfy the condition. The shorter one is (3,9,5,3), which has length 4.

Sample Input 2

4
2 5 3 1

Sample Output 2

-1

There is no subarray that satisfies the condition.

Sample Input 3

10
1 1 2 3 5 8 13 21 34 55