Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
サンタさんに手紙を出したい高橋くんは、 X 円切手が 1 枚だけ貼られた封筒を用意しました。
サンタさんに手紙を届けるためには、貼られている切手の総額が Y 円以上である必要があります。
高橋くんは、この封筒に 10 円切手を何枚か貼り足すことで、貼られている切手の総額を Y 円以上にしたいです。
高橋くんはこの封筒に、最小で何枚の 10 円切手を貼り足す必要がありますか?
制約
- X,Y は整数
- 1 \le X,Y \le 1000
入力
入力は以下の形式で標準入力から与えられる。
X Y
出力
答えを整数として出力せよ。
入力例 1
80 94
出力例 1
2
- 80 円切手に 0 枚の 10 円切手を貼り足せば総額が 80 円となり、これは手紙を届けるのに必要な 94 円未満です。
- 80 円切手に 1 枚の 10 円切手を貼り足せば総額が 90 円となり、これは手紙を届けるのに必要な 94 円未満です。
- 80 円切手に 2 枚の 10 円切手を貼り足せば総額が 100 円となり、これは手紙を届けるのに必要な 94 円以上です。
入力例 2
1000 63
出力例 2
0
もともと貼られている切手だけで金額が十分である可能性もあります。
入力例 3
270 750
出力例 3
48
Score : 100 points
Problem Statement
Takahashi wants to send a letter to Santa Claus. He has an envelope with an X-yen (Japanese currency) stamp stuck on it.
To be delivered to Santa Claus, the envelope must have stamps in a total value of at least Y yen.
Takahashi will put some more 10-yen stamps so that the envelope will have stamps worth at least Y yen in total.
At least how many more 10-yen stamps does Takahashi need to put on the envelope?
Constraints
- X and Y are integers.
- 1 \le X,Y \le 1000
Input
Input is given from Standard Input in the following format:
X Y
Output
Print the answer as an integer.
Sample Input 1
80 94
Sample Output 1
2
- After adding zero 10-yen stamps to the 80-yen stamp, the total is 80 yen, which is less than the required amount of 94 yen.
- After adding one 10-yen stamp to the 80-yen stamp, the total is 90 yen, which is less than the required amount of 94 yen.
- After adding two 10-yen stamps to the 80-yen stamp, the total is 100 yen, which is not less than the required amount of 94 yen.
Sample Input 2
1000 63
Sample Output 2
0
The envelope may already have a stamp with enough value.
Sample Input 3
270 750
Sample Output 3
48
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
整数 L,R と、英小文字のみからなる文字列 S が与えられます。
S の L 文字目から R 文字目までの部分を反転した(すなわち、 L 文字目から R 文字目までの文字の並びを逆にした)文字列を出力してください。
制約
- S は英小文字のみからなる。
- 1 \le |S| \le 10^5 (|S| は S の長さ)
- L,R は整数
- 1 \le L \le R \le |S|
入力
入力は以下の形式で標準入力から与えられる。
L R S
出力
問題文の指示通り出力せよ。
入力例 1
3 7 abcdefgh
出力例 1
abgfedch
abcdefgh の 3 文字目から 7 文字目までの部分を反転すると、 abgfedch となります。
入力例 2
1 7 reviver
出力例 2
reviver
操作を行った結果が元の文字列と同一であることもあります。
入力例 3
4 13 merrychristmas
出力例 3
meramtsirhcyrs
Score : 200 points
Problem Statement
You are given integers L, R, and a string S consisting of lowercase English letters.
Print this string after reversing (the order of) the L-th through R-th characters.
Constraints
- S consists of lowercase English letters.
- 1 \le |S| \le 10^5 (|S| is the length of S.)
- L and R are integers.
- 1 \le L \le R \le |S|
Input
Input is given from Standard Input in the following format:
L R S
Output
Print the specified string.
Sample Input 1
3 7 abcdefgh
Sample Output 1
abgfedch
After reversing the 3-rd through 7-th characters of abcdefgh, we have abgfedch.
Sample Input 2
1 7 reviver
Sample Output 2
reviver
The operation may result in the same string as the original.
Sample Input 3
4 13 merrychristmas
Sample Output 3
meramtsirhcyrs
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 個の袋があります。
袋 i には L_i 個のボールが入っていて、袋 i の j(1\leq j\leq L_i) 番目のボールには正の整数 a_{i,j} が書かれています。
それぞれの袋から 1 つずつボールを取り出します。
取り出したボールに書かれた数の総積が X になるような取り出し方は何通りありますか？
ただし、書かれた数が同じであっても全てのボールは区別します。
制約
- N \geq 2
- L_i \geq 2
- 袋に入っているボールの個数の総積は 10^5 を超えない。すなわち、\displaystyle\prod_{i=1}^{N}L_i \leq 10^5
- 1 \leq a_{i,j} \leq 10^9
- 1 \leq X \leq 10^{18}
- 入力に含まれる値は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N X
L_1 a_{1,1} a_{1,2} \ldots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \ldots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \ldots a_{N,L_N}
出力
答えを出力せよ。
入力例 1
2 40 3 1 8 4 2 10 5
出力例 1
2
袋 1 の 3 番目のボールと袋 2 の 1 番目のボールを選ぶと、a_{1,3} \times a_{2,1} = 4 \times 10 = 40 となります。
袋 1 の 2 番目のボールと袋 2 の 2 番目のボールを選ぶと、a_{1,2} \times a_{2,2} = 8 \times 5 = 40 となります。
これ以外に総積が 40 になる取り出し方は存在しないので、答えは 2 です。
入力例 2
3 200 3 10 10 10 3 10 10 10 5 2 2 2 2 2
出力例 2
45
書かれた数が同じであっても全てのボールは区別することに注意してください。
入力例 3
3 1000000000000000000 2 1000000000 1000000000 2 1000000000 1000000000 2 1000000000 1000000000
出力例 3
0
総積が X になる取り出し方が 1 つも存在しないこともあります。
Score : 300 points
Problem Statement
We have N bags.
Bag i contains L_i balls. The j-th ball (1\leq j\leq L_i) in Bag i has a positive integer a_{i,j} written on it.
We will pick out one ball from each bag.
How many ways are there to pick the balls so that the product of the numbers written on the picked balls is X?
Here, we distinguish all balls, even with the same numbers written on them.
Constraints
- N \geq 2
- L_i \geq 2
- The product of the numbers of balls in the bags is at most 10^5: \displaystyle\prod_{i=1}^{N}L_i \leq 10^5.
- 1 \leq a_{i,j} \leq 10^9
- 1 \leq X \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X
L_1 a_{1,1} a_{1,2} \ldots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \ldots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \ldots a_{N,L_N}
Output
Print the answer.
Sample Input 1
2 40 3 1 8 4 2 10 5
Sample Output 1
2
When choosing the 3-rd ball in Bag 1 and 1-st ball in Bag 2, we have a_{1,3} \times a_{2,1} = 4 \times 10 = 40.
When choosing the 2-nd ball in Bag 1 and 2-nd ball in Bag 2, we have a_{1,2} \times a_{2,2} = 8 \times 5 = 40.
There are no other ways to make the product 40, so the answer is 2.
Sample Input 2
3 200 3 10 10 10 3 10 10 10 5 2 2 2 2 2
Sample Output 2
45
Note that we distinguish all balls, even with the same numbers written on them.
Sample Input 3
3 1000000000000000000 2 1000000000 1000000000 2 1000000000 1000000000 2 1000000000 1000000000
Sample Output 3
0
There may be no way to make the product X.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の数列 A=(A_1,A_2,\ldots,A_N) と、整数 K が与えられます。
A の連続部分列のうち、要素の和が K になるものはいくつありますか？
すなわち、以下の条件を全て満たす整数の組 (l,r) はいくつありますか？
- 1\leq l\leq r\leq N
- \displaystyle\sum_{i=l}^{r}A_i = K
制約
- 1\leq N \leq 2\times 10^5
- |A_i| \leq 10^9
- |K| \leq 10^{15}
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
6 5 8 -3 5 7 0 -4
出力例 1
3
(l,r)=(1,2),(3,3),(2,6) の 3 組が条件を満たします。
入力例 2
2 -1000000000000000 1000000000 -1000000000
出力例 2
0
条件を満たす (l,r) の組が 1 つも存在しないこともあります。
Score : 400 points
Problem Statement
Given is a sequence of length N: A=(A_1,A_2,\ldots,A_N), and an integer K.
How many of the contiguous subsequences of A have the sum of K?
In other words, how many pairs of integers (l,r) satisfy all of the conditions below?
- 1\leq l\leq r\leq N
- \displaystyle\sum_{i=l}^{r}A_i = K
Constraints
- 1\leq N \leq 2\times 10^5
- |A_i| \leq 10^9
- |K| \leq 10^{15}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
6 5 8 -3 5 7 0 -4
Sample Output 1
3
(l,r)=(1,2),(3,3),(2,6) are the three pairs that satisfy the conditions.
Sample Input 2
2 -1000000000000000 1000000000 -1000000000
Sample Output 2
0
There may be no pair that satisfies the conditions.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
\displaystyle \sum_{k=0}^{10^{100}} \left \lfloor \frac{X}{10^k} \right \rfloor を求めてください。
注釈
\lfloor A \rfloor は、 A の小数点以下を切り捨てた値を指します。
制約
- X は整数
- 1 \le X < 10^{500000}
入力
入力は以下の形式で標準入力から与えられる。
X
出力
答えを整数として出力せよ。
但し、たとえ答えが大きな整数であっても、求める答えを正確に整数として出力する必要がある。たとえば、 2.33e+21 のような指数表記や、 0523 のような先頭に不要な 0 を付けたような表記は許されない。
入力例 1
1225
出力例 1
1360
求める値は、 1225+122+12+1+0+0+\dots+0=1360 となります。
入力例 2
99999
出力例 2
111105
繰り上がりに注意してください。
入力例 3
314159265358979323846264338327950288419716939937510
出力例 3
349065850398865915384738153697722542688574377708317
入力される値も出力すべき値も非常に大きくなる場合があります。
Score : 500 points
Problem Statement
Find \displaystyle \sum_{k=0}^{10^{100}} \left \lfloor \frac{X}{10^k} \right \rfloor.
Notes
\lfloor A \rfloor denotes the value of A truncated to an integer.
Constraints
- X is an integer.
- 1 \le X < 10^{500000}
Input
Input is given from Standard Input in the following format:
X
Output
Print the answer as an integer.
Here, the answer must be precisely printed as an integer, even if it is large. It is not allowed to use exponential notation, such as 2.33e+21, or print unnecessary leading zeros, as in 0523.
Sample Input 1
1225
Sample Output 1
1360
The value we seek is 1225+122+12+1+0+0+\dots+0=1360.
Sample Input 2
99999
Sample Output 2
111105
Beware of carries.
Sample Input 3
314159265358979323846264338327950288419716939937510
Sample Output 3
349065850398865915384738153697722542688574377708317
The values in input and output can both be enormous.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
(1,2,\ldots,N) を並び替えた長さ N の順列 P=(P_1,P_2,\ldots,P_N) があります。
あなたが可能な操作は M 種類あり、操作 i は「 P の a_i 番目の要素と P の b_i 番目の要素を入れ替える」というものです。
操作を好きな順序で、合計 5\times 10^5 回以下行うことによって、P を昇順に並び替えることはできますか？
できるならば、操作手順を 1 つ教えてください。できないならばその旨を伝えてください。
制約
- 2\leq N \leq 1000
- P は (1,2,\ldots,N) を並び替えた順列
- 1\leq M \leq \min(2\times 10^5, \frac{N(N-1)}{2})
- 1\leq a_i \lt b_i\leq N
- i\neq j ならば (a_i,b_i)\neq (a_j,b_j)
- 入力に含まれる値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \ldots P_N M a_1 b_1 a_2 b_2 \vdots a_M b_M
出力
P を昇順に並び替えることができるならば以下の形式で出力せよ。
K c_1 c_2 \ldots c_K
ここで、K は操作の回数を表し、c_i(1\leq i \leq K) は i 回目に行う操作が操作 c_i であることを表す。
0\leq K \leq 5\times 10^5 を満たさなければならないことに注意せよ。
P を昇順に並び替えることができないならば、-1 と出力せよ。
入力例 1
6 5 3 2 4 6 1 4 1 5 5 6 1 2 2 3
出力例 1
3 4 2 1
P は、(5,3,2,4,6,1)\to (5,2,3,4,6,1)\to (5,2,3,4,1,6)\to (1,2,3,4,5,6) と変化します。
入力例 2
5 3 4 1 2 5 2 1 3 2 5
出力例 2
-1
P を昇順に並び替えることはできません。
入力例 3
4 1 2 3 4 6 1 2 1 3 1 4 2 3 2 4 3 4
出力例 3
0
初めから P が昇順に並んでいることもあります。
また、以下のような答えも正解になります。
4 5 5 5 5
操作の回数を最小化する必要はないことに注意してください。
Score : 500 points
Problem Statement
We have a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).
There are M kinds of operations available to you. Operation i swaps the a_i-th and b_i-th elements of P.
Is it possible to sort P in ascending order by doing at most 5\times 10^5 operations in total in any order?
If it is possible, give one such sequence of operations. Otherwise, report so.
Constraints
- 2\leq N \leq 1000
- P is a permutation of (1,2,\ldots,N).
- 1\leq M \leq \min(2\times 10^5, \frac{N(N-1)}{2})
- 1\leq a_i \lt b_i\leq N
- (a_i,b_i)\neq (a_j,b_j) if i\neq j.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N M a_1 b_1 a_2 b_2 \vdots a_M b_M
Output
If it is possible to sort P in ascending order, print the following:
K c_1 c_2 \ldots c_K
Here, K represents the number of operations to do, and c_i (1\leq i \leq K) means the i-th operation to do is Operation c_i.
Note that 0\leq K \leq 5\times 10^5 must hold.
If it is impossible to sort P in ascending order, print -1.
Sample Input 1
6 5 3 2 4 6 1 4 1 5 5 6 1 2 2 3
Sample Output 1
3 4 2 1
P changes as follows: (5,3,2,4,6,1)\to (5,2,3,4,6,1)\to (5,2,3,4,1,6)\to (1,2,3,4,5,6).
Sample Input 2
5 3 4 1 2 5 2 1 3 2 5
Sample Output 2
-1
We cannot sort P in ascending order.
Sample Input 3
4 1 2 3 4 6 1 2 1 3 1 4 2 3 2 4 3 4
Sample Output 3
0
P may already be sorted in ascending order.
Additionally, here is another accepted output:
4 5 5 5 5
Note that it is not required to minimize the number of operations.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N \times N のグリッドがあり、いくつかのマスにはブロックが置いてあります。
グリッドの情報は N 個の文字列 S_1,S_2,\dots,S_N によって以下の形式で与えられます。
- S_i の j 文字目が
#のとき、グリッドの上から i マス目、左から j マス目にブロックがある。 - S_i の j 文字目が
.のとき、グリッドの上から i マス目、左から j マス目にブロックがない。
高橋くんは、以下の操作を 0 回以上好きなだけ行うことができます。
- まず、 1 以上 N 以下の整数 D と、グリッド内の D \times D の部分正方形を選ぶ。
- その後、体力 D を消費して部分正方形内のブロックをすべて破壊する。
高橋くんがすべてのブロックを破壊するのに必要な体力の最小値を求めてください。
制約
- N は整数
- 1 \le N \le 50
- S_i は
#と.のみからなる - |S_i|=N
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを整数として出力せよ。
入力例 1
5 ##... .##.. #.#.. ..... ....#
出力例 1
4
以下の部分正方形を選ぶことで、消費する体力を 4 にすることができ、これが最適です。
- 上から 1 マス目、左から 1 マス目を左上とした、 3 \times 3 の部分正方形
- 上から 5 マス目、左から 5 マス目を左上とした、 1 \times 1 の部分正方形
入力例 2
3 ... ... ...
出力例 2
0
グリッドにブロックが 1 つもない場合もあります。
入力例 3
21 ..................... ..................... ...#.#............... ....#.............#.. ...#.#...........#.#. ..................#.. ..................... ..................... ..................... ..........#.....#.... ......#..###......... ........#####..#..... .......#######....... .....#..#####........ .......#######....... ......#########...... .......#######..#.... ......#########...... ..#..###########..... .........###......... .........###.........
出力例 3
19
Score : 600 points
Problem Statement
There is a N \times N grid, with blocks on some squares.
The grid is described by N strings S_1,S_2,\dots,S_N, as follows.
- If the j-th character of S_i is
#, there is a block on the square at the i-th row from the top and j-th column from the left. - If the j-th character of S_i is
., there is not a block on the square at the i-th row from the top and j-th column from the left.
Takahashi can do the operation below zero or more times.
- First, choose an integer D between 1 and N (inclusive), and a D \times D subsquare within the grid.
- Then, consume D stamina points to destroy all blocks within the subsquare.
Find the minimum number of stamina points needed to destroy all the blocks.
Constraints
- N is an integer.
- 1 \le N \le 50
- S_i consists of
#and.. - |S_i|=N
Input
Input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the answer as an integer.
Sample Input 1
5 ##... .##.. #.#.. ..... ....#
Sample Output 1
4
By choosing the subsquares below, Takahashi will consume 4 stamina points, which is optimal.
- The 3 \times 3 subsquare whose top-left square is at the 1-st row from the top and 1-st column from the left.
- The 1 \times 1 subsquare whose top-left square is at the 5-th row from the top and 5-th column from the left.
Sample Input 2
3 ... ... ...
Sample Output 2
0
There may be no block on the grid.
Sample Input 3
21 ..................... ..................... ...#.#............... ....#.............#.. ...#.#...........#.#. ..................#.. ..................... ..................... ..................... ..........#.....#.... ......#..###......... ........#####..#..... .......#######....... .....#..#####........ .......#######....... ......#########...... .......#######..#.... ......#########...... ..#..###########..... .........###......... .........###.........
Sample Output 3
19
Time Limit: 7 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
2 次元平面上にクリスマスツリーが N 個あり、i 個目のクリスマスツリーは座標 (x_i,y_i) にあります。
以下の Q 個のクエリに答えてください。
クエリ i ： (a_i,b_i) からマンハッタン距離で K_i 番目に近いクリスマスツリーまでの距離はいくつですか？
制約
- 1\leq N \leq 10^5
- 0\leq x_i\leq 10^5
- 0\leq y_i\leq 10^5
- i\neq j ならば (x_i,y_i) \neq (x_j,y_j)
- 1\leq Q \leq 10^5
- 0\leq a_i\leq 10^5
- 0\leq b_i\leq 10^5
- 1\leq K_i\leq N
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 \vdots x_N y_N Q a_1 b_1 K_1 \vdots a_Q b_Q K_Q
出力
Q 行に出力せよ。
i 行目には、クエリ i に対する答えを出力せよ。
入力例 1
4 3 3 4 6 7 4 2 5 6 3 5 1 3 5 2 3 5 3 3 5 4 100 200 3 300 200 1
出力例 1
1 2 2 5 293 489
(3,5) から 1,2,3,4 個目のクリスマスツリーまでのマンハッタン距離は、それぞれ 2,2,5,1 です。
よって、最初の 4 つのクエリの答えはそれぞれ 1,2,2,5 です。
Score : 600 points
Problem Statement
There are N Christmas trees in the two-dimensional plane. The i-th tree is at coordinates (x_i,y_i).
Answer the following Q queries.
Query i: What is the distance between (a_i,b_i) and the K_i-th nearest Christmas tree to that point, measured in Manhattan distance?
Constraints
- 1\leq N \leq 10^5
- 0\leq x_i\leq 10^5
- 0\leq y_i\leq 10^5
- (x_i,y_i) \neq (x_j,y_j) if i\neq j.
- 1\leq Q \leq 10^5
- 0\leq a_i\leq 10^5
- 0\leq b_i\leq 10^5
- 1\leq K_i\leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N x_1 y_1 \vdots x_N y_N Q a_1 b_1 K_1 \vdots a_Q b_Q K_Q
Output
Print Q lines.
The i-th line should contain the answer to Query i.
Sample Input 1
4 3 3 4 6 7 4 2 5 6 3 5 1 3 5 2 3 5 3 3 5 4 100 200 3 300 200 1
Sample Output 1
1 2 2 5 293 489
The distances from (3,5) to the 1-st, 2-nd, 3-rd, 4-th trees to that point are 2, 2, 5, 1, respectively.
Thus, the answers to the first four queries are 1, 2, 2, 5, respectively.