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
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
関数 f を f(x) = x^2 + 2x + 3 と定義します。
整数 t が入力されるので、 f(f(f(t)+t)+f(f(t))) を求めてください。
ただし、答えは 2 \times 10^9 以下の整数であることが保証されます。
制約
- t は 0 以上 10 以下の整数である
入力
入力は以下の形式で標準入力から与えられる。
t
出力
答えを整数として出力せよ。
入力例 1
0
出力例 1
1371
答えは以下の手順によって計算されます。
- f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
- f(t)+t = 3 + 0 = 3
- f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
- f(f(t)) = f(3) = 18
- f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371
入力例 2
3
出力例 2
722502
入力例 3
10
出力例 3
1111355571
Score : 100 points
Problem Statement
Let us define a function f as f(x) = x^2 + 2x + 3.
Given an integer t, find f(f(f(t)+t)+f(f(t))).
Here, it is guaranteed that the answer is an integer not greater than 2 \times 10^9.
Constraints
- t is an integer between 0 and 10 (inclusive).
Input
Input is given from Standard Input in the following format:
t
Output
Print the answer as an integer.
Sample Input 1
0
Sample Output 1
1371
The answer is computed as follows.
- f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
- f(t)+t = 3 + 0 = 3
- f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
- f(f(t)) = f(3) = 18
- f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371
Sample Input 2
3
Sample Output 2
722502
Sample Input 3
10
Sample Output 3
1111355571
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N 個の駅、駅 1, 駅 2, \ldots, 駅 N が直線上にこの順に並んでいます。
ここで、1\leq i\leq N-1 について、駅 i と駅 (i+1) の間の距離は D_i です。
1\leq i<j\leq N をみたす整数の組 (i,j) それぞれについて、駅 i と駅 j の間の距離を求めてください。
なお、出力形式については出力の欄を参照してください。
制約
- 2 \leq N \leq 50
- 1 \leq D_i \leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
D_1 D_2 \ldots D_{N-1}
出力
N-1 行出力せよ。
i 行目 (1\leq i\leq N-1) には、(N-i) 個の整数を空白区切りで出力せよ。
i 行目の j 番目 (1\leq j\leq N-i) には、駅 i と駅 (i+j) の間の距離を出力せよ。
入力例 1
5 5 10 2 3
出力例 1
5 15 17 20 10 12 15 2 5 3
各駅の間の距離は次のようになります。
- 駅 1 と駅 2 の間の距離は 5 です。
- 駅 1 と駅 3 の間の距離は 5+10=15 です。
- 駅 1 と駅 4 の間の距離は 5+10+2=17 です。
- 駅 1 と駅 5 の間の距離は 5+10+2+3=20 です。
- 駅 2 と駅 3 の間の距離は 10 です。
- 駅 2 と駅 4 の間の距離は 10+2=12 です。
- 駅 2 と駅 5 の間の距離は 10+2+3=15 です。
- 駅 3 と駅 4 の間の距離は 2 です。
- 駅 3 と駅 5 の間の距離は 2+3=5 です。
- 駅 4 と駅 5 の間の距離は 3 です。
よって、上記のように出力します。
入力例 2
2 100
出力例 2
100
Score : 200 points
Problem Statement
There are N stations, station 1, station 2, \ldots, station N, arranged in this order on a straight line.
Here, for 1\leq i\leq N-1, the distance between stations i and (i+1) is D_i.
For each pair of integers (i,j) satisfying 1\leq i<j\leq N, find the distance between stations i and j.
For the output format, refer to the Output section.
Constraints
- 2 \leq N \leq 50
- 1 \leq D_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
D_1 D_2 \ldots D_{N-1}
Output
Output N-1 lines.
On the i-th line (1\leq i\leq N-1), output (N-i) integers, separated by spaces.
The j-th integer on the i-th line (1\leq j\leq N-i) should be the distance between stations i and (i+j).
Sample Input 1
5 5 10 2 3
Sample Output 1
5 15 17 20 10 12 15 2 5 3
The distances between stations are as follows:
- The distance between stations 1 and 2 is 5.
- The distance between stations 1 and 3 is 5+10=15.
- The distance between stations 1 and 4 is 5+10+2=17.
- The distance between stations 1 and 5 is 5+10+2+3=20.
- The distance between stations 2 and 3 is 10.
- The distance between stations 2 and 4 is 10+2=12.
- The distance between stations 2 and 5 is 10+2+3=15.
- The distance between stations 3 and 4 is 2.
- The distance between stations 3 and 5 is 2+3=5.
- The distance between stations 4 and 5 is 3.
Thus, output as shown above.
Sample Input 2
2 100
Sample Output 2
100
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
高橋君は改札機の利用履歴を集計しました。 しかし、高橋君はうっかりいくつかの入退場記録を消してしまいました。 高橋君は消してしまった記録の復元を試みようとしています。
i, o のみからなる文字列 S が与えられます。
S の任意の位置に文字を 0 文字以上挿入することで、変更後の文字列が以下の条件を満たすようにしたいです。
- 長さが偶数であり、奇数文字目が
iで偶数文字目がoである。
挿入する必要のある文字数の最小値を求めて下さい。なお、問題の制約下で、有限個の文字を適切に挿入することで、S が条件をみたすようにできることが証明できます。
制約
- S は
i,oからなる長さ 1 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
ioi
出力例 1
1
3 文字目のあとに o を挿入して ioio とすることで、条件を満たすことができます。0 文字以下の挿入で条件を満たすことはできません。
入力例 2
iioo
出力例 2
2
1 文字目のあとに o を、3 文字目のあとに i を挿入することで、条件を満たすことができます。1 文字以下の挿入で条件を満たすことはできません。
入力例 3
io
出力例 3
0
S がすでに条件を満たします。
Score : 250 points
Problem Statement
Takahashi aggregated usage records from ticket gates. However, he accidentally erased some records of entering and exiting stations. He is trying to restore the erased records.
You are given a string S consisting of i and o. We want to insert zero or more characters at arbitrary positions in S so that the resulting string satisfies the following conditions:
- Its length is even, and every odd-numbered (1st, 3rd, ...) character is
iwhile every even-numbered (2nd, 4th, ...) character iso.
Find the minimum number of characters that need to be inserted. It can be proved under the constraints of this problem that by inserting an appropriate finite number of characters, S can be made to satisfy the conditions.
Constraints
- S is a string of length between 1 and 100, consisting of
iando.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
ioi
Sample Output 1
1
We can insert o after the 3rd character to form ioio to satisfy the conditions. The conditions cannot be satisfied by inserting zero or fewer characters.
Sample Input 2
iioo
Sample Output 2
2
We can insert o after the 1st character and i after the 3rd character to satisfy the conditions. The conditions cannot be satisfied by inserting one or fewer characters.
Sample Input 3
io
Sample Output 3
0
S already satisfies the conditions.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
N 頂点 M 辺の単純な無向グラフがあります。 グラフは頂点 1, 頂点 2,\ldots, 頂点 N からなり、i 番目 (1\le i\le M) の辺は頂点 u _ i と頂点 v _ i を結んでいます。
あなたは、次の操作を 0 回以上行います。
- まだ削除されていない辺をひとつ選び、削除する。
あなたの目的はグラフを二部グラフにすることです。 操作を行ったあとのグラフを二部グラフにするために、最低でも何回操作を行う必要があるか求めてください。
グラフが単純であるとは
グラフが単純であるとは、自己ループ(u _ i=v _ i となる辺)や多重辺(u _ i=u _ j かつ v _ i=v _ j となる辺のペア)が存在しないことをいいます。
二部グラフとは
二部グラフとは、頂点をそれぞれ黒か白のどちらか一色で塗り、次の条件を満たすことができるグラフのことをいいます。
- どの辺についても、その辺が結んでいるふたつの頂点に塗られた色は異なる。
制約
- 2\le N\le10
- 1\le M\le\dfrac{N(N-1)}2
- 1\le u _ i\lt v _ i\le N\ (1\le i\le M)
- 与えられるグラフは単純
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M u _ 1 v _ 1 u _ 2 v _ 2 \vdots u _ M v _ M
出力
操作を行ったあとのグラフを二部グラフにするために、行う必要がある操作の回数を出力せよ。
入力例 1
5 8 1 2 1 3 1 4 2 3 2 5 3 4 3 5 4 5
出力例 1
2
例えば、頂点 1 と頂点 3 を結ぶ辺、頂点 3 と頂点 5 を結ぶ辺の 2 つを削除することでグラフを二部グラフにすることができます。
操作を 1 回以下行うことでグラフを二部グラフにすることはできないため、2 を出力してください。
入力例 2
2 1 1 2
出力例 2
0
グラフははじめから二部グラフです。 よって、行う必要がある操作の回数は 0 回です。
入力例 3
10 20 5 9 1 4 3 8 1 6 4 10 5 7 5 6 3 7 3 6 5 10 1 3 3 4 6 7 1 2 4 7 1 5 1 9 9 10 4 5 8 9
出力例 3
5
Score : 350 points
Problem Statement
There is a simple undirected graph with N vertices and M edges. The graph consists of vertex 1, vertex 2,\ldots, vertex N, and the i-th edge (1\le i\le M) connects vertices u _ i and v _ i.
You will perform the following operation zero or more times:
- Choose one edge that has not been deleted yet, and delete it.
Your goal is to make the graph bipartite. Find the minimum number of operations needed to make the graph after the operations bipartite.
What it means for a graph to be simple?
A graph is simple if and only if it has no self-loops (edges where u _ i=v _ i) or multi-edges (pairs of edges where u _ i=u _ j and v _ i=v _ j).
What is a bipartite graph?
A bipartite graph is a graph where it is possible to color each vertex black or white satisfying the following condition:
- For every edge, the two vertices connected by that edge have different colors.
Constraints
- 2\le N\le10
- 1\le M\le\dfrac{N(N-1)}2
- 1\le u _ i\lt v _ i\le N\ (1\le i\le M)
- The given graph is simple.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M u _ 1 v _ 1 u _ 2 v _ 2 \vdots u _ M v _ M
Output
Print the number of operations that need to be performed to make the graph bipartite.
Sample Input 1
5 8 1 2 1 3 1 4 2 3 2 5 3 4 3 5 4 5
Sample Output 1
2
You can make the graph bipartite by deleting two edges: for example, the edge connecting vertices 1 and 3, and the edge connecting vertices 3 and 5.
It is impossible to make the graph bipartite by performing one or less operations, so print 2.
Sample Input 2
2 1 1 2
Sample Output 2
0
The graph is bipartite from the beginning. Thus, the number of operations that need to be performed is 0.
Sample Input 3
10 20 5 9 1 4 3 8 1 6 4 10 5 7 5 6 3 7 3 6 5 10 1 3 3 4 6 7 1 2 4 7 1 5 1 9 9 10 4 5 8 9
Sample Output 3
5