Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
高橋君は学校でゲームを楽しんでいます。チャイムが鳴ると同時にゲームが開始します。
高橋君はチャイムが鳴った直後から、以下の動作を繰り返し行います。
- 毎秒 S メートルの速さで A 秒間走る。その後の B 秒間は静止する。
チャイムが鳴ってから X 秒が経過するまでに、高橋君は合計何メートル走りますか?
制約
- 1 \leq S \leq 15
- 1 \leq A \leq 1000
- 1 \leq B \leq 1000
- 1 \leq X \leq 1000
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
S A B X
出力
答えを 1 行に出力せよ。単位 (メートル) は省いて出力すること。
入力例 1
7 3 2 11
出力例 1
49
チャイムが鳴ってからの 11 秒間、高橋君は以下のように動きます。
- 0 秒後から 3 秒後までのあいだ、高橋君は毎秒 7 メートルの速さで走る。このあいだの移動距離は 21 メートル。
- 3 秒後から 5 秒後までのあいだ、高橋君は静止する。
- 5 秒後から 8 秒後までのあいだ、高橋君は毎秒 7 メートルの速さで走る。このあいだの移動距離は 21 メートル。
- 8 秒後から 10 秒後までのあいだ、高橋君は静止する。
- 10 秒後から 11 秒後までのあいだ、高橋君は毎秒 7 メートルの速さで走る。このあいだの移動距離は 7 メートル。
総移動距離は 49 メートルなので、49 を出力します。
入力例 2
6 3 2 9
出力例 2
36
チャイムが鳴ってからの 9 秒間、高橋君は以下のように動きます。
- 0 秒後から 3 秒後までのあいだ、高橋君は毎秒 6 メートルの速さで走る。このあいだの移動距離は 18 メートル。
- 3 秒後から 5 秒後までのあいだ、高橋君は静止する。
- 5 秒後から 8 秒後までのあいだ、高橋君は毎秒 6 メートルの速さで走る。このあいだの移動距離は 18 メートル。
- 8 秒後から 9 秒後までのあいだ、高橋君は静止する。
総移動距離は 36 メートルなので、36 を出力します。
入力例 3
1 1 666 428
出力例 3
1
チャイムが鳴ってからの 428 秒間、高橋君は以下のように動きます。
- 0 秒後から 1 秒後までのあいだ、高橋君は毎秒 1 メートルの速さで走る。このあいだの移動距離は 1 メートル。
- 1 秒後から 428 秒後までのあいだ、高橋君は静止する。
総移動距離は 1 メートルなので、1 を出力します。
Score : 150 points
Problem Statement
Takahashi is enjoying a game at school. The game starts at the moment the bell rings.
Immediately after the bell rings, he repeats the following actions:
- Run at a speed of S meters per second for A seconds. Then, remain stationary for B seconds.
How many meters in total does he run by the time X seconds have elapsed since the bell rang?
Constraints
- 1 \leq S \leq 15
- 1 \leq A \leq 1000
- 1 \leq B \leq 1000
- 1 \leq X \leq 1000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
S A B X
Output
Output the answer in one line. Omit the unit (meters) in the output.
Sample Input 1
7 3 2 11
Sample Output 1
49
During the 11 seconds after the bell rings, Takahashi moves as follows:
- From 0 seconds to 3 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 21 meters.
- From 3 seconds to 5 seconds, he remains stationary.
- From 5 seconds to 8 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 21 meters.
- From 8 seconds to 10 seconds, he remains stationary.
- From 10 seconds to 11 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 7 meters.
The total distance traveled is 49 meters, so output 49.
Sample Input 2
6 3 2 9
Sample Output 2
36
During the 9 seconds after the bell rings, Takahashi moves as follows:
- From 0 seconds to 3 seconds, he runs at a speed of 6 meters per second. The distance traveled during this time is 18 meters.
- From 3 seconds to 5 seconds, he remains stationary.
- From 5 seconds to 8 seconds, he runs at a speed of 6 meters per second. The distance traveled during this time is 18 meters.
- From 8 seconds to 9 seconds, he remains stationary.
The total distance traveled is 36 meters, so output 36.
Sample Input 3
1 1 666 428
Sample Output 3
1
During the 428 seconds after the bell rings, Takahashi moves as follows:
- From 0 seconds to 1 second, he runs at a speed of 1 meter per second. The distance traveled during this time is 1 meter.
- From 1 second to 428 seconds, he remains stationary.
The total distance traveled is 1 meter, so output 1.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
長さ N の英小文字からなる文字列 S と英小文字 c_1,c_2 が与えられます。
S の文字のうち c_1 であるもの 以外 を全て c_2 に置き換えた文字列を求めてください。
制約
- 1\le N\le 100
- N は整数
- c_1,c_2 は英小文字
- S は英小文字からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N c_1 c_2 S
出力
答えを出力せよ。
入力例 1
3 b g abc
出力例 1
gbg
S= abc のうち、 b でない a と c を g に置き換えた結果 gbg になります。したがって、 gbg を出力してください。
入力例 2
1 s h s
出力例 2
s
置き換えた後の文字列が元の文字列と変わらない場合もあります。
入力例 3
7 d a atcoder
出力例 3
aaaadaa
入力例 4
10 b a acaabcabba
出力例 4
aaaabaabba
Score : 100 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters, along with lowercase English letters c_1 and c_2.
Find the string obtained by replacing every character of S that is not c_1 with c_2.
Constraints
- 1\le N\le 100
- N is an integer.
- c_1 and c_2 are lowercase English letters.
- S is a string of length N consisting of lowercase English letters.
Input
The input is given in the following format from Standard Input:
N c_1 c_2 S
Output
Print the answer.
Sample Input 1
3 b g abc
Sample Output 1
gbg
Replacing a and c (which are not b) with g in S= abc results in gbg, so print gbg.
Sample Input 2
1 s h s
Sample Output 2
s
It is possible that the resulting string after replacement is the same as the original string.
Sample Input 3
7 d a atcoder
Sample Output 3
aaaadaa
Sample Input 4
10 b a acaabcabba
Sample Output 4
aaaabaabba
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
整数 B が与えられます。
A^A = B であるような正の整数 A が存在するならばその値を、存在しないならば -1 を出力してください。
制約
- 1 \leq B \leq 10^{18}
- B は整数
入力
入力は以下の形式で標準入力から与えられる。
B
出力
A^A = B であるような正の整数 A が存在するならばその値を、存在しないならば -1 を出力せよ。
A^A = B を満たす正の整数 A が複数ある場合は、どれを出力しても正解とみなされる。
入力例 1
27
出力例 1
3
3^3 = 27 なので 3 を出力します。
入力例 2
100
出力例 2
-1
A^A = B を満たす A は存在しません。
入力例 3
10000000000
出力例 3
10
Score : 200 points
Problem Statement
You are given an integer B.
If there exists a positive integer A such that A^A = B, print its value; otherwise, output -1.
Constraints
- 1 \leq B \leq 10^{18}
- B is an integer.
Input
The input is given from Standard Input in the following format:
B
Output
If there exists a positive integer A such that A^A = B, print its value; otherwise, print -1.
If there are multiple positive integers A such that A^A = B, any of them will be accepted.
Sample Input 1
27
Sample Output 1
3
3^3 = 27, so print 3.
Sample Input 2
100
Sample Output 2
-1
There is no A such that A^A = B.
Sample Input 3
10000000000
Sample Output 3
10
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N 人の人がいます。i \, (1 \leq i \leq N) 人目の人の姓は S_i、名は T_i です。
同姓同名であるような人の組が存在するか、すなわち 1 \leq i \lt j \leq N かつ S_i=S_j かつ T_i=T_j を満たすような整数対 (i,j) が存在するか判定してください。
制約
- 2 \leq N \leq 1000
- N は整数
- S_i,T_i は英小文字のみからなる長さ 1 以上 10 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
N
S_1 T_1
S_2 T_2
\hspace{0.6cm}\vdots
S_N T_N
出力
同姓同名であるような人の組が存在するなら Yes を、存在しないなら No を出力せよ。
入力例 1
3 tanaka taro sato hanako tanaka taro
出力例 1
Yes
1 人目の人と 3 人目の人が同姓同名です。
入力例 2
3 saito ichiro saito jiro saito saburo
出力例 2
No
同姓同名であるような人の組は存在しません。
入力例 3
4 sypdgidop bkseq bajsqz hh ozjekw mcybmtt qfeysvw dbo
出力例 3
No
Score : 200 points
Problem Statement
There are N people. The family name and given name of the i-th person (1 \leq i \leq N) are S_i and T_i, respectively.
Determine whether there is a pair of people with the same family and given names. In other words, determine whether there is a pair of integers (i,j) such that 1 \leq i \lt j \leq N, S_i=S_j, and T_i=T_j.
Constraints
- 2 \leq N \leq 1000
- N is an integer.
- Each of S_i and T_i is a string of length between 1 and 10 (inclusive) consisting of English lowercase letters.
Input
Input is given from Standard Input in the following format:
N
S_1 T_1
S_2 T_2
\hspace{0.6cm}\vdots
S_N T_N
Output
If there is a pair of people with the same family and given names, print Yes; otherwise, print No.
Sample Input 1
3 tanaka taro sato hanako tanaka taro
Sample Output 1
Yes
The first and third persons have the same family and given names.
Sample Input 2
3 saito ichiro saito jiro saito saburo
Sample Output 2
No
No two persons have the same family and given names.
Sample Input 3
4 sypdgidop bkseq bajsqz hh ozjekw mcybmtt qfeysvw dbo
Sample Output 3
No
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
1 から N までの番号が付けられた N 個のおもちゃと、1 から N-1 までの番号が付けられた N-1 個の箱があります。 おもちゃ i\ (1\leq i\leq N) の大きさは A_i、箱 i\ (1\leq i\leq N-1) の大きさは B_i です。
すべてのおもちゃを別々の箱にしまいたいと考えている高橋君は、今から以下の操作を順に行うことにしました。
- 任意の正整数 x を選んで、大きさ x の箱を 1 つ購入する。
- N 個のおもちゃそれぞれを、(元々あった箱と新しく購入した箱を合わせた)N 個の箱のいずれかに入れる。 ただし、各おもちゃはそのおもちゃの大きさ以上の大きさを持つ箱にしか入れることはできず、また 1 つの箱に 2 つ以上のおもちゃを入れることもできない。
高橋君は、操作 1 で十分な大きさの箱を購入することで操作 2 が実行できるようにしたいですが、大きな箱ほど値段が高いため、可能な限り小さな箱を購入したいです。
高橋君が操作 2 を実行できるような x の値が存在するか判定し、存在するならばその最小値を求めてください。
制約
- 2\leq N \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_{N-1}
出力
高橋君が操作 2 を実行できるような x の値が存在するならばその最小値を、存在しないならば -1 を出力せよ。
入力例 1
4 5 2 3 7 6 2 8
出力例 1
3
x=3 とした場合(すなわち、操作 1 で大きさ 3 の箱を購入した場合)を考えます。
新しく購入した箱を箱 4 と呼ぶことにすると、おもちゃ 1,\dots,4 の大きさはそれぞれ 5,2,3,7、箱 1,\dots,4 の大きさはそれぞれ 6,2,8,3 となります。 よって、おもちゃ 1 を箱 1 に、おもちゃ 2 を箱 2 に、おもちゃ 3 を箱 4 に、おもちゃ 4 を箱 3 にそれぞれ入れることができます。
逆に、x\leq 2 のときは N 個のおもちゃすべてを別々の箱に入れることができません。 よって答えは 3 です。
入力例 2
4 3 7 2 5 8 1 6
出力例 2
-1
操作 1 でどのような大きさの箱を購入したとしても、箱 2 に入れられる大きさのおもちゃが存在しないため、操作 2 を実行することができません。
入力例 3
8 2 28 17 39 57 56 37 32 34 27 73 28 76 61 27
出力例 3
37
Score : 350 points
Problem Statement
There are N toys numbered from 1 to N, and N-1 boxes numbered from 1 to N-1. Toy i\ (1 \leq i \leq N) has a size of A_i, and box i\ (1 \leq i \leq N-1) has a size of B_i.
Takahashi wants to store all the toys in separate boxes, and he has decided to perform the following steps in order:
- Choose an arbitrary positive integer x and purchase one box of size x.
- Place each of the N toys into one of the N boxes (the N-1 existing boxes plus the newly purchased box). Here, each toy can only be placed in a box whose size is not less than the toy's size, and no box can contain two or more toys.
He wants to execute step 2 by purchasing a sufficiently large box in step 1, but larger boxes are more expensive, so he wants to purchase the smallest possible box.
Determine whether there exists a value of x such that he can execute step 2, and if it exists, find the minimum such x.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_{N-1}
Output
If there exists a value of x such that Takahashi can execute step 2, print the minimum such x. Otherwise, print -1.
Sample Input 1
4 5 2 3 7 6 2 8
Sample Output 1
3
Consider the case where x=3 (that is, he purchases a box of size 3 in step 1).
If the newly purchased box is called box 4, toys 1,\dots,4 have sizes of 5, 2, 3, and 7, respectively, and boxes 1,\dots,4 have sizes of 6, 2, 8, and 3, respectively. Thus, toy 1 can be placed in box 1, toy 2 in box 2, toy 3 in box 4, and toy 4 in box 3.
On the other hand, if x \leq 2, it is impossible to place all N toys into separate boxes. Therefore, the answer is 3.
Sample Input 2
4 3 7 2 5 8 1 6
Sample Output 2
-1
No matter what size of box is purchased in step 1, no toy can be placed in box 2, so it is impossible to execute step 2.
Sample Input 3
8 2 28 17 39 57 56 37 32 34 27 73 28 76 61 27
Sample Output 3
37
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
あなたは以下の操作を 0 回以上好きな順番で好きな回数行うことができます:
- A_k=A_{k+1}=A_{k+2}=A_{k+3} を満たす 1 以上 |A|-3 以下の整数 k を選び、A から A_k,A_{k+1},A_{k+2},A_{k+3} を削除する。(より厳密には、 A を (A_1,A_2,\ldots,A_{k-1},A_{k+4},A_{k+5},\ldots,A_N) に置き換える。)
ここで、 |A| は整数列 A の長さを表します。
操作を繰り返した後の最終的な |A| としてあり得る最小値を求めてください。
制約
- 1\le N\le 2\times 10^5
- 1\le A_i\le N
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
操作を繰り返した後の最終的な |A| としてあり得る最小値を出力せよ。
入力例 1
10 1 1 1 4 4 4 4 1 2 3
出力例 1
2
以下のように 2 回操作することで |A|=2 にすることができます。
- k=4 を選ぶ。A_4=A_5=A_6=A_7=4 が成り立つためこの選択は正当である。 A=(1,1,1,1,2,3) となる。
- k=1 を選ぶ。A_1=A_2=A_3=A_4=1 が成り立つためこの選択は正当である。 A=(2,3) となる。
|A| を 2 未満にすることはできないため、 2 を出力してください。
入力例 2
3 2 1 3
出力例 2
3
はじめから操作を行うことができません。
入力例 3
13 1 1 4 4 4 1 1 1 1 4 1 4 1
出力例 3
5
Score : 300 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.
You can perform the following operation zero or more times in any order:
- Choose an integer k between 1 and |A|-3, inclusive, such that A_k=A_{k+1}=A_{k+2}=A_{k+3}, and remove A_k,A_{k+1},A_{k+2},A_{k+3} from A. (More formally, replace A with (A_1,A_2,\ldots,A_{k-1},A_{k+4},A_{k+5},\ldots,A_N).)
Here, |A| represents the length of the integer sequence A.
Find the minimum possible value of the final |A| after repeating the operation.
Constraints
- 1\le N\le 2\times 10^5
- 1\le A_i\le N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Output the minimum possible value of the final |A| after repeating the operation.
Sample Input 1
10 1 1 1 4 4 4 4 1 2 3
Sample Output 1
2
You can make |A|=2 with two operations as follows:
- Choose k=4. This choice is valid since A_4=A_5=A_6=A_7=4 holds. A=(1,1,1,1,2,3) is obtained.
- Choose k=1. This choice is valid since A_1=A_2=A_3=A_4=1 holds. A=(2,3) is obtained.
It is impossible to make |A| less than 2, so output 2.
Sample Input 2
3 2 1 3
Sample Output 2
3
You cannot perform any operation from the beginning.
Sample Input 3
13 1 1 4 4 4 1 1 1 1 4 1 4 1
Sample Output 3
5
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
0 から N-1 までの番号がつけられた N 個のマスが並んでいます。 今から、すぬけくんが以下の手順に従って全てのマスに印をつけていきます。
- マス 0 に印をつける。
-
次の i - iii の手順を N−1 回繰り返す。
- 最後に印をつけたマスの番号を A としたとき、変数 x を (A+D) \bmod N で初期化する。
- マス x に印が付いている限り、 x を (x+1) \bmod N に更新することを繰り返す。
- マス x に印をつける。
すぬけくんが K 番目に印をつけるマスの番号を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\leq T \leq 10^5
- 1\leq K\leq N \leq 10^9
- 1\leq D \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。ここで、\mathrm{test}_i は i 番目のテストケースを意味する。
T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T
各テストケースは以下の形式で与えられる。
N D K
出力
T 行出力せよ。
i\ (1\leq i \leq T) 行目には、i 番目のテストケースに対する答えを出力せよ。
入力例 1
9 4 2 1 4 2 2 4 2 3 4 2 4 5 8 1 5 8 2 5 8 3 5 8 4 5 8 5
出力例 1
0 2 1 3 0 3 1 4 2
N=4,D=2 のとき、すぬけくんは以下のように印をつけていきます。
- マス 0 に印をつける。
- (1回目) x=(0+2)\bmod 4=2 と初期化する。マス 2 は印がついていないので、印をつける。
(2回目) x=(2+2)\bmod 4=0 と初期化する。マス 0 は印がついているので、x=(0+1)\bmod 4=1 と更新する。マス 1 は印がついていないので、印をつける。
(3回目) x=(1+2)\bmod 4=3 と初期化する。マス 3 は印がついていないので、印をつける。
Score : 400 points
Problem Statement
There are N squares indexed 0 through (N-1) arranged in a line. Snuke is going to mark every square by the following procedure.
- Mark square 0.
-
Repeat the following steps i - iii (N-1) times.
- Initialize a variable x with (A+D) \bmod N, where A is the index of the square marked last time.
- While square x is marked, repeat replacing x with (x+1) \bmod N.
- Mark square x.
Find the index of the square that Snuke marks for the K-th time.
Given T test cases, find the answer for each of them.
Constraints
- 1\leq T \leq 10^5
- 1\leq K\leq N \leq 10^9
- 1\leq D \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format, where \mathrm{test}_i denotes the i-th test case:
T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T
Each test case is given in the following format:
N D K
Output
Print T lines.
The i-th (1\leq i \leq T) line should contain the answer to the i-th test case.
Sample Input 1
9 4 2 1 4 2 2 4 2 3 4 2 4 5 8 1 5 8 2 5 8 3 5 8 4 5 8 5
Sample Output 1
0 2 1 3 0 3 1 4 2
If N=4 and D=2, Snuke marks the squares as follows.
- Mark square 0.
- (1-st iteration) Let x=(0+2)\bmod 4=2. Since square 2 is not marked, mark it.
(2-nd iteration) Let x=(2+2)\bmod 4=0. Since square 0 is marked, let x=(0+1)\bmod 4=1. Since square 1 is not marked, mark it.
(3-rd iteration) Let x=(1+2)\bmod 4=3. Since square 3 is not marked, mark it.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
文字列の多重集合 X,Y があります。はじめ、両方ともに空です。
Q 個のクエリが与えられるので、順に処理してください。i 番目のクエリでは、整数 T_i と文字列 S_i が与えられるので、T_i=1 ならば X に S_i を追加し、T_i=2 ならば Y に S_i を追加してください。
各クエリの処理後、以下の値を出力してください。
- Y に含まれる文字列のうち、X のどの要素も接頭辞として持たないものの個数
制約
- Q は 1 以上 2 \times 10^5 以下の整数
- T_i \in \{1,2\}
- S_i は長さ 1 以上 5 \times 10^5 以下の英小文字のみからなる文字列
- \displaystyle \sum_{i=1}^Q |S_i| \leq 5 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
Q T_1 S_1 T_2 S_2 \vdots T_Q S_Q
出力
Q 行出力せよ。i 行目 (1 \leq i \leq Q) には、i 番目のクエリの処理後の答えを出力せよ。
入力例 1
4 1 at 2 watcoder 2 atcoder 1 wa
出力例 1
0 1 1 0
i=1,2,3,4 番目のクエリの処理後の答えはそれぞれ以下のようになります。
- i=1: Y は空なので、求める個数は 0 です。
- i=2:
watcoderは X のどの要素も接頭辞として持たないので、求める個数は 1 です。 - i=3:
watcoderは X のどの要素も接頭辞として持たず、atcoderはatを接頭辞として持つので、求める個数は 1 個です。 - i=4:
watcoderはwaを、atcoderはatを接頭辞として持つので、求める個数は 0 個です。
入力例 2
10 1 w 1 avko 2 atcoder 1 bzginn 2 beginner 1 atco 2 contest 1 ntxcdg 1 atc 1 contest
出力例 2
0 0 1 1 2 1 2 2 2 1
Score : 500 points
Problem Statement
There are two multisets of strings, X and Y, both initially empty.
You are given Q queries to process in order. In the i-th query, you receive an integer T_i and a string S_i. If T_i=1, insert S_i into X; if T_i=2, insert S_i into Y.
After processing each query, print this value:
- the number of strings in Y that have no element of X as a prefix.
Constraints
- Q is an integer between 1 and 2 \times 10^5, inclusive.
- T_i \in \{1,2\}
- Each S_i is a string of length between 1 and 5\times 10^5, inclusive, consisting of lowercase English letters.
- \displaystyle \sum_{i=1}^Q |S_i| \leq 5 \times 10^5
Input
The input is given from Standard Input in the following format:
Q T_1\ S_1 T_2\ S_2 \vdots T_Q\ S_Q
Output
Print Q lines. The i-th line (1 \leq i \leq Q) should contain the count after processing the i-th query.
Sample Input 1
4 1 at 2 watcoder 2 atcoder 1 wa
Sample Output 1
0 1 1 0
The counts after processing the queries for i=1,2,3,4 are as follows.
- i=1: Y is empty, so the count is 0.
- i=2:
watcoderhas no element of X as a prefix, so the count is 1. - i=3:
watcoderhas no element of X as a prefix, whileatcoderhasatas a prefix, so the count is 1. - i=4:
watcoderhaswaas a prefix, andatcoderhasatas a prefix, so the count is 0.
Sample Input 2
10 1 w 1 avko 2 atcoder 1 bzginn 2 beginner 1 atco 2 contest 1 ntxcdg 1 atc 1 contest
Sample Output 2
0 0 1 1 2 1 2 2 2 1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
長さ L のパンが 1 つあり、これを N 人の子供たちに切り分けます。 i 番目 (1\leq i\leq N) の子供は長さ A_i のパンを欲しがっています。
そこで、高橋君は次の操作を繰り返して、長さ A_1,A_2,\ldots,A_N のパンを切り出して配ることにしました。
長さ k のパン 1 つと 1 以上 k-1 以下の整数 x を選ぶ。選んだパンを長さ x のパンと 長さ k-x のパンに切り分ける。
このとき、x の値によらずコストが k かかる。
それぞれの子供に配るパンは長さがちょうど A_i のパン 1 つである必要がありますが、誰にも配られずに余るパンがいくつあっても構いません。
このとき、全ての子供たちにパンを配るために必要な最小のコストを求めてください。
制約
- 2 \leq N \leq 2\times 10^5
- 1\leq A_i\leq 10^9
- A_1+A_2+\cdots+A_N\leq L\leq 10^{15}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N L A_1 A_2 \ldots A_N
出力
全ての子供たちにパンを配るために必要な最小のコストを出力せよ。
入力例 1
5 7 1 2 1 2 1
出力例 1
16
高橋君は次のようにしてパンを切り分けて配ることができます。
- 長さ 7 のパンと整数 x=3 を選ぶ。パンは長さ 3 のパンと長さ 4 のパンに切り分けられる。 (コスト 7 )
- 長さ 3 のパンと整数 x=1 を選ぶ。パンは長さ 1 のパンと長さ 2 のパンに切り分けられる。前者を 1 番目の子供に配る。 (コスト 3 )
- 長さ 2 のパンと整数 x=1 を選ぶ。パンは長さ 1 のパン 2 つに切り分けられる。これを 3,5 番目の子供に配る。 (コスト 2 )
- 長さ 4 のパンと整数 x=2 を選ぶ。パンは長さ 2 のパン 2 つに切り分けられる。これを 2,4 番目の子供に配る。 (コスト 4 )
このとき、コストは 7+3+2+4=16 かかり、これが最小です。 また、余るパンはありません。
入力例 2
3 1000000000000000 1000000000 1000000000 1000000000
出力例 2
1000005000000000
それぞれの子供に配るパンの長さはちょうど A_i でなければならない事に注意してください。
Score : 500 points
Problem Statement
We have a loaf of bread of length L, which we will cut and distribute to N children.
The i-th child (1\leq i\leq N) wants a loaf of length A_i.
Now, Takahashi will repeat the operation below to cut the loaf into lengths A_1, A_2, \ldots, A_N for the children.
Choose a loaf of length k and an integer x between 1 and k-1 (inclusive). Cut the loaf into two loaves of length x and k-x.
This operation incurs a cost of k regardless of the value of x.
Each child i must receive a loaf of length exactly A_i, but it is allowed to leave some loaves undistributed.
Find the minimum cost needed to distribute loaves to all children.
Constraints
- 2 \leq N \leq 2\times 10^5
- 1\leq A_i\leq 10^9
- A_1+A_2+\cdots+A_N\leq L\leq 10^{15}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N L A_1 A_2 \ldots A_N
Output
Print the minimum cost needed to distribute loaves to all children.
Sample Input 1
5 7 1 2 1 2 1
Sample Output 1
16
Takahashi can cut the loaf for the children as follows.
- Choose the loaf of length 7 and x=3, cutting it into loaves of length 3 and 4 for a cost of 7.
- Choose the loaf of length 3 and x=1, cutting it into loaves of length 1 and 2 for a cost of 3. Give the former to the 1-st child.
- Choose the loaf of length 2 and x=1, cutting it into two loaves of length 1 for a cost of 2. Give them to the 3-rd and 5-th children.
- Choose the loaf of length 4 and x=2, cutting it into two loaves of length 2 for a cost of 4. Give them to the 2-nd and 4-th children.
This incurs a cost of 7+3+2+4=16, which is the minimum possible. There will be no leftover loaves.
Sample Input 2
3 1000000000000000 1000000000 1000000000 1000000000
Sample Output 2
1000005000000000
Note that each child i must receive a loaf of length exactly A_i.