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 - Weird Function

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
C - Distance Table

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
D - Ticket Gate Log

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 i while every even-numbered (2nd, 4th, ...) character is o.

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 i and o.

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.

E - Bipartize

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