A - Range Swap

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の数列 A=(A_1,A_2,\ldots,A_N) および正整数 P,Q,R,S が与えられます。
ここで、P,Q,R,S は、1\leq P\leq Q<R\leq S \leq N および Q-P=S-R をみたしています。

数列 A の P 番目から Q 番目の項までと R 番目から S 番目の項までを入れ替えた数列を B=(B_1, B_2,\ldots, B_N) とします。
数列 B を出力してください。

制約

  • 1\leq N \leq 100
  • 1\leq A_i\leq 100
  • 1\leq P\leq Q<R\leq S \leq N
  • Q-P=S-R
  • 入力はすべて整数

入力

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

N P Q R S
A_1 A_2 \ldots A_N

出力

B_1, B_2,\ldots, B_N を空白区切りで出力せよ。


入力例 1

8 1 3 5 7
1 2 3 4 5 6 7 8

出力例 1

5 6 7 4 1 2 3 8

数列 A=(1,2,3,4,5,6,7,8) の 1 番目から 3 番目の項 (1,2,3) と 5 番目から 7 番目までの項 (5,6,7) を 入れ替えると, B=(5,6,7,4,1,2,3,8) となります。 よってこれを空白区切りで出力します。


入力例 2

5 2 3 4 5
2 2 1 1 1

出力例 2

2 1 1 2 1

数列には同じ整数が複数回現れる事もあります。


入力例 3

2 1 1 2 2
50 100

出力例 3

100 50

入力例 4

10 2 4 7 9
22 75 26 45 72 81 47 29 97 2

出力例 4

22 47 29 97 72 81 75 26 45 2

Score : 100 points

Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N and positive integers P,Q,R, and S.
Here, P,Q,R, and S satisfy 1\leq P\leq Q<R\leq S \leq N and Q-P=S-R.

Let B=(B_1, B_2,\ldots, B_N) be the sequence obtained by swapping the P-th through Q-th terms and the R-th through S-th terms of A.
Print the sequence B.

Constraints

  • 1\leq N \leq 100
  • 1\leq A_i\leq 100
  • 1\leq P\leq Q<R\leq S \leq N
  • Q-P=S-R
  • All values in the input are integers.

Input

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

N P Q R S
A_1 A_2 \ldots A_N

Output

Print B_1, B_2,\ldots, B_N, with spaces in between.


Sample Input 1

8 1 3 5 7
1 2 3 4 5 6 7 8

Sample Output 1

5 6 7 4 1 2 3 8

Swapping the 1-st through 3-rd terms (1,2,3) and the 5-th through 7-th terms (5,6,7) of the sequence A=(1,2,3,4,5,6,7,8) results in B=(5,6,7,4,1,2,3,8), which should be printed with spaces in between.


Sample Input 2

5 2 3 4 5
2 2 1 1 1

Sample Output 2

2 1 1 2 1

The same integer may occur multiple times in the sequence.


Sample Input 3

2 1 1 2 2
50 100

Sample Output 3

100 50

Sample Input 4

10 2 4 7 9
22 75 26 45 72 81 47 29 97 2

Sample Output 4

22 47 29 97 72 81 75 26 45 2
B - Long Loong

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

正の整数 X について、レベル X の 龍文字列 とは、1 個の L, X 個の o, 1 個の n, 1 個の g をこの順に並べた長さ (X+3) の文字列です。

正の整数 N が与えられるので、レベル N の龍文字列を出力してください。
大文字と小文字は区別されることに注意してください。

制約

  • 1\leq N\leq 2024
  • N は整数

入力

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

N

出力

レベル N の龍文字列を出力せよ。


入力例 1

3

出力例 1

Looong

1 個の L, 3 個の o, 1 個の n, 1 個の g をこの順に並べた文字列は Looong です。


入力例 2

1

出力例 2

Long

Score: 100 points

Problem Statement

For a positive integer X, the Dragon String of level X is a string of length (X+3) formed by one L, X occurrences of o, one n, and one g arranged in this order.

You are given a positive integer N. Print the Dragon String of level N.
Note that uppercase and lowercase letters are distinguished.

Constraints

  • 1 \leq N \leq 2024
  • N is an integer.

Input

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

N

Output

Print the Dragon String of level N.


Sample Input 1

3

Sample Output 1

Looong

Arranging one L, three os, one n, and one g in this order yields Looong.


Sample Input 2

1

Sample Output 2

Long
C - Sum of Digits Sequence

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 x に対して、f(x) を x の十進表記における各桁の和として定義します。例えば、f(123) = 1 + 2 + 3 = 6 です。

無限数列 A = (A_0, A_1, A_2, \ldots) を以下の式により定義します。

  • A_0 = 1
  • i \geq 1 のとき A_i = \displaystyle\sum_{j = 0}^{i - 1} f(A_j)

正整数 N が与えられます。A_N の値を求めてください。

制約

  • N は 1 以上 100 以下の整数

入力

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

N

出力

答えを出力せよ。


入力例 1

6

出力例 1

23
  • A_0 = 1
  • A_1 = f(A_0) = 1
  • A_2 = f(A_0) + f(A_1) = 2
  • A_3 = f(A_0) + f(A_1) + f(A_2) = 4
  • A_4 = f(A_0) + f(A_1) + f(A_2) + f(A_3) = 8
  • A_5 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) = 16
  • A_6 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) + f(A_5) = 23

であるため、A_6 = 23 です。


入力例 2

45

出力例 2

427

Score : 200 points

Problem Statement

For a positive integer x, define f(x) as the sum of the digits in the decimal representation of x. For example, f(123) = 1 + 2 + 3 = 6.

Define an infinite sequence A = (A_0, A_1, A_2, \ldots) by the following formula:

  • A_0 = 1
  • For i \geq 1, A_i = \displaystyle\sum_{j = 0}^{i - 1} f(A_j)

You are given a positive integer N. Find the value of A_N.

Constraints

  • N is an integer between 1 and 100, inclusive.

Input

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

N

Output

Print the answer.


Sample Input 1

6

Sample Output 1

23
  • A_0 = 1
  • A_1 = f(A_0) = 1
  • A_2 = f(A_0) + f(A_1) = 2
  • A_3 = f(A_0) + f(A_1) + f(A_2) = 4
  • A_4 = f(A_0) + f(A_1) + f(A_2) + f(A_3) = 8
  • A_5 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) = 16
  • A_6 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) + f(A_5) = 23

Thus, A_6 = 23.


Sample Input 2

45

Sample Output 2

427
D - Prefix and Suffix

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる文字列 S, T が与えられます。S の長さは N、T の長さは M です。(N \leq M が制約で保証されています)

S が T の 接頭辞 であるとは、T のはじめ N 文字からなる文字列が S と一致することを言います。
S が T の 接尾辞 であるとは、T の後ろ N 文字からなる文字列が S と一致することを言います。

S が T の接頭辞であり、かつ接尾辞でもある場合は 0 を、
S が T の接頭辞であるが、接尾辞でない場合は 1 を、
S が T の接尾辞であるが、接頭辞でない場合は 2 を、
S が T の接頭辞でも接尾辞でもない場合は 3 を出力してください。

制約

  • 1 \leq N \leq M \leq 100
  • S は英小文字からなる長さ N の文字列
  • T は英小文字からなる長さ M の文字列

入力

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

N M
S
T

出力

問題文の指示に従って答えを出力せよ。


入力例 1

3 7
abc
abcdefg

出力例 1

1

S は T の接頭辞ですが接尾辞ではありません。よって 1 を出力します。


入力例 2

3 4
abc
aabc

出力例 2

2

S は T の接尾辞ですが接頭辞ではありません。


入力例 3

3 3
abc
xyz

出力例 3

3

S は T の接頭辞でも接尾辞でもありません。


入力例 4

3 3
aaa
aaa

出力例 4

0

S と T が完全に一致する場合もあります。この場合、S は T の接頭辞であり、かつ接尾辞でもあります。

Score : 200 points

Problem Statement

You are given two strings S and T consisting of lowercase English letters. The lengths of S and T are N and M, respectively. (The constraints guarantee that N \leq M.)

S is said to be a prefix of T when the first N characters of T coincide S.
S is said to be a suffix of T when the last N characters of T coincide S.

If S is both a prefix and a suffix of T, print 0;
If S is a prefix of T but not a suffix, print 1;
If S is a suffix of T but not a prefix, print 2;
If S is neither a prefix nor a suffix of T, print 3.

Constraints

  • 1 \leq N \leq M \leq 100
  • S is a string of length N consisting of lowercase English letters.
  • T is a string of length M consisting of lowercase English letters.

Input

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

N M
S
T

Output

Print the answer according to the instructions in the problem statement.


Sample Input 1

3 7
abc
abcdefg

Sample Output 1

1

S is a prefix of T but not a suffix, so you should print 1.


Sample Input 2

3 4
abc
aabc

Sample Output 2

2

S is a suffix of T but not a prefix.


Sample Input 3

3 3
abc
xyz

Sample Output 3

3

S is neither a prefix nor a suffix of T.


Sample Input 4

3 3
aaa
aaa

Sample Output 4

0

S and T may coincide, in which case S is both a prefix and a suffix of T.

E - Cycle Graph?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1,2,\dots,N の番号が、辺には 1,2,\dots,M の番号がつけられており、辺 i は頂点 A_i と頂点 B_i を結んでいます。

このグラフがサイクルグラフであるか判定してください。

単純無向グラフとは 単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。

サイクルグラフとは 頂点に 1, 2, \dots, N の番号が付けられた N 頂点のグラフがサイクルグラフであるとは、(1, 2, \dots, N) を並べ変えて得られる数列 (v_1, v_2, \dots, v_N) であって、以下の条件を満たすものが存在することをいいます。
  • i = 1, 2, \dots, N-1 に対して、頂点 v_i と v_{i+1} を結ぶ辺が存在する
  • 頂点 v_N と v_1 を結ぶ辺が存在する
  • それら以外の辺は存在しない

制約

  • 3\leq N \leq 2\times 10^5
  • 0 \leq M \leq 2\times 10^5
  • 1 \leq A_i, B_i \leq N
  • 与えられるグラフは単純
  • 入力は全て整数

入力

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

N M
A_1 B_1
\vdots
A_M B_M

出力

与えられたグラフがサイクルグラフであるなら Yes、そうでないなら No と出力せよ。


入力例 1

4 4
2 4
3 1
4 1
2 3

出力例 1

Yes

与えられたグラフは以下の通りであり、これはサイクルグラフです。

図


入力例 2

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

出力例 2

No

与えられたグラフは以下の通りであり、これはサイクルグラフではありません。

図

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1,2,\dots,N and the edges are numbered 1,2,\dots,M. Edge i connects vertices A_i and B_i.

Determine whether this graph is a cycle graph.

Definition of simple undirected graph A simple undirected graph is a graph with undirected edges without self-loops or multi-edges.

Definition of cycle graph An N-vertex graph with vertices labeled 1,2,\dots,N is a cycle graph when there exists a permutation (v_1,v_2,\dots,v_N) of (1,2,\dots,N) such that:
  • For each i = 1,2,\dots,N-1, there is an edge between vertices v_i and v_{i+1}.
  • There is an edge between vertices v_N and v_1.
  • No other edges exist.

Constraints

  • 3 \le N \le 2\times 10^5
  • 0 \le M \le 2\times 10^5
  • 1 \le A_i, B_i \le N
  • The given graph is simple.
  • All input values are integers.

Input

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

N M
A_1 B_1
\vdots
A_M B_M

Output

Output Yes if the given graph is a cycle graph; otherwise, print No.


Sample Input 1

4 4
2 4
3 1
4 1
2 3

Sample Output 1

Yes

The given graph is as follows, and this is a cycle graph.

Figure


Sample Input 2

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

Sample Output 2

No

The given graph is as follows, and this is not a cycle graph.

Figure