AtCoder Beginner Contest 138

A - Red or Not

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

整数 a と、英小文字からなる文字列 s が入力されます。

a が 3200 以上なら s と出力し、a が 3200 未満なら red と出力するプログラムを書いてください。

制約

2800 \leq a < 5000
s は長さ 1 以上 10 以下の文字列である。
s の各文字は英小文字である。

入力

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

a
s

出力

a が 3200 以上なら s と出力し、a が 3200 未満なら red と出力せよ。

入力例 1

3200
pink

出力例 1

pink

a = 3200 は 3200 以上であるため s = pink と出力します。

入力例 2

3199
pink

出力例 2

red

a = 3199 は 3200 未満であるため red と出力します。

入力例 3

4049
red

出力例 3

red

a = 4049 は 3200 以上であるため s = red と出力します。

Score : 100 points

Problem Statement

You will be given an integer a and a string s consisting of lowercase English letters as input.

Write a program that prints s if a is not less than 3200 and prints red if a is less than 3200.

Constraints

2800 \leq a < 5000
s is a string of length between 1 and 10 (inclusive).
Each character of s is a lowercase English letter.

Input

Input is given from Standard Input in the following format:

a
s

Output

If a is not less than 3200, print s; if a is less than 3200, print red.

Sample Input 1

3200
pink

Sample Output 1

pink

a = 3200 is not less than 3200, so we print s = pink.

Sample Input 2

3199
pink

Sample Output 2

red

a = 3199 is less than 3200, so we print red.

Sample Input 3

4049
red

Sample Output 3

red

a = 4049 is not less than 3200, so we print s = red.

B - Resistors in Parallel

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

N 個の整数の列 A_1, \ldots, A_N が与えられます。

これらの逆数の総和の逆数 \frac{1}{\frac{1}{A_1} + \ldots + \frac{1}{A_N}} を求めてください。

制約

1 \leq N \leq 100
1 \leq A_i \leq 1000

入力

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

N
A_1 A_2 \ldots A_N

出力

\frac{1}{\frac{1}{A_1} + \ldots + \frac{1}{A_N}} の値を表す小数 (または整数) を出力せよ。

出力は、ジャッジの出力との絶対誤差または相対誤差が 10^{-5} 以下のとき正解と判定される。

入力例 1

2
10 30

出力例 1

7.5

\frac{1}{\frac{1}{10} + \frac{1}{30}} = \frac{1}{\frac{4}{30}} = \frac{30}{4} = 7.5 です。

なお、7.50001, 7.49999 などと出力しても正解と判定されます。

入力例 2

3
200 200 200

出力例 2

66.66666666666667

\frac{1}{\frac{1}{200} + \frac{1}{200} + \frac{1}{200}} = \frac{1}{\frac{3}{200}} = \frac{200}{3} = 66.6666... です。

なお、6.66666e+1 などと出力しても正解と判定されます。

入力例 3

1
1000

出力例 3

\frac{1}{\frac{1}{1000}} = 1000 です。

なお、+1000.0 などと出力しても正解と判定されます。

Score : 200 points

Problem Statement

Given is a sequence of N integers A_1, \ldots, A_N.

Find the (multiplicative) inverse of the sum of the inverses of these numbers, \frac{1}{\frac{1}{A_1} + \ldots + \frac{1}{A_N}}.

Constraints

1 \leq N \leq 100
1 \leq A_i \leq 1000

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print a decimal number (or an integer) representing the value of \frac{1}{\frac{1}{A_1} + \ldots + \frac{1}{A_N}}.

Your output will be judged correct when its absolute or relative error from the judge's output is at most 10^{-5}.

Sample Input 1

2
10 30

Sample Output 1

7.5

\frac{1}{\frac{1}{10} + \frac{1}{30}} = \frac{1}{\frac{4}{30}} = \frac{30}{4} = 7.5.

Printing 7.50001, 7.49999, and so on will also be accepted.

Sample Input 2

3
200 200 200

Sample Output 2

66.66666666666667

\frac{1}{\frac{1}{200} + \frac{1}{200} + \frac{1}{200}} = \frac{1}{\frac{3}{200}} = \frac{200}{3} = 66.6666....

Printing 6.66666e+1 and so on will also be accepted.

Sample Input 3

1
1000

Sample Output 3

\frac{1}{\frac{1}{1000}} = 1000.

Printing +1000.0 and so on will also be accepted.

C - Alchemist

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

あなたは鍋と N 個の具材を持っています。各具材は価値と呼ばれる実数の値を持ち、i 個目 (1 \leq i \leq N) の具材の価値は v_i です。

2 個の具材を鍋に入れると、それらは消滅して新たに 1 個の具材が生成されます。この新たな具材の価値は元の 2 個の具材の価値を x, y として (x + y) / 2 であり、この具材を再び鍋に入れることもできます。

この具材の合成を N - 1 回行うと、最後に 1 個の具材が残ります。この具材の価値として考えられる最大の値を求めてください。

制約

2 \leq N \leq 50
1 \leq v_i \leq 1000
入力中の値はすべて整数である。

入力

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

N
v_1 v_2 \ldots v_N

出力

最後に残る 1 個の具材の価値として考えられる最大の値を表す小数 (または整数) を出力せよ。

出力は、ジャッジの出力との絶対誤差または相対誤差が 10^{-5} 以下のとき正解と判定される。

入力例 1

2
3 4

出力例 1

3.5

はじめに持っている具材が 2 個の場合、それらをともに鍋に入れるほかありません。価値 3, 4 の具材から合成される具材の価値は (3 + 4) / 2 = 3.5 です。

なお、3.50001, 3.49999 などと出力しても正解となります。

入力例 2

3
500 300 200

出力例 2

今回ははじめに 3 個の具材を持っており、一度目の合成で鍋にどの具材を入れるかに選択の余地があります。選択肢は次の 3 通りです。

価値 500, 300 の具材を入れ、価値 (500 + 300) / 2 = 400 の具材を合成する。この場合、次の合成ではこれと価値 200 の具材を鍋に入れることになり、価値 (400 + 200) / 2 = 300 の具材が合成される。
価値 500, 200 の具材を入れ、価値 (500 + 200) / 2 = 350 の具材を合成する。この場合、次の合成ではこれと価値 300 の具材を鍋に入れることになり、価値 (350 + 300) / 2 = 325 の具材が合成される。
価値 300, 200 の具材を入れ、価値 (300 + 200) / 2 = 250 の具材を合成する。この場合、次の合成ではこれと価値 500 の具材を鍋に入れることになり、価値 (250 + 500) / 2 = 375 の具材が合成される。

よって、最後に残る 1 個の具材の価値として考えられる最大の値は 375 です。

なお、375.0 などと出力しても正解となります。

入力例 3

5
138 138 138 138 138

出力例 3

Score : 300 points

Problem Statement

You have a pot and N ingredients. Each ingredient has a real number parameter called value, and the value of the i-th ingredient (1 \leq i \leq N) is v_i.

When you put two ingredients in the pot, they will vanish and result in the formation of a new ingredient. The value of the new ingredient will be (x + y) / 2 where x and y are the values of the ingredients consumed, and you can put this ingredient again in the pot.

After you compose ingredients in this way N-1 times, you will end up with one ingredient. Find the maximum possible value of this ingredient.

Constraints

2 \leq N \leq 50
1 \leq v_i \leq 1000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
v_1 v_2 \ldots v_N

Output

Print a decimal number (or an integer) representing the maximum possible value of the last ingredient remaining.

Your output will be judged correct when its absolute or relative error from the judge's output is at most 10^{-5}.

Sample Input 1

2
3 4

Sample Output 1

3.5

If you start with two ingredients, the only choice is to put both of them in the pot. The value of the ingredient resulting from the ingredients of values 3 and 4 is (3 + 4) / 2 = 3.5.

Printing 3.50001, 3.49999, and so on will also be accepted.

Sample Input 2

3
500 300 200

Sample Output 2

You start with three ingredients this time, and you can choose what to use in the first composition. There are three possible choices:

Use the ingredients of values 500 and 300 to produce an ingredient of value (500 + 300) / 2 = 400. The next composition will use this ingredient and the ingredient of value 200, resulting in an ingredient of value (400 + 200) / 2 = 300.
Use the ingredients of values 500 and 200 to produce an ingredient of value (500 + 200) / 2 = 350. The next composition will use this ingredient and the ingredient of value 300, resulting in an ingredient of value (350 + 300) / 2 = 325.
Use the ingredients of values 300 and 200 to produce an ingredient of value (300 + 200) / 2 = 250. The next composition will use this ingredient and the ingredient of value 500, resulting in an ingredient of value (250 + 500) / 2 = 375.

Thus, the maximum possible value of the last ingredient remaining is 375.

Printing 375.0 and so on will also be accepted.

Sample Input 3

5
138 138 138 138 138

Sample Output 3

D - Ki

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

1 から N までの番号がついた N 個の頂点を持つ根付き木が与えられます。この木の根は頂点 1 で、i 番目の辺 (1 \leq i \leq N - 1) は頂点 a_i と頂点 b_i を結びます。

各頂点にはカウンターが設置されており、はじめすべての頂点のカウンターの値は 0 です。

これから、以下のような Q 回の操作が行われます。

操作 j (1 \leq j \leq Q): 頂点 p_j を根とする部分木に含まれるすべての頂点のカウンターの値に x_j を足す。

すべての操作のあとの各頂点のカウンターの値を求めてください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq a_i < b_i \leq N
1 \leq p_j \leq N
1 \leq x_j \leq 10^4
与えられるグラフは木である。
入力中の値はすべて整数である。

入力

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

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

出力

すべての操作のあとの各頂点のカウンターの値を、頂点 1, 2, \ldots, N の順に空白区切りで出力せよ。

入力例 1

出力例 1

100 110 111 110

この入力中の木は次のようなものです。

各操作で、頂点のカウンターの値は次のように変化します。

操作 1: 頂点 2 を根とする部分木に含まれるすべての頂点、すなわち頂点 2, 3, 4 のカウンターの値に 10 を足す。頂点 1, 2, 3, 4 のカウンターの値はそれぞれ 0, 10, 10, 10 となる。
操作 2: 頂点 1 を根とする部分木に含まれるすべての頂点、すなわち頂点 1, 2, 3, 4 のカウンターの値に 100 を足す。頂点 1, 2, 3, 4 のカウンターの値はそれぞれ 100, 110, 110, 110 となる。
操作 3: 頂点 3 を根とする部分木に含まれるすべての頂点、すなわち頂点 3 のカウンターの値に 1 を足す。頂点 1, 2, 3, 4 のカウンターの値はそれぞれ 100, 110, 111, 110 となる。

入力例 2

出力例 2

20 20 20 20 20 20

Score : 400 points

Problem Statement

Given is a rooted tree with N vertices numbered 1 to N. The root is Vertex 1, and the i-th edge (1 \leq i \leq N - 1) connects Vertex a_i and b_i.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value 0.

Now, the following Q operations will be performed:

Operation j (1 \leq j \leq Q): Increment by x_j the counter on every vertex contained in the subtree rooted at Vertex p_j.

Find the value of the counter on each vertex after all operations.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq a_i < b_i \leq N
1 \leq p_j \leq N
1 \leq x_j \leq 10^4
The given graph is a tree.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

Output

Print the values of the counters on Vertex 1, 2, \ldots, N after all operations, in this order, with spaces in between.

Sample Input 1

Sample Output 1

100 110 111 110

The tree in this input is as follows:

Each operation changes the values of the counters on the vertices as follows:

Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 0, 10, 10, 10, respectively.
Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1, 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 110, 110, respectively.
Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 111, 110, respectively.

Sample Input 2

Sample Output 2

20 20 20 20 20 20

E - Strings of Impurity

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

英小文字からなる二つの文字列 s, t が与えられます。次の条件を満たす整数 i (1 \leq i \leq 10^{100} \times |s|) が存在するか判定し、存在する場合はそのような i の最小値を求めてください。

s を 10^{100} 個連結して得られる文字列を s' とする。t は、文字列 {s'}_1{s'}_2\ldots{s'}_i (s' の先頭 i 文字) の部分列である。

注記

文字列 a の部分列とは、a から 0 文字以上を削除して残った文字を相対的な順序を保ったまま連結して得られる文字列です。例えば、contest の部分列には net, c, contest などがあります。

制約

1 \leq |s| \leq 10^5
1 \leq |t| \leq 10^5
s, t は英小文字からなる。

入力

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

s
t

出力

条件を満たす整数 i が存在する場合はそのような i の最小値を、存在しない場合は -1 を出力せよ。

入力例 1

contest
son

出力例 1

t = son は文字列 contestcon (s' = contestcontestcontest... の先頭 10 文字) の部分列であるため、i = 10 は条件を満たします。

一方で、t は文字列 contestco (s' の先頭 9 文字) の部分列ではないため、i = 9 は条件を満たしません。

同様に、8 以下の任意の整数も条件を満たしません。よって、条件を満たす整数 i の最小値は 10 です。

入力例 2

contest
programming

出力例 2

-1

t = programming は s' = contestcontestcontest... の部分列ではありません。よって、条件を満たす整数 i は存在しません。

入力例 3

contest
sentence

出力例 3

ここにそのようなケースを置くことはできませんが、答えは 32 bit 整数に収まらない可能性があるのでご注意ください。

Score : 500 points

Problem Statement

Given are two strings s and t consisting of lowercase English letters. Determine if there exists an integer i satisfying the following condition, and find the minimum such i if it exists.

Let s' be the concatenation of 10^{100} copies of s. t is a subsequence of the string {s'}_1{s'}_2\ldots{s'}_i (the first i characters in s').

Notes

A subsequence of a string a is a string obtained by deleting zero or more characters from a and concatenating the remaining characters without changing the relative order. For example, the subsequences of contest include net, c, and contest.

Constraints

1 \leq |s| \leq 10^5
1 \leq |t| \leq 10^5
s and t consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

s
t

Output

If there exists an integer i satisfying the following condition, print the minimum such i; otherwise, print -1.

Sample Input 1

contest
son

Sample Output 1

t = son is a subsequence of the string contestcon (the first 10 characters in s' = contestcontestcontest...), so i = 10 satisfies the condition.

On the other hand, t is not a subsequence of the string contestco (the first 9 characters in s'), so i = 9 does not satisfy the condition.

Similarly, any integer less than 9 does not satisfy the condition, either. Thus, the minimum integer i satisfying the condition is 10.

Sample Input 2

contest
programming

Sample Output 2

-1

t = programming is not a substring of s' = contestcontestcontest.... Thus, there is no integer i satisfying the condition.

Sample Input 3

contest
sentence

Sample Output 3

Note that the answer may not fit into a 32-bit integer type, though we cannot put such a case here.

F - Coincidence

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

整数 L, R が与えられます。整数の組 (x, y) (L \leq x \leq y \leq R) であって、y を x で割った余りが y \text{ XOR } x に等しいものの個数を 10^9 + 7 で割ったあまりを求めてください。

\text{ XOR } とは

整数 A, B のビットごとの排他的論理和 a \text{ XOR } b は、以下のように定義されます。

a \text{ XOR } b を二進数表記した際の 2^k (k \geq 0) の位の数は、A, B を二進数表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。

例えば、3 \text{ XOR } 5 = 6 となります (二進数表記すると: 011 \text{ XOR } 101 = 110)。

制約

1 \leq L \leq R \leq 10^{18}

入力

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

L R

出力

条件を満たす整数の組 (x, y) (L \leq x \leq y \leq R) の個数を 10^9 + 7 で割ったあまりを出力せよ。

入力例 1

2 3

出力例 1

条件を満たす組は (2, 2), (2, 3), (3, 3) の 3 通りです。

入力例 2

10 100

出力例 2

入力例 3

1 1000000000000000000

出力例 3

68038601

個数を 10^9 + 7 で割ったあまりを計算することを忘れないでください。

Score : 600 points

Problem Statement

Given are integers L and R. Find the number, modulo 10^9 + 7, of pairs of integers (x, y) (L \leq x \leq y \leq R) such that the remainder when y is divided by x is equal to y \text{ XOR } x.

What is \text{ XOR }?

The XOR of integers A and B, A \text{ XOR } B, is defined as follows:

When A \text{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.

For example, 3 \text{ XOR } 5 = 6. (In base two: 011 \text{ XOR } 101 = 110.)

Constraints

1 \leq L \leq R \leq 10^{18}

Input

Input is given from Standard Input in the following format:

L R

Output

Print the number of pairs of integers (x, y) (L \leq x \leq y \leq R) satisfying the condition, modulo 10^9 + 7.

Sample Input 1

2 3

Sample Output 1

Three pairs satisfy the condition: (2, 2), (2, 3), and (3, 3).

Sample Input 2

10 100

Sample Output 2

Sample Input 3

1 1000000000000000000

Sample Output 3

68038601

Be sure to compute the number modulo 10^9 + 7.