AtCoder Beginner Contest 150

A - 500 Yen Coins

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

高橋君は 500 円玉を K 枚持っています。これらの総額が X 円以上である場合は Yes を、そうでない場合は No を出力してください。

制約

1 ≤ K ≤ 100
1 ≤ X ≤ 10^5

入力

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

K X

出力

総額が X 円以上である場合は Yes を、そうでない場合は No を出力せよ。

入力例 1

2 900

出力例 1

Yes

500 円玉が 2 枚なので総額は 1000 円であり、これは X = 900 円以上です。

入力例 2

1 501

出力例 2

No

500 円玉が 1 枚なので総額は 500 円であり、これは X = 501 円未満です。

入力例 3

4 2000

出力例 3

Yes

500 円玉が 4 枚なので総額は 2000 円であり、これは X = 2000 円以上です。

Score : 100 points

Problem Statement

Takahashi has K 500-yen coins. (Yen is the currency of Japan.) If these coins add up to X yen or more, print Yes; otherwise, print No.

Constraints

1 \leq K \leq 100
1 \leq X \leq 10^5

Input

Input is given from Standard Input in the following format:

K X

Output

If the coins add up to X yen or more, print Yes; otherwise, print No.

Sample Input 1

2 900

Sample Output 1

Yes

Two 500-yen coins add up to 1000 yen, which is not less than X = 900 yen.

Sample Input 2

1 501

Sample Output 2

No

One 500-yen coin is worth 500 yen, which is less than X = 501 yen.

Sample Input 3

4 2000

Sample Output 3

Yes

Four 500-yen coins add up to 2000 yen, which is not less than X = 2000 yen.

B - Count ABC

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

英大文字のみからなる長さ N の文字列 S があります。

S の連続する部分列 (入出力例をご覧ください) として ABC がいくつ含まれるかを求めてください。

制約

3 \leq N \leq 50
S は英大文字のみからなる。

入力

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

N
S

出力

S が連続する部分列として含む ABC の個数を出力せよ。

入力例 1

10
ZABCDBABCQ

出力例 1

S の 2 文字目から 4 文字目、および 7 文字目から 9 文字目の 2 箇所の連続する部分列が ABC に一致しています。

入力例 2

19
THREEONEFOURONEFIVE

出力例 2

S は ABC に一致する連続する部分列を含みません。

入力例 3

33
ABCCABCBABCCABACBCBBABCBCBCBCABCB

出力例 3

Score : 200 points

Problem Statement

We have a string S of length N consisting of uppercase English letters.

How many times does ABC occur in S as contiguous subsequences (see Sample Inputs and Outputs)?

Constraints

3 \leq N \leq 50
S consists of uppercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print number of occurrences of ABC in S as contiguous subsequences.

Sample Input 1

10
ZABCDBABCQ

Sample Output 1

Two contiguous subsequences of S are equal to ABC: the 2-nd through 4-th characters, and the 7-th through 9-th characters.

Sample Input 2

19
THREEONEFOURONEFIVE

Sample Output 2

No contiguous subsequences of S are equal to ABC.

Sample Input 3

33
ABCCABCBABCCABACBCBBABCBCBCBCABCB

Sample Output 3

C - Count Order

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

大きさ N の順列 ((1,~2,~...,~N) を並び替えてできる数列) P,~Q があります。

大きさ N の順列は N! 通り考えられます。このうち、P が辞書順で a 番目に小さく、Q が辞書順で b 番目に小さいとして、|a - b| を求めてください。

注記

2 つの数列 X,~Y について、ある整数 k が存在して X_i = Y_i~(1 \leq i < k) かつ X_k < Y_k が成り立つとき、X は Y より辞書順で小さいと定義されます。

制約

2 \leq N \leq 8
P,~Q は大きさ N の順列である。
入力は全て整数である。

入力

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

N
P_1 P_2 ... P_N
Q_1 Q_2 ... Q_N

出力

|a - b| を出力せよ。

入力例 1

3
1 3 2
3 1 2

出力例 1

大きさ 3 の順列は、(1,~2,~3)、(1,~3,~2)、(2,~1,~3)、(2,~3,~1)、(3,~1,~2)、(3,~2,~1) の 6 個あります。このうち (1,~3,~2) は辞書順で 2 番目、(3,~1,~2) は辞書順で 5 番目なので、答えは |2 - 5| = 3 です。

入力例 2

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

出力例 2

入力例 3

3
1 2 3
1 2 3

出力例 3

Score : 300 points

Problem Statement

We have two permutations P and Q of size N (that is, P and Q are both rearrangements of (1,~2,~...,~N)).

There are N! possible permutations of size N. Among them, let P and Q be the a-th and b-th lexicographically smallest permutations, respectively. Find |a - b|.

Notes

For two sequences X and Y, X is said to be lexicographically smaller than Y if and only if there exists an integer k such that X_i = Y_i~(1 \leq i < k) and X_k < Y_k.

Constraints

2 \leq N \leq 8
P and Q are permutations of size N.

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 ... P_N
Q_1 Q_2 ... Q_N

Output

Print |a - b|.

Sample Input 1

3
1 3 2
3 1 2

Sample Output 1

There are 6 permutations of size 3: (1,~2,~3), (1,~3,~2), (2,~1,~3), (2,~3,~1), (3,~1,~2), and (3,~2,~1). Among them, (1,~3,~2) and (3,~1,~2) come 2-nd and 5-th in lexicographical order, so the answer is |2 - 5| = 3.

Sample Input 2

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

Sample Output 2

Sample Input 3

3
1 2 3
1 2 3

Sample Output 3

D - Semi Common Multiple

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

長さ N の偶数からなる正の整数列 A= {a_1,a_2,...,a_N} と、整数 M が与えられます。

任意の k(1 \leq k \leq N) に対して以下の条件を満たす正の整数 X を A の「半公倍数」と定義します。

X= a_k \times (p+0.5) を満たす負でない整数 p が存在する。

1 以上 M 以下の整数のうちの A の半公倍数の個数を求めてください。

制約

1 \leq N \leq 10^5
1 \leq M \leq 10^9
2 \leq a_i \leq 10^9
a_i は偶数である。
入力は全て整数である。

入力

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

N M
a_1 a_2 ... a_N

出力

1 以上 M 以下の整数のうちの A の半公倍数の個数を出力せよ。

入力例 1

2 50
6 10

出力例 1

15 = 6 \times 2.5
15 = 10 \times 1.5
45 = 6 \times 7.5
45 = 10 \times 4.5

より、15,45 は A の半公倍数です。1 以上 50 以下の整数に他に A の半公倍数はないので、答えは 2 となります。

入力例 2

3 100
14 22 40

出力例 2

答えが 0 の場合もあります。

入力例 3

5 1000000000
6 6 2 6 2

出力例 3

166666667

Score : 400 points

Problem Statement

Given are a sequence A= {a_1,a_2,......a_N} of N positive even numbers, and an integer M.

Let a semi-common multiple of A be a positive integer X that satisfies the following condition for every k (1 \leq k \leq N):

There exists a non-negative integer p such that X= a_k \times (p+0.5).

Find the number of semi-common multiples of A among the integers between 1 and M (inclusive).

Constraints

1 \leq N \leq 10^5
1 \leq M \leq 10^9
2 \leq a_i \leq 10^9
a_i is an even number.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
a_1 a_2 ... a_N

Output

Print the number of semi-common multiples of A among the integers between 1 and M (inclusive).

Sample Input 1

2 50
6 10

Sample Output 1

15 = 6 \times 2.5
15 = 10 \times 1.5
45 = 6 \times 7.5
45 = 10 \times 4.5

Thus, 15 and 45 are semi-common multiples of A. There are no other semi-common multiples of A between 1 and 50, so the answer is 2.

Sample Input 2

3 100
14 22 40

Sample Output 2

The answer can be 0.

Sample Input 3

5 1000000000
6 6 2 6 2

Sample Output 3

166666667

E - Change a Little Bit

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

0, 1 からなる長さ N の異なる 2 つの数列 S, T に対し、関数 f(S, T) を以下のように定めます。

S に対し以下の操作を繰り返して T と等しくすることを考える。このとき行う操作のコストの和として考えられる最小の値が f(S, T) である。
- S_i を (0 から 1、もしくは 1 から 0 に) 変更する。この操作のコストは、変更の直前に S_j \neq T_j (1 \leq j \leq N) であったような整数 j の個数を D として、D \times C_i である。

0, 1 からなる長さ N の異なる 2 つの数列の組 (S, T) は 2^N \times (2^N - 1) 通り考えられます。これらすべてに対する f(S, T) の和を 10^9+7 で割った余りを計算してください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq C_i \leq 10^9
入力は全て整数である

入力

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

N
C_1 C_2 \cdots C_N

出力

f(S, T) の和を 10^9+7 で割った余りを出力せよ。

入力例 1

1
1000000000

出力例 1

999999993

0, 1 からなる長さ 1 の異なる 2 つの数列の組 (S, T) は以下の 2 通りが考えられます。

S = (0), T = (1): S_1 を 1 に変更することでコスト 1000000000 で S = T とできるため、f(S, T) = 1000000000 です。
S = (1), T = (0): S_1 を 0 に変更することでコスト 1000000000 で S = T とできるため、f(S, T) = 1000000000 です。

これらの和は 2000000000 であり、これを 10^9+7 で割った余りは 999999993 です。

入力例 2

2
5 8

出力例 2

0, 1 からなる長さ 2 の異なる 2 つの数列の組 (S, T) は 12 通り存在し、例えば以下のものが考えられます。

S = (0, 1), T = (1, 0)

この場合、1 回目の操作で S_1 を 1 に変更し、2 回目の操作で S_2 を 0 に変更するとき、操作のコストの和は 5 \times 2 + 8 = 18 です。これより小さいコストで S = T とすることはできないので、f(S, T) = 18 です。

入力例 3

5
52 67 72 25 79

出力例 3

Score : 500 points

Problem Statement

For two sequences S and T of length N consisting of 0 and 1, let us define f(S, T) as follows:

Consider repeating the following operation on S so that S will be equal to T. f(S, T) is the minimum possible total cost of those operations.
- Change S_i (from 0 to 1 or vice versa). The cost of this operation is D \times C_i, where D is the number of integers j such that S_j \neq T_j (1 \leq j \leq N) just before this change.

There are 2^N \times (2^N - 1) pairs (S, T) of different sequences of length N consisting of 0 and 1. Compute the sum of f(S, T) over all of those pairs, modulo (10^9+7).

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq C_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
C_1 C_2 \cdots C_N

Output

Print the sum of f(S, T), modulo (10^9+7).

Sample Input 1

1
1000000000

Sample Output 1

999999993

There are two pairs (S, T) of different sequences of length 2 consisting of 0 and 1, as follows:

S = (0), T = (1): by changing S_1 to 1, we can have S = T at the cost of 1000000000, so f(S, T) = 1000000000.
S = (1), T = (0): by changing S_1 to 0, we can have S = T at the cost of 1000000000, so f(S, T) = 1000000000.

The sum of these is 2000000000, and we should print it modulo (10^9+7), that is, 999999993.

Sample Input 2

2
5 8

Sample Output 2

There are 12 pairs (S, T) of different sequences of length 3 consisting of 0 and 1, which include:

S = (0, 1), T = (1, 0)

In this case, if we first change S_1 to 1 then change S_2 to 0, the total cost is 5 \times 2 + 8 = 18. We cannot have S = T at a smaller cost, so f(S, T) = 18.

Sample Input 3

5
52 67 72 25 79

Sample Output 3

F - Xor Shift

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

非負整数からなる長さ N の数列 a=\{a_0,\ldots,a_{N-1}\} と b=\{b_0,\ldots,b_{N-1}\} が与えられます。

すぬけ君は 0 \leq k < N を満たす整数 k と、0 以上の整数 x を決めて、新しく長さ N の数列 a'=\{a_0',\ldots,a_{N-1}'\} を次のようにして作ります。

a_i'= a_{i+k \mod N}\ XOR \ x

a' が b と等しくなるような (k,x) の組を全て求めてください。

\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 N \leq 2 \times 10^5
0 \leq a_i,b_i < 2^{30}
入力中のすべての値は整数である。

入力

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

N
a_0 a_1 ... a_{N-1}
b_0 b_1 ... b_{N-1}

出力

a' と b が等しくなるような (k,x) の組を、1 行に 1 組ずつ、k の昇順 (k が等しいものは x の昇順) にすべて出力せよ。

このような組が存在しない場合の出力は空でよい。

入力例 1

3
0 2 1
1 2 3

出力例 1

1 3

(k,x)=(1,3) のとき、

a_0'=(a_1\ XOR \ 3)=1
a_1'=(a_2\ XOR \ 3)=2
a_2'=(a_0\ XOR \ 3)=3

となり、a' は b と等しくなります。

入力例 2

5
0 0 0 0 0
2 2 2 2 2

出力例 2

入力例 3

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

出力例 3

2 2
5 5

入力例 4

2
1 2
0 0

出力例 4

条件を満たすような組が存在しないこともあります。

Score : 600 points

Problem Statement

Given are two sequences a=\{a_0,\ldots,a_{N-1}\} and b=\{b_0,\ldots,b_{N-1}\} of N non-negative integers each.

Snuke will choose an integer k such that 0 \leq k < N and an integer x not less than 0, to make a new sequence of length N, a'=\{a_0',\ldots,a_{N-1}'\}, as follows:

a_i'= a_{i+k \mod N}\ XOR \ x

Find all pairs (k,x) such that a' will be equal to b.

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 N \leq 2 \times 10^5
0 \leq a_i,b_i < 2^{30}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_0 a_1 ... a_{N-1}
b_0 b_1 ... b_{N-1}

Output

Print all pairs (k, x) such that a' and b will be equal, using one line for each pair, in ascending order of k (ascending order of x for pairs with the same k).

If there are no such pairs, the output should be empty.

Sample Input 1

3
0 2 1
1 2 3

Sample Output 1

1 3

If (k,x)=(1,3),

a_0'=(a_1\ XOR \ 3)=1
a_1'=(a_2\ XOR \ 3)=2
a_2'=(a_0\ XOR \ 3)=3

and we have a' = b.

Sample Input 2

5
0 0 0 0 0
2 2 2 2 2

Sample Output 2

Sample Input 3

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

Sample Output 3

2 2
5 5

Sample Input 4

2
1 2
0 0

Sample Output 4

No pairs may satisfy the condition.