Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
1 から N の番号がついた N 人の人がいます。
人 i はキーエンス本社ビルの建築面積を S_i 平方メートルであると予想しました。
キーエンス本社ビルは下図のような形をしています。ただし、a,b はある 正の整数 です。
つまり、キーエンス本社ビルの建築面積は 4ab+3a+3b 平方メートルと表されます。
N 人のうち、この情報のみによって、予想した面積が確実に誤りであるとわかる人数を求めてください。
制約
- 1 \leq N \leq 20
- 1 \leq S_i \leq 1000
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N S_1 \ldots S_N
出力
答えを出力せよ。
入力例 1
3 10 20 39
出力例 1
1
a=1,b=1 のとき面積は 10 平方メートル、a=2,b=3 のとき面積は 39 平方メートルとなります。
しかし a,b がどのような正の整数であったとしても面積が 20 平方メートルになることはありません。
よって、人 2 の予想だけは確実に誤りであることがわかります。
入力例 2
5 666 777 888 777 666
出力例 2
3
Score : 200 points
Problem Statement
There are N people numbered 1 to N.
Person i guessed the building area of KEYENCE headquarters building to be S_i square meters.
The shape of KEYENCE headquarters building is shown below, where a and b are some positive integers.
That is, the building area of the building can be represented as 4ab+3a+3b.
Based on just this information, how many of the N people are guaranteed to be wrong in their guesses?
Constraints
- 1 \leq N \leq 20
- 1 \leq S_i \leq 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N S_1 \ldots S_N
Output
Print the answer.
Sample Input 1
3 10 20 39
Sample Output 1
1
The area would be 10 square meters if a=1,b=1, and 39 square meters if a=2,b=3.
However, no pair of positive integers a and b would make the area 20 square meters.
Thus, we can only be sure that Person 2 guessed wrong.
Sample Input 2
5 666 777 888 777 666
Sample Output 2
3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。
各マスの状態は文字 C_{i,j} で表されます。C_{i,j} が . ならば (i, j) には何も置かれておらず、 # ならば箱が 1 個置かれています。
1 \leq j \leq W を満たす整数 j に対して、整数 X_j を次のように定義します。
- j 列目に置かれている箱の個数。言い換えると、C_{i,j} が
#であるような整数 i の個数。
X_1, X_2, \dots, X_W をすべて求めてください。
制約
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- H, W は整数
- C_{i, j} は
.または#
入力
入力は以下の形式で標準入力から与えられる。
H W
C_{1,1}C_{1,2}\dots C_{1,W}
C_{2,1}C_{2,2}\dots C_{2,W}
\vdots
C_{H,1}C_{H,2}\dots C_{H,W}
出力
X_1, X_2, \dots, X_W を以下の形式に従って出力せよ。
X_1 X_2 \dots X_W
入力例 1
3 4 #..# .#.# .#.#
出力例 1
1 2 0 3
1 列目の箱が置かれているマスは (1, 1) の 1 ヵ所です。よって X_1 = 1 です。
2 列目の箱が置かれているマスは (2, 2), (3, 2) の 2 ヵ所です。よって X_2 = 2 です。
3 列目の箱が置かれているマスは存在しません。よって X_3 = 0 です。
4 列目の箱が置かれているマスは (1, 4), (2, 4), (3, 4) の 3 ヵ所です。よって X_4 = 3 です。
よって (X_1, X_2, X_3, X_4) = (1, 2, 0, 3) が答えとなります。
入力例 2
3 7 ....... ....... .......
出力例 2
0 0 0 0 0 0 0
箱が置かれているマスが存在しない場合もあります。
入力例 3
8 3 .#. ### .#. .#. .## ..# ##. .##
出力例 3
2 7 4
入力例 4
5 47 .#..#..#####..#...#..#####..#...#...###...##### .#.#...#.......#.#...#......##..#..#...#..#.... .##....#####....#....#####..#.#.#..#......##### .#.#...#........#....#......#..##..#...#..#.... .#..#..#####....#....#####..#...#...###...#####
出力例 4
0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3
Score : 200 points
Problem Statement
There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The squares are described by characters C_{i,j}. If C_{i,j} is ., (i, j) is empty; if it is #, (i, j) contains a box.
For integers j satisfying 1 \leq j \leq W, let the integer X_j defined as follows.
- X_j is the number of boxes in the j-th column. In other words, X_j is the number of integers i such that C_{i,j} is
#.
Find all of X_1, X_2, \dots, X_W.
Constraints
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- H and W are integers.
- C_{i, j} is
.or#.
Input
The input is given from Standard Input in the following format:
H W
C_{1,1}C_{1,2}\dots C_{1,W}
C_{2,1}C_{2,2}\dots C_{2,W}
\vdots
C_{H,1}C_{H,2}\dots C_{H,W}
Output
Print X_1, X_2, \dots, X_W in the following format:
X_1 X_2 \dots X_W
Sample Input 1
3 4 #..# .#.# .#.#
Sample Output 1
1 2 0 3
In the 1-st column, one square, (1, 1), contains a box. Thus, X_1 = 1.
In the 2-nd column, two squares, (2, 2) and (3, 2), contain a box. Thus, X_2 = 2.
In the 3-rd column, no squares contain a box. Thus, X_3 = 0.
In the 4-th column, three squares, (1, 4), (2, 4), and (3, 4), contain a box. Thus, X_4 = 3.
Therefore, the answer is (X_1, X_2, X_3, X_4) = (1, 2, 0, 3).
Sample Input 2
3 7 ....... ....... .......
Sample Output 2
0 0 0 0 0 0 0
There may be no square that contains a box.
Sample Input 3
8 3 .#. ### .#. .#. .## ..# ##. .##
Sample Output 3
2 7 4
Sample Input 4
5 47 .#..#..#####..#...#..#####..#...#...###...##### .#.#...#.......#.#...#......##..#..#...#..#.... .##....#####....#....#####..#.#.#..#......##### .#.#...#........#....#......#..##..#...#..#.... .#..#..#####....#....#####..#...#...###...#####
Sample Output 4
0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は、レジ打ちの仕事をしています。
レジの機械には 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 の 11 個のボタンがあります。
レジの機械には、はじめ 0 が表示されています。
ボタン 00 を押すと、表示されている数が 100 倍されます。
それ以外のボタンを押すと、表示されている数が 10 倍されたあとに、押されたボタンに書かれている数が加算されます。
高橋君は、レジに整数 S を表示させたいです。 レジに S が表示されている状態にするためには、少なくとも何回ボタンを押す必要があるか求めてください。
制約
- 1\leq S\leq 10^{100000}
- S は整数
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを 1 行で出力せよ。
入力例 1
40004
出力例 1
4
例えば、次のように操作することでボタンを 4 回押して 40004 を表示させることができます。 はじめ、レジには 0 が表示されています。
- ボタン
4を押す。レジに表示されている数は 4 となる。 - ボタン
00を押す。レジに表示されている数は 400 となる。 - ボタン
0を押す。レジに表示されている数は 4000 となる。 - ボタン
4を押す。レジに表示されている数は 40004 となる。
3 回までボタンを押すことでレジに 40004 を表示させることはできないので、出力すべき値は 4 です。
入力例 2
1355506027
出力例 2
10
入力例 3
10888869450418352160768000001
出力例 3
27
S は 64\operatorname{bit} 整数に収まらない場合があることに注意してください。
Score : 300 points
Problem Statement
Takahashi is a cashier.
There is a cash register with 11 keys: 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.
The cash register initially displays 0.
Whenever he types the key 00, the displayed number is multiplied by 100;
whenever he types one of the others, the displayed number is multiplied by 10, and then added by the number written on the key.
Takahashi wants the cash register to display an integer S. At least how many keystrokes are required to make it display S?
Constraints
- 1\leq S\leq 10^{100000}
- S is an integer.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer in a line.
Sample Input 1
40004
Sample Output 1
4
For example, the following four keystrokes make the cash register display 40004. Initially, the cash register displays 0.
- Type the key
4. It now displays 4. - Type the key
00. It now displays 400. - Type the key
0. It now displays 4000. - Type the key
4. It now displays 40004.
He cannot make it display 40004 with three or fewer keystrokes, so 4 should be printed.
Sample Input 2
1355506027
Sample Output 2
10
Sample Input 3
10888869450418352160768000001
Sample Output 3
27
Note that S may not fit into a 64-\operatorname{bit} integer type.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 個の商品があります。i = 1, 2, \ldots, N について、i 番目の商品の値段は A_i 円です。
高橋君は K 枚のクーポンを持っています。
1 枚のクーポンは 1 つの商品に対して使用することができ、1 つの商品に対してはクーポンを何枚でも（ 0 枚でもよい）使用することができます。
値段が a 円の商品に対して k 枚のクーポンを使用すると、その商品を \max\lbrace a - kX, 0\rbrace 円で買うことができます。
高橋君がすべての商品を買うために支払う合計金額の最小値を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K, X \leq 10^9
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K X A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
5 4 7 8 3 10 5 13
出力例 1
12
1 番目の商品に対してクーポン 1 枚、3 番目の商品に対してクーポン 1 枚、5 番目の商品に対してクーポン 2 枚を使用すると、
- 1 番目の商品を \max\lbrace A_1-X, 0 \rbrace = 1 円で買うことができ、
- 2 番目の商品を \max\lbrace A_2, 0 \rbrace = 3 円で買うことができ、
- 3 番目の商品を \max\lbrace A_3-X, 0 \rbrace = 3 円で買うことができ、
- 4 番目の商品を \max\lbrace A_4, 0 \rbrace = 5 円で買うことができ、
- 5 番目の商品を \max\lbrace A_5-2X, 0 \rbrace = 0 円で買うことができます。
よって、すべての商品を 1 + 3 + 3 + 5 + 0 = 12 円で買うことができ、これが最小です。
入力例 2
5 100 7 8 3 10 5 13
出力例 2
0
入力例 3
20 815 60 2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202
出力例 3
112
Score : 300 points
Problem Statement
There are N items in a shop. For each i = 1, 2, \ldots, N, the price of the i-th item is A_i yen (the currency of Japan).
Takahashi has K coupons.
Each coupon can be used on one item. You can use any number of coupons, possibly zero, on the same item. Using k coupons on an item with a price of a yen allows you to buy it for \max\lbrace a - kX, 0\rbrace yen.
Print the minimum amount of money Takahashi needs to buy all the items.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K, X \leq 10^9
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K X A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
5 4 7 8 3 10 5 13
Sample Output 1
12
By using 1 coupon on the 1-st item, 1 coupon on the 3-rd item, and 2 coupons on the 5-th item, Takahashi can:
- buy the 1-st item for \max\lbrace A_1-X, 0 \rbrace = 1 yen,
- buy the 2-nd item for \max\lbrace A_2, 0 \rbrace = 3 yen,
- buy the 3-rd item for \max\lbrace A_3-X, 0 \rbrace = 3 yen,
- buy the 4-th item for \max\lbrace A_4, 0 \rbrace = 5 yen,
- buy the 5-th item for \max\lbrace A_5-2X, 0 \rbrace = 0 yen,
for a total of 1 + 3 + 3 + 5 + 0 = 12 yen, which is the minimum possible.
Sample Input 2
5 100 7 8 3 10 5 13
Sample Output 2
0
Sample Input 3
20 815 60 2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202
Sample Output 3
112
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
長さ N の整数列 A = (A_1, A_2, \ldots, A_N) と正整数 K が与えられます。
各 i = 1, 2, \ldots, Q について、A の連続部分列 (A_{l_i}, A_{l_i+1}, \ldots, A_{r_i}) が良い数列かどうかを判定してください。
ここで、長さ n の数列 X = (X_1, X_2, \ldots, X_n) は、下記の操作を好きな回数（ 0 回でも良い）だけ行うことによって、X のすべての要素を 0 にすることができるとき、かつ、そのときに限り良い数列です。
1 \leq i \leq n-K+1 を満たす整数 i および、整数 c （負の数でも良い）を選び、K 個の要素 X_{i}, X_{i+1}, \ldots, X_{i+K-1} のそれぞれに c を加算する。
なお、すべての i = 1, 2, \ldots, Q について、r_i - l_i + 1 \geq K が保証されます。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq \min\lbrace 10, N \rbrace
- -10^9 \leq A_i \leq 10^9
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq l_i, r_i \leq N
- r_i-l_i+1 \geq K
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N Q l_1 r_1 l_2 r_2 \vdots l_Q r_Q
出力
Q 行出力せよ。
i = 1, 2, \ldots, Q について、i 行目には数列 (A_{l_i}, A_{l_i+1}, \ldots, A_{r_i}) が良い数列である場合は Yes を、
そうでない場合は No を出力せよ。
入力例 1
7 3 3 -1 1 -2 2 0 5 2 1 6 2 7
出力例 1
Yes No
数列 X \coloneqq (A_1, A_2, A_3, A_4, A_5, A_6) = (3, -1, 1, -2, 2, 0) は良い数列です。 実際、下記の手順で操作を行うことで、すべての要素を 0 にすることができます。
- まず、i = 2, c = 4 として操作を行う。その結果、X = (3, 3, 5, 2, 2, 0) となる。
- 次に、i = 3, c = -2 として操作を行う。その結果、X = (3, 3, 3, 0, 0, 0) となる。
- 最後に、i = 1, c = -3 として操作を行う。その結果、X = (0, 0, 0, 0, 0, 0) となる。
よって、1 行目には Yes を出力します。
一方、数列 (A_2, A_3, A_4, A_5, A_6, A_7) = (-1, 1, -2, 2, 0, 5) は、
どのような手順で操作を行ってもすべての要素を 0 にすることはできないため、良い数列ではありません。
よって、2 行目には No を出力します。
入力例 2
20 4 -19 -66 -99 16 18 33 32 28 26 11 12 0 -16 4 21 21 37 17 55 -19 5 13 16 4 11 3 12 13 18 4 10
出力例 2
No Yes No Yes No
Score : 400 points
Problem Statement
You are given an integer sequence of length N, A = (A_1, A_2, \ldots, A_N), and a positive integer K.
For each i = 1, 2, \ldots, Q, determine whether a contiguous subsequence of A, (A_{l_i}, A_{l_i+1}, \ldots, A_{r_i}), is a good sequence.
Here, a sequence of length n, X = (X_1, X_2, \ldots, X_n), is good if and only if there is a way to perform the operation below some number of times (possibly zero) to make all elements of X equal 0.
Choose an integer i such that 1 \leq i \leq n-K+1 and an integer c (possibly negative). Add c to each of the K elements X_{i}, X_{i+1}, \ldots, X_{i+K-1}.
It is guaranteed that r_i - l_i + 1 \geq K for every i = 1, 2, \ldots, Q.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq \min\lbrace 10, N \rbrace
- -10^9 \leq A_i \leq 10^9
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq l_i, r_i \leq N
- r_i-l_i+1 \geq K
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N Q l_1 r_1 l_2 r_2 \vdots l_Q r_Q
Output
Print Q lines.
For each i = 1, 2, \ldots, Q, the i-th line should contain Yes if the sequence (A_{l_i}, A_{l_i+1}, \ldots, A_{r_i}) is good, and No otherwise.
Sample Input 1
7 3 3 -1 1 -2 2 0 5 2 1 6 2 7
Sample Output 1
Yes No
The sequence X \coloneqq (A_1, A_2, A_3, A_4, A_5, A_6) = (3, -1, 1, -2, 2, 0) is good. Indeed, you can do the following to make all elements equal 0.
- First, do the operation with i = 2, c = 4, making X = (3, 3, 5, 2, 2, 0).
- Next, do the operation with i = 3, c = -2, making X = (3, 3, 3, 0, 0, 0).
- Finally, do the operation with i = 1, c = -3, making X = (0, 0, 0, 0, 0, 0).
Thus, the first line should contain Yes.
On the other hand, for the sequence (A_2, A_3, A_4, A_5, A_6, A_7) = (-1, 1, -2, 2, 0, 5), there is no way to make all elements equal 0, so it is not a good sequence.
Thus, the second line should contain No.
Sample Input 2
20 4 -19 -66 -99 16 18 33 32 28 26 11 12 0 -16 4 21 21 37 17 55 -19 5 13 16 4 11 3 12 13 18 4 10
Sample Output 2
No Yes No Yes No