C - Multiple Gift

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

高橋君は、日頃の感謝を込めて、お母さんに数列をプレゼントすることにしました。 お母さんにプレゼントする数列 A は、以下の条件を満たす必要があります。

  • A は X 以上 Y 以下の整数からなる
  • すべての 1\leq i \leq |A|-1 に対し、A_{i+1} は A_i の倍数であり、かつ A_{i+1} は A_i より真に大きい

高橋君がお母さんにプレゼントできる数列の長さの最大値を求めてください。

制約

  • 1 \leq X \leq Y \leq 10^{18}
  • 入力は全て整数である

入力

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

X Y

出力

数列の長さの最大値を出力せよ。

入力例 1

3 20

出力例 1

3

数列 3,6,18 が条件を満たします。

入力例 2

25 100

出力例 2

3

入力例 3

314159265 358979323846264338

出力例 3

31

Score : 300 points

Problem Statement

As a token of his gratitude, Takahashi has decided to give his mother an integer sequence. The sequence A needs to satisfy the conditions below:

  • A consists of integers between X and Y (inclusive).
  • For each 1\leq i \leq |A|-1, A_{i+1} is a multiple of A_i and strictly greater than A_i.

Find the maximum possible length of the sequence.

Constraints

  • 1 \leq X \leq Y \leq 10^{18}
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

Print the maximum possible length of the sequence.

Sample Input 1

3 20

Sample Output 1

3

The sequence 3,6,18 satisfies the conditions.

Sample Input 2

25 100

Sample Output 2

3

Sample Input 3

314159265 358979323846264338

Sample Output 3

31
D - Wide Flip

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 500 点

問題文

0 と 1 からなる文字列 S が与えられます。 以下の操作を好きな回数繰り返すことで S の要素をすべて 0 にできるような、|S| 以下の最大の整数 K を求めてください。

  • S の長さ K 以上の連続する区間 [l,r] を選ぶ(すなわち、r-l+1\geq K が満たされる必要がある)。l\leq i\leq r なるすべての整数 i に対し、S_i が 0 なら S_i を 1 に、S_i が 1 なら S_i を 0 に置き換える。

制約

  • 1\leq |S|\leq 10^5
  • S_i(1\leq i\leq N) は 0 または 1 である

入力

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

S

出力

操作を好きな回数繰り返すことで S の要素をすべて 0 にできるような 最大の (21:08 JST 修正) 整数 K を出力せよ。

入力例 1

010

出力例 1

2

以下の操作で、S の要素をすべて 0 にできます。

  • 長さ 3 の区間 [1,3] に操作を行う。S は 101 になる。
  • 長さ 2 の区間 [1,2] に操作を行う。S は 011 になる。
  • 長さ 2 の区間 [2,3] に操作を行う。S は 000 になる。

入力例 2

100000000

出力例 2

8

入力例 3

00001111

出力例 3

4

Score : 500 points

Problem Statement

You are given a string S consisting of 0 and 1. Find the maximum integer K not greater than |S| such that we can turn all the characters of S into 0 by repeating the following operation some number of times.

  • Choose a contiguous segment [l,r] in S whose length is at least K (that is, r-l+1\geq K must be satisfied). For each integer i such that l\leq i\leq r, do the following: if S_i is 0, replace it with 1; if S_i is 1, replace it with 0.

Constraints

  • 1\leq |S|\leq 10^5
  • S_i(1\leq i\leq N) is either 0 or 1.

Input

Input is given from Standard Input in the following format:

S

Output

Print the maximum integer K such that we can turn all the characters of S into 0 by repeating the operation some number of times.

Sample Input 1

010

Sample Output 1

2

We can turn all the characters of S into 0 by the following operations:

  • Perform the operation on the segment S[1,3] with length 3. S is now 101.
  • Perform the operation on the segment S[1,2] with length 2. S is now 011.
  • Perform the operation on the segment S[2,3] with length 2. S is now 000.

Sample Input 2

100000000

Sample Output 2

8

Sample Input 3

00001111

Sample Output 3

4
E - Papple Sort

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 800 点

問題文

英小文字からなる文字列 S が与えられます。 隣り合う 2 つの文字を入れ替える操作を繰り返して S を回文にできるかどうか判定し、できる場合は操作の最小回数を求めてください。

制約

  • 1 \leq |S| \leq 2 × 10^5
  • S は英小文字からなる

入力

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

S

出力

回文にできない場合、-1 を出力せよ。そうでない場合、操作の最小回数を出力せよ。

入力例 1

eel

出力例 1

1

以下の操作で、S を回文にすることができます。

  • 2 文字目と 3 文字目を入れ替える。新しい S は ele となる。

入力例 2

ataatmma

出力例 2

4

以下の操作で、S を回文にすることができます。

  • 5 文字目と 6 文字目を入れ替える。新しい S は ataamtma となる。
  • 4 文字目と 5 文字目を入れ替える。新しい S は atamatma となる。
  • 3 文字目と 4 文字目を入れ替える。新しい S は atmaatma となる。
  • 2 文字目と 3 文字目を入れ替える。新しい S は amtaatma となる。

入力例 3

snuke

出力例 3

-1

S を回文にすることはできません。

Score : 800 points

Problem Statement

You are given a string S consisting of lowercase English letters. Determine whether we can turn S into a palindrome by repeating the operation of swapping two adjacent characters. If it is possible, find the minimum required number of operations.

Constraints

  • 1 \leq |S| \leq 2 × 10^5
  • S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

If we cannot turn S into a palindrome, print -1. Otherwise, print the minimum required number of operations.

Sample Input 1

eel

Sample Output 1

1

We can turn S into a palindrome by the following operation:

  • Swap the 2-nd and 3-rd characters. S is now ele.

Sample Input 2

ataatmma

Sample Output 2

4

We can turn S into a palindrome by the following operation:

  • Swap the 5-th and 6-th characters. S is now ataamtma.
  • Swap the 4-th and 5-th characters. S is now atamatma.
  • Swap the 3-rd and 4-th characters. S is now atmaatma.
  • Swap the 2-nd and 3-rd characters. S is now amtaatma.

Sample Input 3

snuke

Sample Output 3

-1

We cannot turn S into a palindrome.
F - Christmas Tree

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 900 点

問題文

高橋君は、AtCoder 社のクリスマスパーティーに向けて、クリスマスツリーを作ることにしました。

クリスマスツリーとは 頂点に 1 から N まで番号付けられた N 頂点 N-1 辺の木で、 i(1\leq i\leq N-1) 本目の辺は頂点 a_i と頂点 b_i を結んでいます。

高橋君は、以下の方法でクリスマスツリーを作りたいです。

  • 2 つの非負整数 A,B を指定する。
  • 長さ B 以下のクリスマスパスを A 個用意する。ただし、長さ X のクリスマスパスとは、X+1 頂点 X 辺からなるグラフであって、頂点に 1 から X+1 までの番号を適切につければ、i(1\leq i\leq X) 本目の辺が頂点 i と頂点 i+1 を結んでいるようにできるものを指す。
  • 以下の操作を、全体が連結になるまで繰り返す。
    • 異なる連結成分に属する 2 頂点 x,y をとる。頂点 x と頂点 y をまとめて 1 つの頂点にする。より正確には、頂点 y に接続するすべての辺 (p,y) について辺 (p,x) を追加したあと、頂点 y と、y に接続する辺をすべて削除する。
  • 出来上がった木の各頂点に、適当な番号をつける。

高橋君は、クリスマスツリーを作ることのできるような組 (A,B) のうち、辞書順最小のものを求めたいです。 すなわち、A の最小値を求め、A の最小値を達成するという条件のもとで B の最小値も求めたいです。

高橋君にかわって、この問題を解いてください。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq a_i,b_i \leq N
  • 与えられるグラフは木である

入力

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

N
a_1 b_1
:
a_{N-1} b_{N-1}

出力

辞書順最小の (A,B) に対し、A,B を空白区切りで出力せよ。

入力例 1

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

出力例 1

3 2

下の図のような方法で、クリスマスツリーを作ることができます。

入力例 2

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

出力例 2

2 5

入力例 3

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

出力例 3

3 4

Score : 900 points

Problem Statement

Takahashi has decided to make a Christmas Tree for the Christmas party in AtCoder, Inc.

A Christmas Tree is a tree with N vertices numbered 1 through N and N-1 edges, whose i-th edge (1\leq i\leq N-1) connects Vertex a_i and b_i.

He would like to make one as follows:

  • Specify two non-negative integers A and B.
  • Prepare A Christmas Paths whose lengths are at most B. Here, a Christmas Path of length X is a graph with X+1 vertices and X edges such that, if we properly number the vertices 1 through X+1, the i-th edge (1\leq i\leq X) will connect Vertex i and i+1.
  • Repeat the following operation until he has one connected tree:
    • Select two vertices x and y that belong to different connected components. Combine x and y into one vertex. More precisely, for each edge (p,y) incident to the vertex y, add the edge (p,x). Then, delete the vertex y and all the edges incident to y.
  • Properly number the vertices in the tree.

Takahashi would like to find the lexicographically smallest pair (A,B) such that he can make a Christmas Tree, that is, find the smallest A, and find the smallest B under the condition that A is minimized.

Solve this problem for him.

Constraints

  • 2 \leq N \leq 10^5
  • 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
a_1 b_1
:
a_{N-1} b_{N-1}

Output

For the lexicographically smallest (A,B), print A and B with a space in between.

Sample Input 1

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

Sample Output 1

3 2

We can make a Christmas Tree as shown in the figure below:

Sample Input 2

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

Sample Output 2

2 5

Sample Input 3

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

Sample Output 3

3 4