AtCoder Beginner Contest 162

A - Lucky 7

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

3 桁の整数 N が与えられます。N のいずれかの桁に数字の 7 は含まれますか？

含まれるなら Yes を、含まれないなら No を出力してください。

制約

100 \leq N \leq 999

入力

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

出力

N のいずれかの桁に 7 が含まれるなら Yes を、含まれないなら No を出力せよ。

入力例 1

出力例 1

Yes

117 は 1 の位が 7 です。

入力例 2

出力例 2

No

123 は 7 を含みません。

入力例 3

出力例 3

Yes

Score : 100 points

Problem Statement

Given is a three-digit integer N. Does N contain the digit 7?

If so, print Yes; otherwise, print No.

Constraints

100 \leq N \leq 999

Input

Input is given from Standard Input in the following format:

Output

If N contains the digit 7, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

117 contains 7 as its last digit.

Sample Input 2

Sample Output 2

No

123 does not contain the digit 7.

Sample Input 3

Sample Output 3

Yes

B - FizzBuzz Sum

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

FizzBuzz列 a_1,a_2,... を次のように定めます。

i が 3 でも 5 でも割り切れるなら、a_i=\text{FizzBuzz}
そうではなく i が 3 で割り切れるなら、a_i=\text{Fizz}
そうではなく i が 5 で割り切れるなら、a_i=\text{Buzz}
そうではないなら、a_i=i

FizzBuzz列の N 項目までに含まれる数の和を求めてください。

制約

1 \leq N \leq 10^6

入力

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

出力

FizzBuzz列の N 項目までに含まれる数の和を出力せよ。

入力例 1

出力例 1

FizzBuzz列の 15 項目までは次の通りです。

1,2,\text{Fizz},4,\text{Buzz},\text{Fizz},7,8,\text{Fizz},\text{Buzz},11,\text{Fizz},13,14,\text{FizzBuzz}

15 項目までには 1,2,4,7,8,11,13,14 が含まれ、これらの和は 60 です。

入力例 2

出力例 2

266666333332

オーバーフローに注意してください。

Score : 200 points

Problem Statement

Let us define the FizzBuzz sequence a_1,a_2,... as follows:

If both 3 and 5 divides i, a_i=\text{FizzBuzz}.
If the above does not hold but 3 divides i, a_i=\text{Fizz}.
If none of the above holds but 5 divides i, a_i=\text{Buzz}.
If none of the above holds, a_i=i.

Find the sum of all numbers among the first N terms of the FizzBuzz sequence.

Constraints

1 \leq N \leq 10^6

Input

Input is given from Standard Input in the following format:

Output

Print the sum of all numbers among the first N terms of the FizzBuzz sequence.

Sample Input 1

Sample Output 1

The first 15 terms of the FizzBuzz sequence are:

1,2,\text{Fizz},4,\text{Buzz},\text{Fizz},7,8,\text{Fizz},\text{Buzz},11,\text{Fizz},13,14,\text{FizzBuzz}

Among them, numbers are 1,2,4,7,8,11,13,14, and the sum of them is 60.

Sample Input 2

Sample Output 2

266666333332

Watch out for overflow.

C - Sum of gcd of Tuples (Easy)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

\displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)} を求めてください。

ただし、\gcd(a,b,c) は a,b,c の最大公約数を表します。

制約

1 \leq K \leq 200
K は整数

入力

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

出力

\displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)} の値を出力せよ。

入力例 1

出力例 1

\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2) +\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2) =1+1+1+1+1+1+1+2=9

となるため、答えは 9 です。

入力例 2

出力例 2

10813692

Score : 300 points

Problem Statement

Find \displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}.

Here \gcd(a,b,c) denotes the greatest common divisor of a, b, and c.

Constraints

1 \leq K \leq 200
K is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the value of \displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}.

Sample Input 1

Sample Output 1

\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2) +\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2) =1+1+1+1+1+1+1+2=9

Thus, the answer is 9.

Sample Input 2

Sample Output 2

10813692

D - RGB Triplets

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

R, G, B のみからなる、長さ N の文字列 S があります。

以下の 2 つの条件をともに満たす組 (i,~j,~k)~(1 \leq i < j < k \leq N) の数を求めてください。

S_i \neq S_j かつ S_i \neq S_k かつ S_j \neq S_k である
j - i \neq k - j である

制約

1 \leq N \leq 4000
S は R, G, B のみからなる、長さ N の文字列である

入力

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

N
S

出力

題意を満たす組の数を出力せよ。

入力例 1

4
RRGB

出力例 1

組 (1,~3,~4) だけが 2 つの条件をともに満たします。組 (2,~3,~4) は、1 つ目の条件は満たしますが 2 つ目の条件を満たさないので不適です。

入力例 2

39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB

出力例 2

Score : 400 points

Problem Statement

We have a string S of length N consisting of R, G, and B.

Find the number of triples (i,~j,~k)~(1 \leq i < j < k \leq N) that satisfy both of the following conditions:

S_i \neq S_j, S_i \neq S_k, and S_j \neq S_k.
j - i \neq k - j.

Constraints

1 \leq N \leq 4000
S is a string of length N consisting of R, G, and B.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the number of triplets in question.

Sample Input 1

4
RRGB

Sample Output 1

Only the triplet (1,~3,~4) satisfies both conditions. The triplet (2,~3,~4) satisfies the first condition but not the second, so it does not count.

Sample Input 2

39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB

Sample Output 2

E - Sum of gcd of Tuples (Hard)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

1 以上 K 以下の整数からなる長さ N の数列 \{A_1,...,A_N\} を考えます。

そのようなものは K^N 個ありますが、その全てについての \gcd(A_1,...,A_N) の和を求めてください。

ただし、答えは非常に大きくなる可能性があるため、和を (10^9+7) で割ったあまりを出力してください。

なお、\gcd(A_1,...,A_N) は A_1,...,A_N の最大公約数を表します。

制約

2 \leq N \leq 10^5
1 \leq K \leq 10^5
入力は全て整数

入力

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

N K

出力

K^N 個の数列全てについての \gcd(A_1,...,A_N) の和を (10^9+7) で割ったあまりを出力せよ。

入力例 1

3 2

出力例 1

\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2) +\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2) =1+1+1+1+1+1+1+2=9

となるため、答えは 9 です。

入力例 2

3 200

出力例 2

10813692

入力例 3

100000 100000

出力例 3

742202979

和を 10^9+7 で割った余りを出力してください。

Score : 500 points

Problem Statement

Consider sequences \{A_1,...,A_N\} of length N consisting of integers between 1 and K (inclusive).

There are K^N such sequences. Find the sum of \gcd(A_1, ..., A_N) over all of them.

Since this sum can be enormous, print the value modulo (10^9+7).

Here \gcd(A_1, ..., A_N) denotes the greatest common divisor of A_1, ..., A_N.

Constraints

2 \leq N \leq 10^5
1 \leq K \leq 10^5
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print the sum of \gcd(A_1, ..., A_N) over all K^N sequences, modulo (10^9+7).

Sample Input 1

3 2

Sample Output 1

\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2) +\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2) =1+1+1+1+1+1+1+2=9

Thus, the answer is 9.

Sample Input 2

3 200

Sample Output 2

10813692

Sample Input 3

100000 100000

Sample Output 3

742202979

Be sure to print the sum modulo (10^9+7).

F - Select Half

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

長さ N の整数列 A_1,...,A_N が与えられます。

この中からちょうど \left\lfloor \frac{N}{2} \right\rfloor 個の整数を、どの 2 箇所も連続しないように選びます。

選んだ要素の和としてありえる最大値を求めてください。

ここで、\lfloor x \rfloor は、x を超えない最大の整数を表します。

制約

2 \leq N \leq 2\times 10^5
|A_i|\leq 10^9
入力は全て整数

入力

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

N
A_1 ... A_N

出力

選ばれた要素の和としてありえる最大値を出力せよ。

入力例 1

6
1 2 3 4 5 6

出力例 1

2,4,6 を選ぶと和は 12 となり、これが最大です。

入力例 2

5
-1000 -100 -10 0 10

出力例 2

-10,10 を選ぶと和は 0 となり、これが最大です。

入力例 3

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

5000000000

オーバーフローに注意してください。

入力例 4

27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49

出力例 4

Score : 600 points

Problem Statement

Given is an integer sequence A_1, ..., A_N of length N.

We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.

Find the maximum possible sum of the chosen elements.

Here \lfloor x \rfloor denotes the greatest integer not greater than x.

Constraints

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

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the maximum possible sum of the chosen elements.

Sample Input 1

6
1 2 3 4 5 6

Sample Output 1

Choosing 2, 4, and 6 makes the sum 12, which is the maximum possible value.

Sample Input 2

5
-1000 -100 -10 0 10

Sample Output 2

Choosing -10 and 10 makes the sum 0, which is the maximum possible value.

Sample Input 3

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5000000000

Watch out for overflow.

Sample Input 4

27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49