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
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
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
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.
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) であって、以下の条件を満たすものが存在することをいいます。
制約
- 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:
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.

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.
