A - Shift

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。
あなたは次の操作をちょうど K 回行います。

  • A の先頭の要素を取り除き、A の末尾に 0 を挿入する。

操作を行った後の A の要素をすべて出力してください。

制約

  • 1 \leq N \leq 100
  • 1 \leq K \leq 100
  • 1 \leq A_i \leq 100
  • 入力される値はすべて整数

入力

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

N K
A_1 A_2 \dots A_N

出力

操作を行った後の A の要素を空白区切りで 1 行に出力せよ。


入力例 1

3 2
2 7 8

出力例 1

8 0 0

操作を行う前は A = (2, 7, 8) です。
操作を 1 回行った時点では A = (7, 8, 0) です。
操作を 2 回行った時点では A = (8, 0, 0) です。
よって (8, 0, 0) が答えです。


入力例 2

3 4
9 9 9

出力例 2

0 0 0

入力例 3

9 5
1 2 3 4 5 6 7 8 9

出力例 3

6 7 8 9 0 0 0 0 0

Score : 100 points

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.
You perform the following operation exactly K times:

  • remove the initial element of A and append a 0 to the tail of A.

Print all the elements of A after the operations.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq K \leq 100
  • 1 \leq A_i \leq 100
  • All values in the input are integers.

Input

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

N K
A_1 A_2 \dots A_N

Output

Print the elements of A after the operations in one line, separated by spaces.


Sample Input 1

3 2
2 7 8

Sample Output 1

8 0 0

Before the operations, A = (2, 7, 8).
After performing the operation once, A = (7, 8, 0).
After performing the operation twice, A = (8, 0, 0).
Thus, (8, 0, 0) is the answer.


Sample Input 2

3 4
9 9 9

Sample Output 2

0 0 0

Sample Input 3

9 5
1 2 3 4 5 6 7 8 9

Sample Output 3

6 7 8 9 0 0 0 0 0
B - Zero Sum Game

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 から N の番号が付けられた N 人の人がおり、この中で一対一の勝敗のつくゲームを何度か行いました。N 人は最初にそれぞれ持ち点として 0 を持っており、各ゲームでは勝者の持ち点が 1 増え、敗者の持ち点が 1 減ります(持ち点が負になることもあります)。最終的に人 i\ (1\leq i\leq N-1) の持ち点が A_i になったとき、人 N の持ち点を求めてください。なお、ゲームの進行によらず最終的な人 N の持ち点は一意に定まることが示せます。

制約

  • 2\leq N\leq 100
  • -100\leq A_i\leq 100
  • 入力は全て整数

入力

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

N
A_1 A_2 \ldots A_{N-1}

出力

答えを出力せよ。


入力例 1

4
1 -2 -1

出力例 1

2

最終的に人 1,2,3 の持ち点が 1,-2,-1 となるような進行として、例えば次のようなものが考えられます。

  • 最初、人 1,2,3,4 の持ち点はそれぞれ 0,0,0,0 である。
  • 人 1 と 2 が対戦して、人 1 が勝利する。4 人の持ち点はそれぞれ 1,-1,0,0 である。
  • 人 1 と 4 が対戦して、人 4 が勝利する。4 人の持ち点はそれぞれ 0,-1,0,1 である。
  • 人 1 と 2 が対戦して、人 1 が勝利する。4 人の持ち点はそれぞれ 1,-2,0,1 である。
  • 人 2 と 3 が対戦して、人 2 が勝利する。4 人の持ち点はそれぞれ 1,-1,-1,1 である。
  • 人 2 と 4 が対戦して、人 4 が勝利する。4 人の持ち点はそれぞれ 1,-2,-1,2 である。

この場合、人 4 の持ち点は 2 になります。ほかにも別の進行が考えられますが、どのような進行であっても人 4 の持ち点は 2 になります。


入力例 2

3
0 0

出力例 2

0

入力例 3

6
10 20 30 40 50

出力例 3

-150

Score: 100 points

Problem Statement

There are N people labeled 1 to N, who have played several one-on-one games without draws. Initially, each person started with 0 points. In each game, the winner's score increased by 1 and the loser's score decreased by 1 (scores can become negative). Determine the final score of person N if the final score of person i\ (1\leq i\leq N-1) is A_i. It can be shown that the final score of person N is uniquely determined regardless of the sequence of games.

Constraints

  • 2 \leq N \leq 100
  • -100 \leq A_i \leq 100
  • All input values are integers.

Input

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

N
A_1 A_2 \ldots A_{N-1}

Output

Print the answer.


Sample Input 1

4
1 -2 -1

Sample Output 1

2

Here is one possible sequence of games where the final scores of persons 1, 2, 3 are 1, -2, -1, respectively.

  • Initially, persons 1, 2, 3, 4 have 0, 0, 0, 0 points, respectively.
  • Persons 1 and 2 play, and person 1 wins. The players now have 1, -1, 0, 0 point(s).
  • Persons 1 and 4 play, and person 4 wins. The players now have 0, -1, 0, 1 point(s).
  • Persons 1 and 2 play, and person 1 wins. The players now have 1, -2, 0, 1 point(s).
  • Persons 2 and 3 play, and person 2 wins. The players now have 1, -1, -1, 1 point(s).
  • Persons 2 and 4 play, and person 4 wins. The players now have 1, -2, -1, 2 point(s).

In this case, the final score of person 4 is 2. Other possible sequences of games exist, but the score of person 4 will always be 2 regardless of the progression.


Sample Input 2

3
0 0

Sample Output 2

0

Sample Input 3

6
10 20 30 40 50

Sample Output 3

-150
C - Pasta

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君の家には N 本の麺からなるパスタがあり、i 本目の麺の長さは A_i です。
高橋君はこれから M 日間の食事計画を立てており、 i 日目にはパスタの麺のうち長さがちょうど B_i であるようなものを 1 本選び、食べようと考えています。 もし、1 日目から M 日目の間に 1 日でもそのような麺が無い日があれば、食事計画は失敗となります。 また、同じ麺を複数の日に食べることはできません。

高橋君が食事計画を最後まで実行することは可能ですか?

制約

  • 1 \leq M \leq N \leq 1000
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 入力はすべて整数である。

入力

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

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

出力

高橋君が食事計画を最後まで実行できる場合は Yes を、そうでない場合は No を出力せよ。


入力例 1

3 2
1 1 3
3 1

出力例 1

Yes

1 日目に 3 本目の麺を、2 日目に 1 本目の麺を食べれば良いので、高橋君の食事計画は実行可能です。


入力例 2

1 1
1000000000
1

出力例 2

No

長さがちょうど 1 の麺が存在する必要があります。


入力例 3

5 2
1 2 3 4 5
5 5

出力例 3

No

長さが 5 の麺は 1 本しか存在しないため、2 日目に食事をとる事が出来ません。

Score : 200 points

Problem Statement

There is pasta consisting of N noodles at Takahashi's home. The length of the i-th noodle is A_i.
Takahashi has a meal plan for the next M days. On the i-th day, he is going to choose a pasta noodle of length exactly B_i and eat it. If no such noodle is available on any day, his plan fails. Additionally, he cannot eat the same noodle on multiple days.

Can Takahashi accomplish his meal plan?

Constraints

  • 1 \leq M \leq N \leq 1000
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

Output

If Takahashi can accomplish his meal plan, print Yes; otherwise, print No.


Sample Input 1

3 2
1 1 3
3 1

Sample Output 1

Yes

He can eat the 3-rd noodle on the 1-st day and the 1-st noodle on the 2-nd day, so his meal plan is feasible.


Sample Input 2

1 1
1000000000
1

Sample Output 2

No

A noodle of length exactly 1 is needed.


Sample Input 3

5 2
1 2 3 4 5
5 5

Sample Output 3

No

Since there are only 1 noodle of length 5, he cannot have a meal on the 2-nd day.

D - Strictly Superior

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder 商店には N 個の商品があります。 i\ (1\leq i\leq N) 番目の商品の価格は P _ i です。 i\ (1\leq i\leq N) 番目の商品は C _ i 個の機能をもち、i\ (1\leq i\leq N) 番目の商品の j\ (1\leq j\leq C _ i) 番目の機能は 1 以上 M 以下の整数 F _ {i,j} として表されます。

高橋くんは、AtCoder 商店の商品で一方が一方の上位互換であるものがないか気になりました。 i 番目の商品と j 番目の商品 (1\leq i,j\leq N) であって、次の条件をすべて満たすものがあるとき Yes と、ないとき No と出力してください。

  • P _ i\geq P _ j である。
  • j 番目の製品は i 番目の製品がもつ機能をすべてもつ。
  • P _ i\gt P _ j であるか、j 番目の製品は i 番目の製品にない機能を 1 つ以上もつ。

制約

  • 2\leq N\leq100
  • 1\leq M\leq100
  • 1\leq P _ i\leq10^5\ (1\leq i\leq N)
  • 1\leq C _ i\leq M\ (1\leq i\leq N)
  • 1\leq F _ {i,1}\lt F _ {i,2}\lt\cdots\lt F _ {i,C _ i}\leq M\ (1\leq i\leq N)
  • 入力はすべて整数

入力

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

N M
P _ 1 C _ 1 F _ {1,1} F _ {1,2} \ldots F _ {1,C _ 1}
P _ 2 C _ 2 F _ {2,1} F _ {2,2} \ldots F _ {2,C _ 2}
\vdots
P _ N C _ N F _ {N,1} F _ {N,2} \ldots F _ {N,C _ N}

出力

答えを 1 行で出力せよ。


入力例 1

5 6
10000 2 1 3
15000 3 1 2 4
30000 3 1 3 5
35000 2 1 5
100000 6 1 2 3 4 5 6

出力例 1

Yes

(i,j)=(4,3) とすると、条件を全て満たします。

他の組は条件を満たしません。例えば (i,j)=(4,5) とすると j 番目の商品は i 番目の商品の機能をすべてもっていますが、P _ i\lt P _ j なので上位互換ではありません。


入力例 2

4 4
3 1 1
3 1 2
3 1 2
4 2 2 3

出力例 2

No

まったく同じ価格と機能をもった商品がある場合もあります。


入力例 3

20 10
72036 3 3 4 9
7716 4 1 2 3 6
54093 5 1 6 7 8 10
25517 7 3 4 5 6 7 9 10
96930 8 2 3 4 6 7 8 9 10
47774 6 2 4 5 6 7 9
36959 5 1 3 4 5 8
46622 7 1 2 3 5 6 8 10
34315 9 1 3 4 5 6 7 8 9 10
54129 7 1 3 4 6 7 8 9
4274 5 2 4 7 9 10
16578 5 2 3 6 7 9
61809 4 1 2 4 5
1659 5 3 5 6 9 10
59183 5 1 2 3 4 9
22186 4 3 5 6 8
98282 4 1 4 7 10
72865 8 1 2 3 4 6 8 9 10
33796 6 1 3 5 7 9 10
74670 4 1 2 6 8

出力例 3

Yes

Score : 200 points

Problem Statement

AtCoder Shop has N products. The price of the i-th product (1\leq i\leq N) is P _ i. The i-th product (1\leq i\leq N) has C_i functions. The j-th function (1\leq j\leq C _ i) of the i-th product (1\leq i\leq N) is represented as an integer F _ {i,j} between 1 and M, inclusive.

Takahashi wonders whether there is a product that is strictly superior to another. If there are i and j (1\leq i,j\leq N) such that the i-th and j-th products satisfy all of the following conditions, print Yes; otherwise, print No.

  • P _ i\geq P _ j.
  • The j-th product has all functions of the i-th product.
  • P _ i\gt P _ j, or the j-th product has one or more functions that the i-th product lacks.

Constraints

  • 2\leq N\leq100
  • 1\leq M\leq100
  • 1\leq P _ i\leq10^5\ (1\leq i\leq N)
  • 1\leq C _ i\leq M\ (1\leq i\leq N)
  • 1\leq F _ {i,1}\lt F _ {i,2}\lt\cdots\lt F _ {i,C _ i}\leq M\ (1\leq i\leq N)
  • All input values are integers.

Input

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

N M
P _ 1 C _ 1 F _ {1,1} F _ {1,2} \ldots F _ {1,C _ 1}
P _ 2 C _ 2 F _ {2,1} F _ {2,2} \ldots F _ {2,C _ 2}
\vdots
P _ N C _ N F _ {N,1} F _ {N,2} \ldots F _ {N,C _ N}

Output

Print the answer in a single line.


Sample Input 1

5 6
10000 2 1 3
15000 3 1 2 4
30000 3 1 3 5
35000 2 1 5
100000 6 1 2 3 4 5 6

Sample Output 1

Yes

(i,j)=(4,3) satisfies all of the conditions.

No other pair satisfies them. For instance, for (i,j)=(4,5), the j-th product has all functions of the i-th one, but P _ i\lt P _ j, so it is not strictly superior.


Sample Input 2

4 4
3 1 1
3 1 2
3 1 2
4 2 2 3

Sample Output 2

No

Multiple products may have the same price and functions.


Sample Input 3

20 10
72036 3 3 4 9
7716 4 1 2 3 6
54093 5 1 6 7 8 10
25517 7 3 4 5 6 7 9 10
96930 8 2 3 4 6 7 8 9 10
47774 6 2 4 5 6 7 9
36959 5 1 3 4 5 8
46622 7 1 2 3 5 6 8 10
34315 9 1 3 4 5 6 7 8 9 10
54129 7 1 3 4 6 7 8 9
4274 5 2 4 7 9 10
16578 5 2 3 6 7 9
61809 4 1 2 4 5
1659 5 3 5 6 9 10
59183 5 1 2 3 4 9
22186 4 3 5 6 8
98282 4 1 4 7 10
72865 8 1 2 3 4 6 8 9 10
33796 6 1 3 5 7 9 10
74670 4 1 2 6 8

Sample Output 3

Yes
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

出力

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


入力例 1

abc

出力例 1

3

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

1

どの 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:

S

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

3

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

1

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