AtCoder Daily Training EASY 2026/08/07 16:00start

A - Arithmetic Progression

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

初項が A、末項が B、公差が D であるような等差数列を出力してください。

なお、そのような等差数列が存在する入力のみが与えられます。

制約

1 \leq A \leq B \leq 100
1\leq D \leq 100
初項が A、末項が B、公差が D であるような等差数列が存在する
入力は全て整数

入力

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

A B D

出力

初項が A、末項が B、公差が D であるような等差数列の項を順に空白区切りで出力せよ。

入力例 1

3 9 2

出力例 1

3 5 7 9

初項が 3、末項が 9、公差が 2 であるような等差数列は (3,5,7,9) です。

入力例 2

10 10 1

出力例 2

初項が 10、末項が 10、公差が 1 であるような等差数列は (10) です。

Score: 100 points

Problem Statement

Print an arithmetic sequence with first term A, last term B, and common difference D.

You are only given inputs for which such an arithmetic sequence exists.

Constraints

1 \leq A \leq B \leq 100
1 \leq D \leq 100
There is an arithmetic sequence with first term A, last term B, and common difference D.
All input values are integers.

Input

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

A B D

Output

Print the terms of the arithmetic sequence with first term A, last term B, and common difference D, in order, separated by spaces.

Sample Input 1

3 9 2

Sample Output 1

3 5 7 9

The arithmetic sequence with first term 3, last term 9, and common difference 2 is (3,5,7,9).

Sample Input 2

10 10 1

Sample Output 2

The arithmetic sequence with first term 10, last term 10, and common difference 1 is (10).

B - Probably English

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字からなる N 個の文字列 W_1,W_2,\dots,W_N が与えられます。
これらのうち一つ以上が and, not, that, the, you のいずれかと一致するなら Yes 、そうでないなら No と出力してください。

制約

N は 1 以上 100 以下の整数
1 \le |W_i| \le 50 ( |W_i| は文字列 W_i の長さ )
W_i は英小文字からなる

入力

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

N
W_1 W_2 \dots W_N

出力

答えを出力せよ。

入力例 1

10
in that case you should print yes and not no

出力例 1

Yes

例えば W_4= you なので、 Yes と出力します。

入力例 2

10
in diesem fall sollten sie no und nicht yes ausgeben

出力例 2

No

文字列 W_i はいずれも、 and, not, that, the, you のいずれとも一致しません。

Score : 100 points

Problem Statement

You are given N strings W_1,W_2,\dots,W_N consisting of lowercase English letters.
If one or more of these strings equal and, not, that, the, or you, then print Yes; otherwise, print No.

Constraints

N is an integer between 1 and 100, inclusive.
1 \le |W_i| \le 50 (|W_i| is the length of W_i.)
W_i consists of lowercase English letters.

Input

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

N
W_1 W_2 \dots W_N

Output

Print the answer.

Sample Input 1

10
in that case you should print yes and not no

Sample Output 1

Yes

We have, for instance, W_4= you, so you should print Yes.

Sample Input 2

10
in diesem fall sollten sie no und nicht yes ausgeben

Sample Output 2

No

None of the strings W_i equals any of and, not, that, the, and you.

C - Sum of Geometric Series

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 N, M が与えられます。

X = \displaystyle\sum_{i = 0}^{M} N^i とします。X \leq 10^9 のときは X の値を、X > 10^9 のときは文字列 inf を出力してください。

制約

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

入力

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

N M

出力

問題文の指示に従って X の値あるいは inf を出力せよ。

入力例 1

7 3

出力例 1

X = 1 + 7 + 49 + 343 = 400 です。400 \leq 10^9 であるため 400 を出力します。

入力例 2

1000000 2

出力例 2

inf

X = 1000001000001 > 10^9 であるため、inf を出力します。

入力例 3

999999999 1

出力例 3

1000000000

入力例 4

998244353 99

出力例 4

inf

Score : 200 points

Problem Statement

You are given two positive integers N and M.

Let X = \displaystyle\sum_{i = 0}^{M} N^i. If X \leq 10^9, print the value of X. If X > 10^9, print inf.

Constraints

1 \leq N \leq 10^9
1 \leq M \leq 100
All input values are integers.

Input

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

N M

Output

Print the value of X or inf as specified by the problem statement.

Sample Input 1

7 3

Sample Output 1

X = 1 + 7 + 49 + 343 = 400. Since 400 \leq 10^9, print 400.

Sample Input 2

1000000 2

Sample Output 2

inf

X = 1000001000001 > 10^9, so print inf.

Sample Input 3

999999999 1

Sample Output 3

1000000000

Sample Input 4

998244353 99

Sample Output 4

inf

D - Greedy Draft

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の客がおり、1 から N までの番号が付けられています。また、M 本の缶ジュースがあり、1 から M までの番号が付けられています。

客 i (1 \leq i \leq N) は長さ L_i の希望リストを持っています。客 i の希望リストの先頭から j 番目 (1 \leq j \leq L_i) は缶ジュース X_{i,j} です。任意の客 i に対して、客 i の希望リストに載っている番号 X_{i, 1}, \dots, X_{i, L_i} は相異なります。

これから客 1, \dots, N が番号の小さいほうから順に、以下にしたがって自分が飲む飲料を選びます。

その時点で誰にも選ばれていない缶ジュースの番号が自分の希望リストに存在する場合、そのうち先頭に最も近い番号の缶ジュースを選ぶ。そうでない場合は水を選ぶ。

それぞれの客がどの飲料を得るかを求めてください。

制約

1 \leq N \leq 100
1 \leq M \leq 100
1 \leq L_i \leq M (1 \leq i \leq N)
1 \leq X_{i,j} \leq M (1 \leq i \leq N, 1 \leq j \leq L_i)
X_{i, 1}, \dots, X_{i, L_i} は相異なる (1 \leq i \leq N)
入力される値はすべて整数

入力

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

N M
L_1
X_{1,1} X_{1,2} \cdots X_{1,L_1}
L_2
X_{2,1} X_{2,2} \cdots X_{2,L_2}
\vdots
L_N
X_{N,1} X_{N,2} \cdots X_{N,L_N}

出力

N 行出力せよ。i 行目 (1 \leq i \leq N) には、客 i が缶ジュースを得る場合はその番号を、水を得る場合は 0 を出力せよ。

入力例 1

出力例 1

客 1 の希望リストにある番号のうち、対応する缶ジュースが誰にも選ばれていないのは 3,1,2 です。このうち先頭に最も近いのは 3 なので、客 1 は缶ジュース 3 を選びます。

客 2 の希望リストにある番号のうち、対応する缶ジュースが誰にも選ばれていないのは 2,1 です。このうち先頭に最も近いのは 2 なので、客 2 は缶ジュース 2 を選びます。

客 3 の希望リストにある番号について、対応する缶ジュースはすべてその時点で誰かに選ばれています。よって客 3 は水を選びます。

客 4 の希望リストにある番号のうち、対応する缶ジュースが誰にも選ばれていないのは 5,1 です。このうち先頭に最も近いのは 5 なので、客 4 は缶ジュース 5 を選びます。

入力例 2

出力例 2

Score : 200 points

Problem Statement

There are N customers numbered 1 to N, and M canned juices numbered 1 to M.

Customer i (1 \leq i \leq N) has a wish list of length L_i. The j-th item (1 \leq j \leq L_i) from the top of customer i's wish list is canned juice X_{i,j}. For any customer i, the numbers X_{i, 1}, \dots, X_{i, L_i} on customer i's wish list are distinct.

Customers 1, \dots, N, in this order, will now choose their beverages, following the procedure below.

If the customer's wish list contains a canned juice that has not yet been chosen by anyone at that point, they choose the canned juice whose number appears earliest in their wish list. Otherwise, they choose water.

Determine which beverage each customer gets.

Constraints

1 \leq N \leq 100
1 \leq M \leq 100
1 \leq L_i \leq M (1 \leq i \leq N)
1 \leq X_{i,j} \leq M (1 \leq i \leq N, 1 \leq j \leq L_i)
X_{i, 1}, \dots, X_{i, L_i} are distinct. (1 \leq i \leq N)
All input values are integers.

Input

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

N M
L_1
X_{1,1} X_{1,2} \cdots X_{1,L_1}
L_2
X_{2,1} X_{2,2} \cdots X_{2,L_2}
\vdots
L_N
X_{N,1} X_{N,2} \cdots X_{N,L_N}

Output

Output N lines. The i-th line (1 \leq i \leq N) should contain the number of the canned juice customer i gets if they get one, or 0 if customer i gets water.

Sample Input 1

Sample Output 1

Among the numbers on customer 1's wish list, the canned juices not yet chosen by anyone are 3, 1, 2. The one appearing earliest in the list is 3, so customer 1 chooses canned juice 3.

Among the numbers on customer 2's wish list, the canned juices not yet chosen by anyone are 2, 1. The one appearing earliest in the list is 2, so customer 2 chooses canned juice 2.

For the numbers on customer 3's wish list, all corresponding canned juices have already been chosen by someone at that point. Thus, customer 3 chooses water.

Among the numbers on customer 4's wish list, the canned juices not yet chosen by anyone are 5, 1. The one appearing earliest in the list is 5, so customer 4 chooses canned juice 5.

Sample Input 2

Sample Output 2

E - Sigma Problem

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

正整数 x,y に対して f(x,y) を「(x+y) を 10^8 で割ったあまり」として定義します。

長さ N の正整数列 A=(A_1,\ldots,A_N) が与えられます。次の式の値を求めてください。

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j)

制約

2\leq N\leq 3\times 10^5
1\leq A_i < 10^8
入力される数値は全て整数

入力

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

N 
A_1 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
3 50000001 50000002

出力例 1

100000012

f(A_1,A_2)=50000004
f(A_1,A_3)=50000005
f(A_2,A_3)=3

なので、答えは f(A_1,A_2)+f(A_1,A_3)+f(A_2,A_3) = 100000012 です。

総和を 10^8 で割ったあまりを求めるわけではないことに注意してください。

入力例 2

5
1 3 99999999 99999994 1000000

出力例 2

303999988

Score: 300 points

Problem Statement

For positive integers x and y, define f(x, y) as the remainder of (x + y) divided by 10^8.

You are given a sequence of positive integers A = (A_1, \ldots, A_N) of length N. Find the value of the following expression:

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j).

Constraints

2 \leq N \leq 3\times 10^5
1 \leq A_i < 10^8
All input values are integers.

Input

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

N 
A_1 \ldots A_N

Output

Print the answer.

Sample Input 1

3
3 50000001 50000002

Sample Output 1

100000012

f(A_1,A_2)=50000004
f(A_1,A_3)=50000005
f(A_2,A_3)=3

Thus, the answer is f(A_1,A_2) + f(A_1,A_3) + f(A_2,A_3) = 100000012.

Note that you are not asked to compute the remainder of the sum divided by 10^8.

Sample Input 2

5
1 3 99999999 99999994 1000000

Sample Output 2

303999988