Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
西暦 N 年は何世紀ですか？
世紀とは？
西暦 1 年から 100 年までを 1 世紀、 101 年から 200 年までを 2 世紀と、以降も同様に西暦を 100 年単位で区切って呼称したものです。制約
- 1 \le N \le 3000
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
2021
出力例 1
21
今年、西暦 2021 年は 21 世紀です。
入力例 2
200
出力例 2
2
西暦 200 年は 2 世紀です。
Score : 100 points
Problem Statement
In what century is the year N?
What is century?
A century is a period of 100 years. For example, the 1-st century consists of the years 1 through 100, the 2-nd century consists of the years 101 through 200, and so on.Constraints
- 1 \le N \le 3000
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
2021
Sample Output 1
21
This year 2021 is in the 21-st century.
Sample Input 2
200
Sample Output 2
2
The year 200 is in the 2-nd century.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
整数 N が与えられます。
以下の操作を K 回行った後の整数 N を出力してください。
- 整数 N が 200 の倍数であれば、N を 200 で割る。
- そうでなければ、整数 N を、N の後ろに文字列として 200 を付け加えた整数に置き換える。
- 例えば、7 を置き換えると 7200 に、1234 を置き換えると 1234200 になります。
制約
- 入力は全て整数
- 1 \le N \le 10^5
- 1 \le K \le 20
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
答えを整数として出力せよ。
入力例 1
2021 4
出力例 1
50531
N=2021 に 4 回操作を行うと、N の値は操作を行うごとに 2021 \rightarrow 2021200 \rightarrow 10106 \rightarrow 10106200 \rightarrow 50531 となります。
入力例 2
40000 2
出力例 2
1
入力例 3
8691 20
出力例 3
84875488281
答えは 32 bit 符号付き整数型に収まらない可能性があります。
Score : 200 points
Problem Statement
You are given an integer N.
Do the following operation K times on it and print the resulting integer.
- If N is a multiple of 200, divide it by 200.
- Otherwise, see N as a string and append 200 to the end of it.
- For example, 7 would become 7200 and 1234 would become 1234200.
Constraints
- All values in input are integers.
- 1 \le N \le 10^5
- 1 \le K \le 20
Input
Input is given from Standard Input in the following format:
N K
Output
Print the answer as an integer.
Sample Input 1
2021 4
Sample Output 1
50531
Applying the operation on N=2021 results in N becoming 2021 \rightarrow 2021200 \rightarrow 10106 \rightarrow 10106200 \rightarrow 50531.
Sample Input 2
40000 2
Sample Output 2
1
Sample Input 3
8691 20
Sample Output 3
84875488281
The answer may not fit into the signed 32-bit integer type.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
200 という整数が大好きなりんごさんのために、次の問題を解いてください。
N 個の正整数からなる数列 A が与えられるので、以下の条件をすべて満たす整数の組 (i,j) の個数を求めてください。
- 1 \le i < j \le N
- A_i - A_j は 200 の倍数である。
制約
- 入力は全て整数
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
6 123 223 123 523 200 2000
出力例 1
4
例えば、(i, j) = (1, 3) のとき、A_1 - A_3 = 0 は 200 の倍数です。
(i,j)=(1,3),(1,4),(3,4),(5,6) の 4 つが条件を満たします。
入力例 2
5 1 2 3 4 5
出力例 2
0
条件を満たす組がひとつも無い場合があります。
入力例 3
8 199 100 200 400 300 500 600 200
出力例 3
9
Score : 300 points
Problem Statement
Ringo loves the integer 200. Solve the problem below for him.
Given a sequence A of N positive integers, find the pair of integers (i, j) satisfying all of the following conditions:
- 1 \le i < j \le N;
- A_i - A_j is a multiple of 200.
Constraints
- All values in input are integers.
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
6 123 223 123 523 200 2000
Sample Output 1
4
For example, for (i, j) = (1, 3), A_1 - A_3 = 0 is a multiple of 200.
We have four pairs satisfying the conditions: (i,j)=(1,3),(1,4),(3,4),(5,6).
Sample Input 2
5 1 2 3 4 5
Sample Output 2
0
There may be no pair satisfying the conditions.
Sample Input 3
8 199 100 200 400 300 500 600 200
Sample Output 3
9
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 個の正整数からなる数列 A = (A_1, A_2, \dots, A_N) が与えられます。 以下の条件を全て満たす 2 つの数列 B = (B_1, B_2, \dots, B_x),\ C = (C_1, C_2, \dots, C_y) が存在するか判定し、存在する場合はひとつ出力してください。
- 1 ≤ x, y ≤ N
- 1 \le B_1 < B_2 < \dots < B_{x} \le N
- 1 \le C_1 < C_2 < \dots < C_{y} \le N
- B と C は、異なる数列である。
- x ≠ y のとき、または、ある整数 i\ (1 ≤ i ≤ \min(x, y)) が存在して B_i ≠ C_i であるとき、B と C は異なるものとする。
- A_{B_1} + A_{B_2} + \dots + A_{B_x} を 200 で割った余りと A_{C_1} + A_{C_2} + \dots + A_{C_y} を 200 で割った余りが等しい。
制約
- 入力はすべて整数
- 2 \le N \le 200
- 1 \le A_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
条件を満たす数列の組 B,C が存在しない場合、1 行に No と出力せよ。
存在する場合、以下の形式で B,C を出力せよ。
Yes x B_1 B_2 \dots B_x y C_1 C_2 \dots C_y
なお、正誤判定器は英大文字と英小文字を区別せず、どちらも受理する。
入力例 1
5 180 186 189 191 218
出力例 1
Yes 1 1 2 3 4
B=(1),C=(3,4) とすると、A_1 = 180,\ A_3 + A_4 = 380 となり、この 2 つを 200 で割った余りは等しくなります。
他にも、以下のような出力も正答として扱われます。
yEs 4 2 3 4 5 3 1 2 5
入力例 2
2 123 523
出力例 2
Yes 1 1 1 2
入力例 3
6 2013 1012 2765 2021 508 6971
出力例 3
No
条件を満たす数列の組が存在しない場合、1 行に No と出力してください。
Score : 400 points
Problem Statement
You are given a sequence of N positive integers: A = (A_1, A_2, \dots, A_N). Determine whether there is a pair of sequences B = (B_1, B_2, \dots, B_x), C = (C_1, C_2, \dots, C_y) satisfying all of the conditions, and print one such pair if it exists.
- 1 ≤ x, y ≤ N.
- 1 \le B_1 < B_2 < \dots < B_{x} \le N.
- 1 \le C_1 < C_2 < \dots < C_{y} \le N.
- B and C are different sequences.
- Here, we consider B and C different when x ≠ y or there is an integer i\ (1 ≤ i ≤ \min(x, y)) such that B_i ≠ C_i.
- A_{B_1} + A_{B_2} + \dots + A_{B_x} and A_{C_1} + A_{C_2} + \dots + A_{C_y} are equal modulo 200.
Constraints
- All values in input are integers.
- 2 \le N \le 200
- 1 \le A_i \le 10^9
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
If there is no pair of sequences B, C satisfying the conditions, print a single line containing No.
Otherwise, print your choice of B and C in the following format:
Yes x B_1 B_2 \dots B_x y C_1 C_2 \dots C_y
The checker is case-insensitive: you can use either uppercase or lowercase letters.
Sample Input 1
5 180 186 189 191 218
Sample Output 1
Yes 1 1 2 3 4
For B=(1),C=(3,4), we have A_1 = 180,\ A_3 + A_4 = 380, which are equal modulo 200.
There are other solutions that will also be accepted, such as:
yEs 4 2 3 4 5 3 1 2 5
Sample Input 2
2 123 523
Sample Output 2
Yes 1 1 1 2
Sample Input 3
6 2013 1012 2765 2021 508 6971
Sample Output 3
No
If there is no pair of sequences satisfying the conditions, print a single line containing No.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
「ABC洋菓子店」で働くパティシエである高橋君は、ケーキを作って AtCoder Beginner Contest 200 を祝うことにしました。
高橋君の作るケーキは、「綺麗さ」「おいしさ」「人気度」の 3 つのパラメータをもち、それぞれのパラメータは 1 以上 N 以下の整数で表されます。
高橋君は、「綺麗さ」が i 、「おいしさ」が j 、「人気度」が k であるケーキを、全ての組 (i,j,k)\ (1 \le i,j,k \le N) に対して 1 つずつ作りました。
その後、高橋君は、できた N^3 個のケーキを以下の順序で並べました。
- 「綺麗さ」+「おいしさ」+「人気度」が小さいものを、より左に並べる。
- ここまでで順序がつかなければ、「綺麗さ」が小さいものを、より左に並べる。
- ここまでで順序がつかなければ、「おいしさ」が小さいものを、より左に並べる。
このとき、左から K 番目にあるケーキの各パラメータの値を求めてください。
制約
- 入力は全て整数
- 1 \le N \le 10^6
- 1 \le K \le N^3
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
答えを「綺麗さ」「おいしさ」「人気度」の順に空白区切りで 3 つの整数として出力せよ。
入力例 1
2 5
出力例 1
1 2 2
各ケーキの各パラメータの値を (「綺麗さ」,「おいしさ」,「人気度」) と書くと、ケーキは左から以下の順に並びます。
(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,1,2),(2,2,1),(2,2,2)
入力例 2
1000000 1000000000000000000
出力例 2
1000000 1000000 1000000
入力される値が大きくなることもあります。
入力例 3
9 47
出力例 3
3 1 4
Score : 500 points
Problem Statement
Takahashi, a pastry chef at ABC Confiserie, has decided to make cakes to celebrate AtCoder Beginner Contest 200.
A cake made by Takahashi has three parameters: beauty, taste, and popularity, each of which is represented by an integer between 1 and N (inclusive).
He has made a cake of beauty i, taste j, and popularity k for every triple (i,j,k)\ (1 \le i,j,k \le N).
Then, he has arranged these N^3 cakes in a row, as follows:
- The cakes are in ascending order of sum of beauty, taste, and popularity from left to right.
- For two cakes with the same sum of beauty, taste, and popularity, the cake with the smaller beauty is to the left.
- For two cakes with the same sum and the same beauty, the cake with the smaller taste is to the left.
Find the beauty, taste, and popularity of the K-th cake from the left.
Constraints
- All values in input are integers.
- 1 \le N \le 10^6
- 1 \le K \le N^3
Input
Input is given from Standard Input in the following format:
N K
Output
Print three integers representing the cake's beauty, taste, popularity, in this order, with spaces in between.
Sample Input 1
2 5
Sample Output 1
1 2 2
The cakes are in the following order:
(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,1,2),(2,2,1),(2,2,2).
Here, each triple of integers represents the beauty, taste, and popularity of a cake.
Sample Input 2
1000000 1000000000000000000
Sample Output 2
1000000 1000000 1000000
The values in input may be large.
Sample Input 3
9 47
Sample Output 3
3 1 4
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
0, 1, ? のみからなる文字列 S があります。この文字列を K 個連結したものを T とします。
この文字列の ? を全て 0 か 1 に置き換えた文字列は、S の中に含まれる ? の数を q 個とすると、全部で 2^{Kq} 通り考えられますが、その全てについて以下の問題を解いて、その答えの和を (10^9+7) で割った余りを求めてください。
?を置き換えた後の文字列を T' とします。T' に以下の操作を繰り返し行うことで全ての文字を同じにするとき、必要な最小の操作回数は何回ですか？
- 1 \le l \le r \le |T'| となる整数 l,r を選ぶ。そして、T' の l 文字目から r 文字目(両端含む)までの各文字を、
0であれば1に、1であれば0に変更する。
制約
- 1 \le |S| \le 10^5
- 1 \le K \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
S K
出力
答えを整数として出力せよ。
入力例 1
101 2
出力例 1
2
文字列 T= 101101 で、ここには ? が含まれません。よって、考えられる唯一の T'= 101101 についての答えを求めればよいです。
例えば、101101 \rightarrow 110011 \rightarrow 111111 と操作を行えば、 2 回で全ての文字列を同じにすることができます。
1 回以下の操作で全ての文字列を同じにすることはできません。
入力例 2
?0? 1
出力例 2
3
文字列 T' として考えられるものは 000, 001, 100, 101 の 4 通りです。
入力例 3
10111?10??1101??1?00?1?01??00010?0?1?? 998244353
出力例 3
235562598
答えは非常に大きくなることがあるので、 (10^9+7) で割った余りを求めてください。
Score : 600 points
Problem Statement
We have a string S consisting of 0, 1, and ?. Let T be the concatenation of K copies of S.
By replacing each ? in T with 0 or 1, we can obtain 2^{Kq} strings, where q is the number of ?s in S. Solve the problem below for each of these strings and find the sum of all the answers, modulo (10^9+7).
Let T' be the string obtained by replacing
?in T. We will repeatedly do the operation below to make all the characters in T the same. At least how many operations are needed for this?
- Choose integers l and r such that 1 \le l \le r \le |T'|, and invert the l-th through r-th characters of T: from
0and1and vice versa.
Constraints
- 1 \le |S| \le 10^5
- 1 \le K \le 10^9
Input
Input is given from Standard Input in the following format:
S K
Output
Print the answer as an integer.
Sample Input 1
101 2
Sample Output 1
2
We have T= 101101, which does not contain ?, so we just need to solve the problem for the only T'= 101101.
We can make all the characters the same in two operations as, for example, 101101 \rightarrow 110011 \rightarrow 111111.
We cannot make all the characters the same in one or fewer operations.
Sample Input 2
?0? 1
Sample Output 2
3
We have four candidates for T': 000, 001, 100, and 101.
Sample Input 3
10111?10??1101??1?00?1?01??00010?0?1?? 998244353
Sample Output 3
235562598
Since the answer can be enormous, find it modulo (10^9+7).