Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
整数 A,B が K 進法表記で与えられます。
A \times B を 10 進法表記で出力してください。
注記
K 進法表記については、Wikipedia「位取り記数法」 を参照してください。
制約
- 2 \leq K \leq 10
- 1 \leq A,B \leq 10^5
- A,B は K 進法表記で与えられる
入力
入力は以下の形式で標準入力から与えられる。
K A B
出力
答えを出力せよ。
入力例 1
2 1011 10100
出力例 1
220
2 進法表記の 1011 を 、10 進法表記すると 11 です。
2 進法表記の 10100 を、 10 進法表記すると 20 です。
11 \times 20 = 220 なので 220 を出力します。
入力例 2
7 123 456
出力例 2
15642
7 進法表記の 123 を 、10 進法表記すると 66 です。
7 進法表記の 456 を、 10 進法表記すると 237 です。
66 \times 237 = 15642 なので 15642 を出力します。
Score : 200 points
Problem Statement
You are given integers A and B, in base K.
Print A \times B in decimal.
Notes
For base-K representation, see Wikipedia's article on Positional notation.
Constraints
- 2 \leq K \leq 10
- 1 \leq A,B \leq 10^5
- A and B are in base-K representation.
Input
Input is given from Standard Input in the following format:
K A B
Output
Print the answer.
Sample Input 1
2 1011 10100
Sample Output 1
220
1011 in base 2 corresponds to 11 in base 10.
10100 in base 2 corresponds to 20 in base 10.
We have 11 \times 20 = 220, so print 220.
Sample Input 2
7 123 456
Sample Output 2
15642
123 in base 7 corresponds to 66 in base 10.
456 in base 7 corresponds to 237 in base 10.
We have 66 \times 237 = 15642, so print 15642.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
0 と 1 からなる長さ 64 の数列 A=(A_0,A_1,\dots,A_{63}) が与えられます。
A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} を求めてください。
制約
- A_i は 0 または 1
入力
入力は以下の形式で標準入力から与えられる。
A_0 A_1 \dots A_{63}
出力
答えを整数として出力せよ。
入力例 1
1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力例 1
13
A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13 です。
入力例 2
1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0
出力例 2
766067858140017173
Score : 200 points
Problem Statement
You are given a sequence A=(A_0,A_1,\dots,A_{63}) of length 64 consisting of 0 and 1.
Find A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63}.
Constraints
- A_i is 0 or 1.
Input
The input is given from Standard Input in the following format:
A_0 A_1 \dots A_{63}
Output
Print the answer as an integer.
Sample Input 1
1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample Output 1
13
A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13.
Sample Input 2
1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0
Sample Output 2
766067858140017173
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
正の整数 L に対して、 レベル L のダンゴ文字列とは、以下の条件を満たす文字列です。
oと-からなる長さ L+1 の文字列である。- 先頭の文字と末尾の文字のうちちょうど一方が
-であり、そのほかの L 文字はすべてoである。
例えば、ooo- はレベル 3 のダンゴ文字列ですが、-ooo- や oo や o-oo- などはダンゴ文字列ではありません(より正確には、どのような正の整数 L に対してもレベル L のダンゴ文字列ではありません)。
2 種類の文字 o - からなる、長さ N の文字列 S が与えられます。
次の条件を満たすような正整数 X のうち、最大のものを求めてください。
- S の連続する部分文字列であって、レベル X のダンゴ文字列であるものが存在する。
ただし、そのような整数が存在しない場合、-1 と出力してください。
制約
- 1\leq N\leq 2\times10^5
- S は
o-からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
S にレベル X のダンゴ文字列が含まれるような最大の X の値を 1 行で出力せよ。
そのような値が存在しない場合、-1 を出力せよ。
入力例 1
10 o-oooo---o
出力例 1
4
たとえば、S の 3 文字目から 7 文字目までに対応する部分文字列 oooo- は、レベル 4 のダンゴ文字列です。
S の部分文字列であってレベル 5 以上のダンゴ文字列であるようなものは存在しないため、4 と出力してください。
入力例 2
1 -
出力例 2
-1
S の連続する部分文字列は空文字列と - の 2 種類だけです。
これらはダンゴ文字列ではないため、-1 と出力してください。
入力例 3
30 -o-o-oooo-oo-o-ooooooo--oooo-o
出力例 3
7
Score : 300 points
Problem Statement
For a positive integer L, a level-L dango string is a string that satisfies the following conditions.
- It is a string of length L+1 consisting of
oand-. - Exactly one of the first character and the last character is
-, and the other L characters areo.
For instance, ooo- is a level-3 dango string, but none of -ooo-, oo, and o-oo- is a dango string (more precisely, none of them is a level-L dango string for any positive integer L).
You are given a string S of length N consisting of the two characters o and -.
Find the greatest positive integer X that satisfies the following condition.
- There is a contiguous substring of S that is a level-X dango string.
If there is no such integer, print -1.
Constraints
- 1\leq N\leq 2\times10^5
- S is a string of length N consisting of
oand-.
Input
The input is given from Standard Input in the following format:
N S
Output
Print the greatest positive integer X such that S contains a level-X dango string, or -1 if there is no such integer.
Sample Input 1
10 o-oooo---o
Sample Output 1
4
For instance, the substring oooo- corresponding to the 3-rd through 7-th characters of S is a level-4 dango string.
No substring of S is a level-5 dango string or above, so you should print 4.
Sample Input 2
1 -
Sample Output 2
-1
Only the empty string and - are the substrings of S.
They are not dango strings, so you should print -1.
Sample Input 3
30 -o-o-oooo-oo-o-ooooooo--oooo-o
Sample Output 3
7
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 点
問題文
H \times W 枚のクッキーが H 行 W 列に並んでいます。
上から i 行目・左から j 列目のクッキーの色は英小文字 c_{i,j} で表されます。
これから、以下の手続きを行います。
1. 各行に対して次の操作を行う : その行に 2 枚以上のクッキーが残っており、それらの色がすべて同じならば、それらに印をつける。
2. 各列に対して次の操作を行う : その列に 2 枚以上のクッキーが残っており、それらの色がすべて同じならば、それらに印をつける。
3. 印のついたクッキーがあればそれらをすべて取り除いて 1. に戻り、なければ手続きを終了する。
手続きを終了した時点で残っているクッキーの枚数を求めてください。
制約
- 2 \leq H, W \leq 2000
- c_{i,j} は英小文字である
入力
入力は以下の形式で標準入力から与えられる。
H W
c_{1,1}c_{1,2} \ldots c_{1,W}
c_{2,1}c_{2,2} \ldots c_{2,W}
\vdots
c_{H,1}c_{H,2} \ldots c_{H,W}
出力
答えを出力せよ。
入力例 1
4 3 aaa aaa abc abd
出力例 1
2
以下で示す順で手続きを行います。
- 1. により、1, 2 行目のクッキーに印をつける。
- 2. により、1 列目のクッキーに印をつける。
- 3. により、印を付けたクッキーを取り除く。
この時点でクッキーは以下のようになっています。ただし、クッキーを取り除いた箇所は . で表しています。
... ... .bc .bd
- 1. により、何もしない。
- 2. により、2 列目のクッキーに印をつける。
- 3. により、印を付けたクッキーを取り除く。
この時点でクッキーは以下のようになっています。ただし、クッキーを取り除いた箇所は . で表しています。
... ... ..c ..d
- 1. により、何もしない。
- 2. により、何もしない。
- 3. により、印がついているクッキーが存在しないので手続きを終了する。
最終的に残っているクッキーの枚数は 2 枚です。
入力例 2
2 5 aaaaa abcde
出力例 2
4
入力例 3
3 3 ooo ooo ooo
出力例 3
0
Score : 400 points
Problem Statement
There are H \times W cookies in H rows and W columns.
The color of the cookie at the i-row from the top and j-th column from the left is represented by a lowercase English letter c_{i,j}.
We will perform the following procedure.
1. For each row, perform the following operation: if there are two or more cookies remaining in the row and they all have the same color, mark them.
2. For each column, perform the following operation: if there are two or more cookies remaining in the column and they all have the same color, mark them.
3. If there are any marked cookies, remove them all and return to 1; otherwise, terminate the procedure.
Find the number of cookies remaining at the end of the procedure.
Constraints
- 2 \leq H, W \leq 2000
- c_{i,j} is a lowercase English letter.
Input
The input is given from Standard Input in the following format:
H W
c_{1,1}c_{1,2} \ldots c_{1,W}
c_{2,1}c_{2,2} \ldots c_{2,W}
\vdots
c_{H,1}c_{H,2} \ldots c_{H,W}
Output
Print the answer.
Sample Input 1
4 3 aaa aaa abc abd
Sample Output 1
2
The procedure is performed as follows.
- 1. Mark the cookies in the first and second rows.
- 2. Mark the cookies in the first column.
- 3. Remove the marked cookies.
At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.
... ... .bc .bd
- 1. Do nothing.
- 2. Mark the cookies in the second column.
- 3. Remove the marked cookies.
At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.
... ... ..c ..d
- 1. Do nothing.
- 2. Do nothing.
- 3. No cookies are marked, so terminate the procedure.
The final number of cookies remaining is 2.
Sample Input 2
2 5 aaaaa abcde
Sample Output 2
4
Sample Input 3
3 3 ooo ooo ooo
Sample Output 3
0