A - Round One

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

高橋君はペーパークイズを解いています。高橋君はすらすらと解いていき、残すは最終問題のみとなりました。

この問題は、答えが 1,2,3 のいずれかである 3 択問題です。

高橋君は超能力によって、A と B が誤答であることがわかりました。

この問題の答えを出力してください。

制約

  • A,B は 1,2,3 のいずれか
  • A と B は異なる

入力

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

A
B

出力

答えを出力せよ。

入力例 1

3
1

出力例 1

2

1,2,3 のうち、3 でも 1 でもないのは 2 です。

入力例 2

1
2

出力例 2

3

Score: 100 points

Problem Statement

Takahashi is solving quizzes. He has easily solved all but the last one.

The last quiz has three choices: 1, 2, and 3.

With his supernatural power, Takahashi has found out that the choices A and B are both wrong.

Print the correct choice for this problem.

Constraints

  • Each of the numbers A and B is 1, 2, or 3.
  • A and B are different.

Input

Input is given from Standard Input in the following format:

A
B

Output

Print the correct choice.

Sample Input 1

3
1

Sample Output 1

2

When we know 3 and 1 are both wrong, the correct choice is 2.

Sample Input 2

1
2

Sample Output 2

3
B - Strings with the Same Length

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

英小文字のみからなる長さ N の文字列 S, T が与えられます。

S の 1 文字目、T の 1 文字目、S の 2 文字目、T の2 文字目、S の 3 文字目、...、S のN 文字目、T のN 文字目というように、 S の各文字と T の各文字を先頭から順に交互に文字を並べ、新しい文字列を作ります。この新しくできた文字列を出力してください。

制約

  • 1 ≤ N ≤ 100
  • |S| = |T| = N
  • S, T は英小文字のみからなる文字列

入力

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

N
S T

出力

新しくできた文字列を出力せよ。

入力例 1

2
ip cc

出力例 1

icpc

入力例 2

8
hmhmnknk uuuuuuuu

出力例 2

humuhumunukunuku

入力例 3

5
aaaaa aaaaa

出力例 3

aaaaaaaaaa

Score : 200 points

Problem Statement

Given are strings s and t of length N each, both consisting of lowercase English letters.

Let us form a new string by alternating the characters of S and the characters of T, as follows: the first character of S, the first character of T, the second character of S, the second character of T, ..., the N-th character of S, the N-th character of T. Print this new string.

Constraints

  • 1 \leq N \leq 100
  • |S| = |T| = N
  • S and T are strings consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S T

Output

Print the string formed.

Sample Input 1

2
ip cc

Sample Output 1

icpc

Sample Input 2

8
hmhmnknk uuuuuuuu

Sample Output 2

humuhumunukunuku

Sample Input 3

5
aaaaa aaaaa

Sample Output 3

aaaaaaaaaa
C - Snack

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 300 点

問題文

高橋君はパーティを企画しています。

パーティーでは参加者に 1 人 1 個以上のお菓子を配る予定です。

高橋君は参加者の人数が A 人か B 人のどちらかになるだろうという予想を立てました。

どちらの場合でも均等に配りきることができるようなお菓子の個数の最小値を求めてください。

ただし、 1 個のお菓子を分割して複数人で分けることはできないものとします。

制約

  • 1 \le A, B \le 10^5
  • A \neq B
  • 入力はすべて整数

入力

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

A B

出力

参加者の人数が A 人の場合でも B 人の場合でも均等に配りきることができるようなお菓子の個数の最小値を出力せよ。

入力例 1

2 3

出力例 1

6

6 個のお菓子があるとき、参加者が 2 人の場合は 3 個ずつ、 3 人の場合は 2 個ずつ配ることができます。

入力例 2

123 456

出力例 2

18696

入力例 3

100000 99999

出力例 3

9999900000

Score : 300 points

Problem Statement

Takahashi is organizing a party.

At the party, each guest will receive one or more snack pieces.

Takahashi predicts that the number of guests at this party will be A or B.

Find the minimum number of pieces that can be evenly distributed to the guests in both of the cases predicted.

We assume that a piece cannot be divided and distributed to multiple guests.

Constraints

  • 1 \leq A, B \leq 10^5
  • A \neq B
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B

Output

Print the minimum number of pieces that can be evenly distributed to the guests in both of the cases with A guests and B guests.

Sample Input 1

2 3

Sample Output 1

6

When we have six snack pieces, each guest can take three pieces if we have two guests, and each guest can take two if we have three guests.

Sample Input 2

123 456

Sample Output 2

18696

Sample Input 3

100000 99999

Sample Output 3

9999900000
D - Brick Break

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

N 個のレンガが横一列に並んでいます。

左から i~(1 \leq i \leq N) 番目のレンガには、整数 a_i が書かれています。

あなたはこのうち N - 1 個以下の任意のレンガを選んで砕くことができます。

その結果、K 個のレンガが残っているとします。このとき、任意の整数 i~(1 \leq i \leq K) について、残っているレンガの中で左から i 番目のものに書かれた整数が i であるとき、すぬけさんは満足します。

すぬけさんが満足するために砕く必要のあるレンガの最小個数を出力してください。もし、どのように砕いてもそれが不可能な場合、代わりに -1 を出力してください。

制約

  • 入力は全て整数である。
  • 1 \leq N \leq 200000
  • 1 \leq a_i \leq N

入力

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

N
a_1 a_2 ... a_N

出力

すぬけさんが満足するために砕く必要のあるレンガの最小個数を出力せよ。もし、どのように砕いてもそれが不可能な場合、代わりに -1 を出力せよ。

入力例 1

3
2 1 2

出力例 1

1

一番左のレンガ 1 個を砕くと、残ったレンガに書かれた整数は左から 1, 2 となります。

このとき、すぬけさんは満足します。

入力例 2

3
2 2 2

出力例 2

-1

この場合、すぬけさんが満足するレンガの砕き方は存在しません。

入力例 3

10
3 1 4 1 5 9 2 6 5 3

出力例 3

7

入力例 4

1
1

出力例 4

0

レンガを 1 つも砕かなくていい場合もあります。

Score : 400 points

Problem Statement

We have N bricks arranged in a row from left to right.

The i-th brick from the left (1 \leq i \leq N) has an integer a_i written on it.

Among them, you can break at most N-1 bricks of your choice.

Let us say there are K bricks remaining. Snuke will be satisfied if, for each integer i (1 \leq i \leq K), the i-th of those brick from the left has the integer i written on it.

Find the minimum number of bricks you need to break to satisfy Snuke's desire. If his desire is unsatisfiable, print -1 instead.

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 200000
  • 1 \leq a_i \leq N

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the minimum number of bricks that need to be broken to satisfy Snuke's desire, or print -1 if his desire is unsatisfiable.

Sample Input 1

3
2 1 2

Sample Output 1

1

If we break the leftmost brick, the remaining bricks have integers 1 and 2 written on them from left to right, in which case Snuke will be satisfied.

Sample Input 2

3
2 2 2

Sample Output 2

-1

In this case, there is no way to break some of the bricks to satisfy Snuke's desire.

Sample Input 3

10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

7

Sample Input 4

1
1

Sample Output 4

0

There may be no need to break the bricks at all.
E - Double Factorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

0 以上の整数 n に対し、 f(n) を次のように定義します。

  • f(n) = 1 (n < 2 のとき)
  • f(n) = n f(n-2) (n ≥ 2 のとき)

整数 N が与えられます。f(N) を 10 進法で表記した時に末尾に何個の 0 が続くかを求めてください。

制約

  • 0 ≤ N ≤ 10^{18}

入力

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

N

出力

f(N) を 10 進法で表記した時の末尾の 0 の個数を出力せよ。

入力例 1

12

出力例 1

1

f(12) = 12 × 10 × 8 × 6 × 4 × 2 = 46080 なので、末尾の 0 の個数は 1 個です。

入力例 2

5

出力例 2

0

f(5) = 5 × 3 × 1 = 15 なので、末尾の 0 の個数は 0 個です。

入力例 3

1000000000000000000

出力例 3

124999999999999995

Score : 500 points

Problem Statement

For an integer n not less than 0, let us define f(n) as follows:

  • f(n) = 1 (if n < 2)
  • f(n) = n f(n-2) (if n \geq 2)

Given is an integer N. Find the number of trailing zeros in the decimal notation of f(N).

Constraints

  • 0 \leq N \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of trailing zeros in the decimal notation of f(N).

Sample Input 1

12

Sample Output 1

1

f(12) = 12 × 10 × 8 × 6 × 4 × 2 = 46080, which has one trailing zero.

Sample Input 2

5

Sample Output 2

0

f(5) = 5 × 3 × 1 = 15, which has no trailing zeros.

Sample Input 3

1000000000000000000

Sample Output 3

124999999999999995
F - Playing Tag on Tree

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点の木があります。i 番目の辺は頂点 A_i と B_i を双方向に結んでいます。

この木の頂点 u に高橋君が、頂点 v に青木君がいます。

2 人は次のような手順で鬼ごっこをします。

  • 1. 高橋君と青木君が同じ頂点にいるときゲームを終了する。そうでないとき、高橋君は隣接する頂点を 1 つ選んでその頂点に移動する。

  • 2. 高橋君と青木君が同じ頂点にいるときゲームを終了する。そうでないとき、青木君は隣接する頂点を 1 つ選んでその頂点に移動する。

  • 3. 1 に戻る。

高橋君はできるだけ遅くゲームが終了するように移動し、青木君はできるだけ早くゲームが終了するように移動します。

高橋君と青木君が常に互いの位置と戦略を把握し最適に移動するとき、ゲームが終了するまでに青木君が移動する回数を求めてください。

なお、ゲームは必ず終了することが証明できます。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq u,v \leq N
  • u \neq v
  • 1 \leq A_i,B_i \leq N
  • 与えられるグラフは木である

入力

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

N u v
A_1 B_1
:
A_{N-1} B_{N-1}

出力

ゲームが終了するまでに青木君が移動する回数を出力せよ。

入力例 1

5 4 1
1 2
2 3
3 4
3 5

出力例 1

2

互いに最適に移動した場合、ゲームは次のように進行します。

  • 高橋君が頂点 3 に移動
  • 青木君が頂点 2 に移動
  • 高橋君が頂点 5 に移動
  • 青木君が頂点 3 に移動
  • 高橋君が頂点 3 に移動

このとき、ゲームが終了するまでの青木君の移動回数は 2 回です。

各手番で同じ頂点にとどまることは出来ないことに注意してください。

入力例 2

5 4 5
1 2
1 3
1 4
1 5

出力例 2

1

入力例 3

2 1 2
1 2

出力例 3

0

入力例 4

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

出力例 4

5

Score : 600 points

Problem Statement

We have a tree with N vertices. The i-th edge connects Vertex A_i and B_i bidirectionally.

Takahashi is standing at Vertex u, and Aoki is standing at Vertex v.

Now, they will play a game of tag as follows:

  • 1. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Takahashi moves to a vertex of his choice that is adjacent to his current vertex.

  • 2. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Aoki moves to a vertex of his choice that is adjacent to his current vertex.

  • 3. Go back to step 1.

Takahashi performs his moves so that the game ends as late as possible, while Aoki performs his moves so that the game ends as early as possible.

Find the number of moves Aoki will perform before the end of the game if both Takahashi and Aoki know each other's position and strategy.

It can be proved that the game is bound to end.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq u,v \leq N
  • u \neq v
  • 1 \leq A_i,B_i \leq N
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N u v
A_1 B_1
:
A_{N-1} B_{N-1}

Output

Print the number of moves Aoki will perform before the end of the game.

Sample Input 1

5 4 1
1 2
2 3
3 4
3 5

Sample Output 1

2

If both players play optimally, the game will progress as follows:

  • Takahashi moves to Vertex 3.
  • Aoki moves to Vertex 2.
  • Takahashi moves to Vertex 5.
  • Aoki moves to Vertex 3.
  • Takahashi moves to Vertex 3.

Here, Aoki performs two moves.

Note that, in each move, it is prohibited to stay at the current vertex.

Sample Input 2

5 4 5
1 2
1 3
1 4
1 5

Sample Output 2

1

Sample Input 3

2 1 2
1 2

Sample Output 3

0

Sample Input 4

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

Sample Output 4

5