A - o-padding

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 N および、英小文字からなる長さが N 未満 の文字列 S が与えられます。

長さが N になるまで S の先頭に英小文字 o を追加し続けることで得られる文字列を出力してください。

制約

  • 2\leq N \leq 100
  • N は整数
  • S は長さ 1 以上 N 未満の英小文字からなる文字列

入力

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

N
S

出力

答えを出力せよ。


入力例 1

5
abc

出力例 1

ooabc

N=5、S の長さは 3 であるため、S の先頭に o を 5-3=2 個追加した文字列が答えとなります。


入力例 2

2
o

出力例 2

oo

入力例 3

12
vgxgpuam

出力例 3

oooovgxgpuam

Score : 100 points

Problem Statement

You are given an integer N and a string S consisting of lowercase English letters with length less than N.

Print the string obtained by repeatedly adding the lowercase English letter o to the beginning of S until its length becomes N.

Constraints

  • 2\leq N \leq 100
  • N is an integer.
  • S is a string consisting of lowercase English letters with length between 1 and N - 1, inclusive.

Input

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

N
S

Output

Print the answer.


Sample Input 1

5
abc

Sample Output 1

ooabc

Since N=5 and the length of S is 3, the answer is the string obtained by adding 5-3=2 os to the beginning of S.


Sample Input 2

2
o

Sample Output 2

oo

Sample Input 3

12
vgxgpuam

Sample Output 3

oooovgxgpuam
B - Who Ate the Cake?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君のケーキが誰かに食べられてしまいました。ケーキを食べた犯人の候補として、人 1、人 2、人 3 の三人が挙げられています。

犯人の目撃者はりんごさんとすぬけくんの二人がいます。りんごさんは人 A が犯人でないことを覚えており、すぬけくんは人 B が犯人でないことを覚えています。

二人の記憶から犯人を一人に特定できるかどうか判定し、特定できるならばその人の番号を出力してください。

制約

  • 1\leq A,B\leq 3
  • 入力は全て整数

入力

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

A B

出力

二人の記憶から犯人を一人に特定できるならばその人の番号を出力し、特定できないならば -1 を出力せよ。


入力例 1

1 2

出力例 1

3

二人の記憶から、人 3 が犯人であることが特定できます。


入力例 2

1 1

出力例 2

-1

二人の記憶からでは、人 2,3 のどちらが犯人か特定することができません。よって -1 を出力します。


入力例 3

3 1

出力例 3

2

Score : 100 points

Problem Statement

Takahashi's cake has been eaten by someone. There are three suspects: person 1, person 2, and person 3.

There are two witnesses, Ringo and Snuke. Ringo remembers that person A is not the culprit, and Snuke remembers that person B is not the culprit.

Determine if the culprit can be uniquely identified based on the memories of the two witnesses. If the culprit can be identified, print the person's number.

Constraints

  • 1 \leq A, B \leq 3
  • All input values are integers.

Input

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

A B

Output

If the culprit can be uniquely identified based on the memories of the two witnesses, print the person's number; otherwise, print -1.


Sample Input 1

1 2

Sample Output 1

3

From the memories of the two witnesses, it can be determined that person 3 is the culprit.


Sample Input 2

1 1

Sample Output 2

-1

From the memories of the two witnesses, it cannot be determined whether person 2 or person 3 is the culprit. Therefore, print -1.


Sample Input 3

3 1

Sample Output 3

2
C - Locked Rooms

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N + 1 個の部屋が一列に並んでおり、順に 0, 1, \ldots, N の番号が付けられています。

部屋の間には N 個のドアがあり、1, 2, \ldots, N の番号が付けられています。ドア i は部屋 i - 1 と部屋 i の間にあります。

各ドアについて鍵の状態を表す値 L_i が与えられ、L_i = 0 のときドア i の鍵は開いており、L_i = 1 のときドア i の鍵は閉まっています。

2 人の人がおり、1 人は部屋 0 に、もう 1 人は部屋 N にいます。それぞれの人は、ドア i の鍵が開いているときに限り、部屋 i - 1 と部屋 i の間を移動することができます。

このとき、2 人のいずれも到達できない部屋の個数を求めてください。

制約

  • 2 \leq N \leq 100
  • L_i \in \lbrace 0, 1 \rbrace
  • 入力される値はすべて整数

入力

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

N
L_1 L_2 \ldots L_N

出力

答えを出力せよ。


入力例 1

5
0 1 0 0 1

出力例 1

3

2 人のいずれも到達できない部屋は部屋 2, 3, 4 の 3 つです。


入力例 2

3
1 0 1

出力例 2

2

入力例 3

8
0 0 1 1 0 1 0 0

出力例 3

3

Score : 200 points

Problem Statement

There are N + 1 rooms arranged in a line, numbered 0, 1, \ldots, N in order.

Between the rooms, there are N doors numbered 1, 2, \ldots, N. Door i is between rooms i - 1 and i.

For each door, a value L_i representing the lock state is given. When L_i = 0, door i is unlocked, and when L_i = 1, door i is locked.

There are two people, one in room 0 and the other in room N. Each person can move between rooms i - 1 and i only when door i is unlocked.

Find the number of rooms that neither of the two people can reach.

Constraints

  • 2 \leq N \leq 100
  • L_i \in \lbrace 0, 1 \rbrace
  • All input values are integers.

Input

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

N
L_1 L_2 \ldots L_N

Output

Output the answer.


Sample Input 1

5
0 1 0 0 1

Sample Output 1

3

The rooms that neither of the two people can reach are rooms 2, 3, 4, which is 3 rooms.


Sample Input 2

3
1 0 1

Sample Output 2

2

Sample Input 3

8
0 0 1 1 0 1 0 0

Sample Output 3

3
D - Hard Calculation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 A,B が与えられます。
A+B を(十進法で)計算する時、繰り上がりが生じないなら Easy 、生じるなら Hard と出力してください。

制約

  • A,B は整数
  • 1 \le A,B \le 10^{18}

入力

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

A B

出力

繰り上がりが生じないなら Easy 、生じるなら Hard と出力せよ。


入力例 1

229 390

出力例 1

Hard

229+390 を計算する際、十の位から百の位へと繰り上がりが発生します。よって、答えは Hard です。


入力例 2

123456789 9876543210

出力例 2

Easy

繰り上がりは発生しません。答えは Easy です。
また、入力が 32bit 整数に収まらないこともあります。

Score : 200 points

Problem Statement

You are given positive integers A and B.
Let us calculate A+B (in decimal). If it does not involve a carry, print Easy; if it does, print Hard.

Constraints

  • A and B are integers.
  • 1 \le A,B \le 10^{18}

Input

Input is given from Standard Input in the following format:

A B

Output

If the calculation does not involve a carry, print Easy; if it does, print Hard.


Sample Input 1

229 390

Sample Output 1

Hard

When calculating 229+390, we have a carry from the tens digit to the hundreds digit, so the answer is Hard.


Sample Input 2

123456789 9876543210

Sample Output 2

Easy

We do not have a carry here; the answer is Easy.
Note that the input may not fit into a 32-bit integer.

E - 2026

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

正整数 n が次の条件を満たす時、n を 良い整数 と呼びます。

  • 0 \lt x \lt y かつ x^2+y^2=n を満たす整数の組 (x,y) がただ 1 つ存在する。

例えば n=2026 とすると、0 \lt x \lt y かつ x^2+y^2=n を満たす整数の組は (x,y)=(1,45) しか存在しないことが確認できます。よって 2026 は良い整数です。

正整数 N が与えられます。N 以下の良い整数を全て列挙してください。

制約

  • 1 \leq N \leq 10^7
  • N は整数

入力

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

N

出力

N 以下の良い整数が k 個あり、それらを昇順に並べた列が (a_1, a_2, \dots, a_k) であるとする。この時、以下の形式で答えを出力せよ。(k=0 である場合は 2 行目は空行として出力せよ。)

k
a_1 a_2 \dots a_k

入力例 1

10

出力例 1

2
5 10

0 \lt x \lt y かつ x^2+y^2=5 を満たす整数の組は (x,y)=(1,2) しか存在しないので 5 は良い整数です。
0 \lt x \lt y かつ x^2+y^2=10 を満たす整数の組は (x,y)=(1,3) しか存在しないので 10 は良い整数です。
N 以下の良い整数はこの 2 個のみです。


入力例 2

1

出力例 2

0


入力例 3

50

出力例 3

14
5 10 13 17 20 25 26 29 34 37 40 41 45 50

Score : 300 points

Problem Statement

A positive integer n is called a good integer when it satisfies the following condition:

  • There exists exactly one pair of integers (x,y) that satisfies 0 \lt x \lt y and x^2+y^2=n.

For example, when n=2026, it can be verified that (x,y)=(1,45) is the only pair of integers that satisfies 0 \lt x \lt y and x^2+y^2=n. Thus, 2026 is a good integer.

You are given a positive integer N. Enumerate all good integers not exceeding N.

Constraints

  • 1 \leq N \leq 10^7
  • N is an integer.

Input

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

N

Output

Let there be k good integers not exceeding N, and let (a_1, a_2, \dots, a_k) be the sequence of these integers in ascending order. Output the answer in the following format. (If k=0, output the second line as an empty line.)

k
a_1 a_2 \dots a_k

Sample Input 1

10

Sample Output 1

2
5 10

(x,y)=(1,2) is the only pair of integers that satisfies 0 \lt x \lt y and x^2+y^2=5, so 5 is a good integer.
(x,y)=(1,3) is the only pair of integers that satisfies 0 \lt x \lt y and x^2+y^2=10, so 10 is a good integer.
These are the only two good integers not exceeding N.


Sample Input 2

1

Sample Output 2

0


Sample Input 3

50

Sample Output 3

14
5 10 13 17 20 25 26 29 34 37 40 41 45 50
F - Previous Permutation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

(1, \dots, N) の順列 P = (P_1, \dots, P_N) が与えられます。ただし、(P_1, \dots, P_N) \neq (1, \dots, N) です。

(1 \dots, N) の順列を全て辞書順で小さい順に並べたとき、P が K 番目であるとします。辞書順で小さい方から K-1 番目の順列を求めてください。

順列とは?

(1, \dots, N) の順列とは、(1, \dots, N) を並べ替えて得られる数列のことをいいます。

辞書順とは?

長さ N の数列 A = (A_1, \dots, A_N), B = (B_1, \dots, B_N) に対し、A が B より辞書順で真に小さいとは、ある整数 1 \leq i \leq N が存在して、下記の 2 つがともに成り立つことをいいます。

  • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
  • A_i < B_i

制約

  • 2 \leq N \leq 100
  • 1 \leq P_i \leq N \, (1 \leq i \leq N)
  • P_i \neq P_j \, (i \neq j)
  • (P_1, \dots, P_N) \neq (1, \dots, N)
  • 入力される値は全て整数

入力

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

N
P_1 \ldots P_N

出力

求める順列を Q = (Q_1, \dots, Q_N) として、Q_1, \dots, Q_N をこの順に空白区切りで一行に出力せよ。


入力例 1

3
3 1 2

出力例 1

2 3 1

(1, 2, 3) の順列を辞書順で小さい順に並べると次のようになります。

  • (1, 2, 3)
  • (1, 3, 2)
  • (2, 1, 3)
  • (2, 3, 1)
  • (3, 1, 2)
  • (3, 2, 1)

よって P = (3, 1, 2) は小さい方から 5 番目であり、求める順列、すなわち小さい方から 5 - 1 = 4 番目の順列は (2, 3, 1) です。


入力例 2

10
9 8 6 5 10 3 1 2 4 7

出力例 2

9 8 6 5 10 2 7 4 3 1

Score : 300 points

Problem Statement

You are given a permutation P = (P_1, \dots, P_N) of (1, \dots, N), where (P_1, \dots, P_N) \neq (1, \dots, N).

Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.

What are permutations?

A permutation of (1, \dots, N) is an arrangement of (1, \dots, N) into a sequence.

What is lexicographical order?

For sequences of length N, A = (A_1, \dots, A_N) and B = (B_1, \dots, B_N), A is said to be strictly lexicographically smaller than B if and only if there is an integer 1 \leq i \leq N that satisfies both of the following.

  • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1}).
  • A_i < B_i.

Constraints

  • 2 \leq N \leq 100
  • 1 \leq P_i \leq N \, (1 \leq i \leq N)
  • P_i \neq P_j \, (i \neq j)
  • (P_1, \dots, P_N) \neq (1, \dots, N)
  • All values in the input are integers.

Input

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

N
P_1 \ldots P_N

Output

Let Q = (Q_1, \dots, Q_N) be the sought permutation. Print Q_1, \dots, Q_N in a single line in this order, separated by spaces.


Sample Input 1

3
3 1 2

Sample Output 1

2 3 1

Here are the permutations of (1, 2, 3) in ascending lexicographical order.

  • (1, 2, 3)
  • (1, 3, 2)
  • (2, 1, 3)
  • (2, 3, 1)
  • (3, 1, 2)
  • (3, 2, 1)

Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).


Sample Input 2

10
9 8 6 5 10 3 1 2 4 7

Sample Output 2

9 8 6 5 10 2 7 4 3 1
G - "redocta".swap(i,i+1)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

atcoder の並べ替えである文字列 S が与えられます。
この文字列 S に対して以下の操作を 0 回以上行います。

  • S 中の隣接する 2 文字を選び、入れ替える。

S を atcoder にするために必要な最小の操作回数を求めてください。

制約

  • S は atcoder の並べ替えである文字列

入力

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

S

出力

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


入力例 1

catredo

出力例 1

8

catredo \rightarrow [ac]tredo \rightarrow actre[od] \rightarrow actr[oe]d \rightarrow actro[de] \rightarrow act[or]de \rightarrow acto[dr]e \rightarrow a[tc]odre \rightarrow atcod[er]
という流れで操作を行うと、 8 回で S を atcoder にすることができ、これが達成可能な最小の操作回数です。


入力例 2

atcoder

出力例 2

0

この場合、文字列 S は元から atcoder です。


入力例 3

redocta

出力例 3

21

Score : 400 points

Problem Statement

You are given a string S that is a permutation of atcoder.
On this string S, you will perform the following operation 0 or more times:

  • Choose two adjacent characters of S and swap them.

Find the minimum number of operations required to make S equal atcoder.

Constraints

  • S is a string that is a permutation of atcoder

Input

Input is given from Standard Input in the following format:

S

Output

Print the answer as an integer.


Sample Input 1

catredo

Sample Output 1

8

You can make S equal atcoder in 8 operations as follows:
catredo \rightarrow [ac]tredo \rightarrow actre[od] \rightarrow actr[oe]d \rightarrow actro[de] \rightarrow act[or]de \rightarrow acto[dr]e \rightarrow a[tc]odre \rightarrow atcod[er]
This is the minimum number of operations achievable.


Sample Input 2

atcoder

Sample Output 2

0

In this case, the string S is already atcoder.


Sample Input 3

redocta

Sample Output 3

21
H - Arithmetic Number

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

以下の条件を満たす正の整数 n を、 等差数 と呼びます。

  • (n を先頭に余計な 0 を付けずに 10 進法で表記した際、) n の上から i 桁目を d_i とする。このとき、 n が k 桁の整数であったとすると、 (d_2-d_1)=(d_3-d_2)=\dots=(d_k-d_{k-1}) が成立する。
    • この条件は、「 数列 (d_1,d_2,\dots,d_k) が等差数列である」と言い換えることができる。
    • 但し、 n が 1 桁の整数である時、 n は等差数であるものとする。

たとえば、 234,369,86420,17,95,8,11,777 は等差数ですが、 751,919,2022,246810,2356 は等差数ではありません。

等差数のうち、 X 以上で最小のものを求めてください。

制約

  • X は 1 以上 10^{17} 以下の整数である

入力

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

X

出力

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


入力例 1

152

出力例 1

159

152 以上で最小の等差数は 159 です。


入力例 2

88

出力例 2

88

X 自身が等差数である場合もあります。


入力例 3

8989898989

出力例 3

9876543210

Score : 500 points

Problem Statement

Let us call a positive integer n that satisfies the following condition an arithmetic number.

  • Let d_i be the i-th digit of n from the top (when n is written in base 10 without unnecessary leading zeros.) Then, (d_2-d_1)=(d_3-d_2)=\dots=(d_k-d_{k-1}) holds, where k is the number of digits in n.
    • This condition can be rephrased into the sequence (d_1,d_2,\dots,d_k) being arithmetic.
    • If n is a 1-digit integer, it is assumed to be an arithmetic number.

For example, 234,369,86420,17,95,8,11,777 are arithmetic numbers, while 751,919,2022,246810,2356 are not.

Find the smallest arithmetic number not less than X.

Constraints

  • X is an integer between 1 and 10^{17} (inclusive).

Input

Input is given from Standard Input in the following format:

X

Output

Print the answer as an integer.


Sample Input 1

152

Sample Output 1

159

The smallest arithmetic number not less than 152 is 159.


Sample Input 2

88

Sample Output 2

88

X itself may be an arithmetic number.


Sample Input 3

8989898989

Sample Output 3

9876543210
I - Maximum Diameter

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

長さ N の正整数列 X=(X_1,X_2\ldots,X_N) に対して、f(X) を以下のように定めます。

  • N 頂点の木であって、i\ (1 \leq i \leq N) 番目の頂点の次数が X_i であるようなものを良い木と呼ぶ。 良い木が存在するならば、f(X) は良い木の直径の最大値。良い木が存在しないならば、f(X)=0。

ただし、木の 2 頂点の間の距離は一方から他方へ移動するときに用いる辺の本数の最小値であり、 木の直径は任意の 2 頂点の間の距離の最大値として定められます。

長さ N の正整数列 X としてあり得るもの全てに対する f(X) の総和を 998244353 で割った余りを求めてください。 なお、f(X) の総和は有限値になることが証明できます。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1\leq T \leq 2\times 10^5
  • 2 \leq N \leq 10^6
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで、\mathrm{test}_i は i 番目のテストケースを意味する。

T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T

各テストケースは以下の形式で与えられる。

N

出力

T 行出力せよ。

i\ (1\leq i \leq T) 行目には、i 番目のテストケースに対する答えを出力せよ。


入力例 1

10
2
3
5
8
13
21
34
55
89
144

出力例 1

1
6
110
8052
9758476
421903645
377386885
881422708
120024839
351256142

N=3 の場合について、

例えば、

  • X=(1,1,1) のとき、次数が 1,1,1 となる 3 頂点の木は存在しないため、f(X)=0 です。
  • X=(2,1,1) のとき、良い木は以下の図のものに限られます。この木の直径は 2 であるため、f(X)=2 です。


3 頂点の木

X=(2,1,1),(1,2,1),(1,1,2) のとき f(X)=2 であり、それ以外の X のとき f(X)=0 であるため、答えは 6 です。

Score : 500 points

Problem Statement

For a sequence X=(X_1,X_2\ldots,X_N) of length N consisting of positive integers, we define f(X) as follows:

  • A tree with N vertices is said to be good if and only if the degree of the i-th (1 \leq i \leq N) vertex is X_i. If a good tree exists, f(X) is the maximum diameter of a good tree; if it doesn't, f(X)=0.

Here, the distance between two vertices is the minimum number of edges that must be traversed to travel from one vertex to the other, and the diameter of a tree is the maximum distance between two vertices.

Find the sum, modulo 998244353, of f(X) over all possible sequences X of length N consisting of positive integers. We can prove that the sum of f(X) is a finite value.

Given T test cases, find the answer for each of them.

Constraints

  • 1\leq T \leq 2\times 10^5
  • 2 \leq N \leq 10^6
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{test}_i denotes the i-th test case:

T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T

Each test case is given in the following format:

N

Output

Print T lines.

The i-th (1\leq i \leq T) line should contain the answer to the i-th test case.


Sample Input 1

10
2
3
5
8
13
21
34
55
89
144

Sample Output 1

1
6
110
8052
9758476
421903645
377386885
881422708
120024839
351256142

If N=3,

for example,

  • when X=(1,1,1), there is no tree with three vertices whose degrees are 1,1, and 1, so f(X)=0.
  • When X=(2,1,1), the only possible tree is illustrated below. The diameter of this tree is 2, so f(X)=2.


3-vertex tree

For X=(2,1,1),(1,2,1),(1,1,2), we have f(X)=2; for other X, we have f(X)=0. Thus, the answer is 6.