Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
N 個のビルが横一列に並んでいて、左から i 番目のビルの高さは H_i です。
左から 1 番目のビルより高いビルが存在するか判定し、存在する場合その内最も左のビルは左から何番目か求めてください。
制約
- 1\leq N\leq 100
- 1\leq H_i \leq 100
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N H_1 H_2 \ldots H_N
出力
左から 1 番目のビルより高いビルが存在しない場合 -1 を出力せよ。
存在する場合、その内最も左のビルは左から何番目か出力せよ。
入力例 1
4 3 2 5 2
出力例 1
3
左から 1 番目のビルより高いビルは、左から 3 番目のビルです。
入力例 2
3 4 3 2
出力例 2
-1
左から 1 番目のビルより高いビルは存在しません。
入力例 3
7 10 5 10 2 10 13 15
出力例 3
6
左から 1 番目のビルより高いビルは、左から 6 番目のビルと左から 7 番目のビルです。その内最も左のビルは左から 6 番目のビルです。
Score: 100 points
Problem Statement
There are N buildings aligned in a row. The i-th building from the left has a height of H_i.
Determine if there is a building taller than the first one from the left. If such a building exists, find the position of the leftmost such building from the left.
Constraints
- 1 \leq N \leq 100
- 1 \leq H_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H_1 H_2 \ldots H_N
Output
If no building is taller than the first one from the left, print -1.
If such a building exists, print the position (index) of the leftmost such building from the left.
Sample Input 1
4 3 2 5 2
Sample Output 1
3
The building taller than the first one from the left is the third one from the left.
Sample Input 2
3 4 3 2
Sample Output 2
-1
No building is taller than the first one from the left.
Sample Input 3
7 10 5 10 2 10 13 15
Sample Output 3
6
The buildings taller than the first one from the left are the sixth and seventh ones. Among them, the leftmost is the sixth one.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
チーム高橋とチーム青木が N 回の試合を行いました。 i 回め (1\leq i\leq N) の試合ではチーム高橋が X _ i 点、チーム青木が Y _ i 点を獲得しました。
N 回の試合で獲得した得点の合計がより多いチームの勝ちです。
どちらのチームが勝ったか出力してください。 ただし、獲得した得点の合計が等しい場合は引き分けとなります。
制約
- 1\leq N\leq 100
- 0\leq X _ i\leq 100\ (1\leq i\leq N)
- 0\leq Y _ i\leq 100\ (1\leq i\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X _ 1 Y _ 1 X _ 2 Y _ 2 \vdots X _ N Y _ N
出力
チーム高橋が勝った場合 Takahashi を、チーム青木が勝った場合 Aoki を、引き分けの場合 Draw を出力せよ。
入力例 1
4 10 2 10 1 10 2 3 2
出力例 1
Takahashi
4 回の試合で、チーム高橋は 33 点、チーム青木は 7 点を獲得しました。
チーム高橋が勝ったため、Takahashi を出力してください。
入力例 2
6 5 4 4 5 2 4 1 6 7 1 3 2
出力例 2
Draw
いずれのチームも 22 点を獲得しました。
引き分けなので、Draw を出力してください。
入力例 3
4 0 0 10 10 50 50 0 100
出力例 3
Aoki
一方もしくは両方のチームが、一試合のうちに 1 点も取れない場合もあります。
Score: 100 points
Problem Statement
Team Takahashi and Team Aoki played N matches. In the i-th match (1\leq i\leq N), Team Takahashi scored X _ i points, and Team Aoki scored Y _ i points.
The team with the higher total score from the N matches wins.
Print the winner. If the two teams have the same total score, it is a draw.
Constraints
- 1\leq N\leq 100
- 0\leq X _ i\leq 100\ (1\leq i\leq N)
- 0\leq Y _ i\leq 100\ (1\leq i\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X _ 1 Y _ 1 X _ 2 Y _ 2 \vdots X _ N Y _ N
Output
If Team Takahashi wins, print Takahashi; if Team Aoki wins, print Aoki; if it is a draw, print Draw.
Sample Input 1
4 10 2 10 1 10 2 3 2
Sample Output 1
Takahashi
In four matches, Team Takahashi scored 33 points, and Team Aoki scored 7 points.
Team Takahashi wins, so print Takahashi.
Sample Input 2
6 5 4 4 5 2 4 1 6 7 1 3 2
Sample Output 2
Draw
Both teams scored 22 points.
It is a draw, so print Draw.
Sample Input 3
4 0 0 10 10 50 50 0 100
Sample Output 3
Aoki
One or both teams may score no points in a match.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N 個のマスが左右一列に並んでおり、左から順にマス 1、マス 2、…、マス N と番号づけられています。
また、K 個のコマがあり、最初左から i 番目のコマはマス A_i に置かれています。
これらに対して、Q 回の操作を行います。
i 回目の操作では次の操作を行います。
- 左から L_i 番目のコマが一番右のマスにあるならば何も行わない。
- そうでない時、左から L_i 番目のコマがあるマスの 1 つ右のマスにコマが無いならば、左から L_i 番目のコマを 1 つ右のマスに移動させる。 1 つ右のマスにコマがあるならば、何も行わない。
Q 回の操作が終了した後の状態について、i=1,2,\ldots,K に対して左から i 番目のコマがあるマスの番号を出力してください。
制約
- 1\leq K\leq N\leq 200
- 1\leq A_1<A_2<\cdots<A_K\leq N
- 1\leq Q\leq 1000
- 1\leq L_i\leq K
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K Q A_1 A_2 \ldots A_K L_1 L_2 \ldots L_Q
出力
K 個の整数を空白区切りで一行に出力せよ。 ここで、i 個目の整数は、 Q 回の操作が終了した後の状態について、左から i 番目のコマの番号を表す。
入力例 1
5 3 5 1 3 4 3 3 1 1 2
出力例 1
2 4 5
最初、コマはマス 1, 3, 4 にあります。これに対して以下のように操作が行われます。
- 左から 3 番目のコマはマス 4 にあります。 これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 3 番目のコマをマス 5 に動かします。 コマはマス 1, 3, 5 にある状態になります。
- 左から 3 番目のコマはマス 5 にあります。 これは一番右のマスなので、何も行いません。 コマはマス 1, 3, 5 にある状態のままです。
- 左から 1 番目のコマはマス 1 にあります。 これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 1 番目のコマをマス 2 に動かします。 コマはマス 2, 3, 5 にある状態になります。
- 左から 1 番目のコマはマス 2 にあります。 これは一番右のマスでありませんが、その 1 つ右のマス(マス 3 )にコマが置かれているため、何も行いません。 コマはマス 2, 3, 5 にある状態のままです。
- 左から 2 番目のコマはマス 3 にあります。 これは一番右のマスでなく、その右のマスにもコマが置かれていないため、左から 2 番目のコマをマス 4 に動かします。 コマはマス 2, 4, 5 にある状態になります。
よって、Q 回の操作が終わった後でコマはマス 2, 4, 5 に置かれているため、2,4,5 を空白区切りでこの順に出力します。
入力例 2
2 2 2 1 2 1 2
出力例 2
1 2
入力例 3
10 6 9 1 3 5 7 8 9 1 2 3 4 5 6 5 6 2
出力例 3
2 5 6 7 9 10
Score : 200 points
Problem Statement
There are N squares, indexed Square 1, Square 2, …, Square N, arranged in a row from left to right.
Also, there are K pieces. The i-th piece from the left is initially placed on Square A_i.
Now, we will perform Q operations against them.
The i-th operation is as follows:
- If the L_i-th piece from the left is on its rightmost square, do nothing.
- Otherwise, move the L_i-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.
Print the index of the square on which the i-th piece from the left is after the Q operations have ended, for each i=1,2,\ldots,K.
Constraints
- 1\leq K\leq N\leq 200
- 1\leq A_1<A_2<\cdots<A_K\leq N
- 1\leq Q\leq 1000
- 1\leq L_i\leq K
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K Q A_1 A_2 \ldots A_K L_1 L_2 \ldots L_Q
Output
Print K integers in one line, with spaces in between. The i-th of them should be the index of the square on which the i-th piece from the left is after the Q operations have ended.
Sample Input 1
5 3 5 1 3 4 3 3 1 1 2
Sample Output 1
2 4 5
At first, the pieces are on Squares 1, 3, and 4. The operations are performed against them as follows:
- The 3-rd piece from the left is on Square 4. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 3-rd piece from the left to Square 5. Now, the pieces are on Squares 1, 3, and 5.
- The 3-rd piece from the left is on Square 5. This is the rightmost square, so do nothing. The pieces are still on Squares 1, 3, and 5.
- The 1-st piece from the left is on Square 1. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 1-st piece from the left to Square 2. Now, the pieces are on Squares 2, 3, and 5.
- The 1-st piece from the left is on Square 2. This is not the rightmost square, but the next square on the right (Square 3) contains a piece, so do nothing. The pieces are still on Squares 2, 3, and 5.
- The 2-nd piece from the left is on Square 3. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 2-nd piece from the left to Square 4; Now, the pieces are still on Squares 2, 4, and 5.
Thus, after the Q operations have ended, the pieces are on Squares 2, 4, and 5, so 2, 4, and 5 should be printed in this order, with spaces in between.
Sample Input 2
2 2 2 1 2 1 2
Sample Output 2
1 2
Sample Input 3
10 6 9 1 3 5 7 8 9 1 2 3 4 5 6 5 6 2
Sample Output 3
2 5 6 7 9 10
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
I begin with T and end with T, and I am full of T. What am I?
文字列 t について、充填率を以下のように定義します。
- t の先頭と末尾の文字がともに
tであり、かつ |t| \geq 3 である場合: t に含まれるtの個数を x とすると、t の充填率は \displaystyle\frac{x-2}{|t|-2} である。ここで、|t| は t の長さを表す。 - そうでない場合: t の充填率は 0 である。
文字列 S が与えられます。S の部分文字列の充填率としてありうる最大値を求めてください。
部分文字列とは
S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。 例えば、ab, bc, bcd は abcd の部分文字列ですが、ac, dc, e は abcd の部分文字列ではありません。
制約
- 1 \leq |S| \leq 100
- S は英小文字からなる文字列。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の部分文字列の充填率としてありうる最大値を出力せよ。
出力された値と真の値との絶対誤差が 10^{-9} 以下のとき、正答と判定される。
入力例 1
attitude
出力例 1
0.50000000000000000
ttit は S の部分文字列であり、その充填率は \displaystyle\frac{3-2}{4-2} = \frac{1}{2} です。
充填率が \frac{1}{2} より高い部分文字列は存在しないので、答えは \frac{1}{2} です。
入力例 2
ottottott
出力例 2
0.66666666666666667
ttottott は S の部分文字列であり、その充填率は \displaystyle\frac{6-2}{8-2} = \frac{2}{3} です。
充填率が \frac{2}{3} より高い部分文字列は存在しないので、答えは \frac{2}{3} です。
入力例 3
coffeecup
出力例 3
0.00000000000000000
ff は S の部分文字列であり、その充填率は 0 です。
充填率が 0 より高い部分文字列は存在しないので、答えは 0 です。
Score : 200 points
Problem Statement
I begin with T and end with T, and I am full of T. What am I?
For a string t, define the filling rate as follows:
- If the first and last characters of t are both
tand |t| \geq 3: Let x be the number oftin t. Then the filling rate of t is \displaystyle\frac{x-2}{|t|-2}, where |t| denotes the length of t. - Otherwise: the filling rate of t is 0.
You are given a string S. Find the maximum possible filling rate of a substring of S.
What is a substring?
A substring of S is a string obtained by removing zero or more characters from the beginning and the end of S. For example,ab, bc, and bcd are substrings of abcd, while ac, dc, and e are not substrings of abcd.
Constraints
- 1 \leq |S| \leq 100
- S is a string consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
Print the maximum possible filling rate of a substring of S.
Your output will be judged as correct when the absolute error from the true value is at most 10^{-9}.
Sample Input 1
attitude
Sample Output 1
0.50000000000000000
ttit is a substring of S, and its filling rate is \displaystyle\frac{3-2}{4-2} = \frac{1}{2}.
There is no substring with a filling rate greater than \frac{1}{2}, so the answer is \frac{1}{2}.
Sample Input 2
ottottott
Sample Output 2
0.66666666666666667
ttottott is a substring of S, and its filling rate is \displaystyle\frac{6-2}{8-2} = \frac{2}{3}.
There is no substring with a filling rate greater than \frac{2}{3}, so the answer is \frac{2}{3}.
Sample Input 3
coffeecup
Sample Output 3
0.00000000000000000
ff is a substring of S, and its filling rate is 0.
There is no substring with a filling rate greater than 0, so the answer is 0.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
AtCoder 社の入口には特殊なパスコード入力装置があり、 この装置は文字列を 1 つ表示する画面と 2 つのボタンからなります。
画面に表示される文字列を t とします。 t ははじめ空文字列であり、ボタンを押すことで t に以下の変化が起きます。
- ボタン A を押すと、t の末尾に
0が追加される。 - ボタン B を押すと、t に含まれるすべての数字が、それぞれ次の数字に置き換わる。ここで、
0から8までの数字については次の数字は 1 大きな数を表す数字とし、9の次の数字は0とする。
たとえば、t が 1984 のときにボタン A を押すと t は 19840 に変化し、さらにボタン B を押すと t は 20951 に変化します。
文字列 S が与えられます。t が空文字列である状態からボタンを 0 回以上押して t を S に一致させるとき、ボタンを最少で何回押す必要があるかを求めてください。
制約
- S は
0,1,2,3,4,5,6,7,8,9からなる文字列 - 1 \leq |S| \leq 5 \times 10^5 (|S| は S の長さをあらわす)
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
21
出力例 1
4
以下の順にボタンを押せば、t が 21 になります。
- ボタン A を押す。t は
0になる。 - ボタン B を押す。t は
1になる。 - ボタン A を押す。t は
10になる。 - ボタン B を押す。t は
21になる。
4 回より少ない回数ボタンを押して t を 21 にすることはできないので、4 を出力します。
入力例 2
407
出力例 2
17
入力例 3
2025524202552420255242025524
出力例 3
150
Score : 300 points
Problem Statement
At the entrance of AtCoder Inc., there is a special pass-code input device. The device consists of a screen displaying one string, and two buttons.
Let t be the string shown on the screen. Initially, t is the empty string. Pressing a button changes t as follows:
- Pressing button A appends
0to the end of t. - Pressing button B replaces every digit in t with the next digit: for digits
0through8the next digit is the one whose value is larger by 1; the next digit after9is0.
For example, if t is 1984 and button A is pressed, t becomes 19840; if button B is then pressed, t becomes 20951.
You are given a string S. Starting from the empty string, press the buttons zero or more times until t coincides with S. Find the minimum number of button presses required.
Constraints
- S is a string consisting of
0,1,2,3,4,5,6,7,8, and9. - 1 \le |S| \le 5 \times 10^{5}, where |S| is the length of S.
Input
The input is given from Standard Input in the following format:
S
Output
Output the answer.
Sample Input 1
21
Sample Output 1
4
The following sequence of presses makes t equal to 21.
- Press button A. t becomes
0. - Press button B. t becomes
1. - Press button A. t becomes
10. - Press button B. t becomes
21.
It is impossible to obtain 21 with fewer than four presses, so output 4.
Sample Input 2
407
Sample Output 2
17
Sample Input 3
2025524202552420255242025524
Sample Output 3
150
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
数字からなる文字列 S が与えられます。
以下の条件を全て満たす文字列 T を 1122文字列 と呼びます。(定義は F 問題と同じです。)
- T は数字からなる空でない文字列
- |T| は偶数。ここで、 |T| は文字列 T の長さを表す
- T の 1 文字目から \frac{|T|}2 文字目までは全て同じ数字である
- T の \frac{|T|}2+1 文字目から |T| 文字目までは全て同じ数字である
- T の 1 文字目の数字に 1 を足すと |T| 文字目の数字になる
例えば 1122 や 01 、 444555 などは 1122文字列 ですが、 1222 や 90 は 1122文字列 ではありません。
S の 部分文字列 であって 1122文字列 であるものの個数を求めてください。
ただし、ある二つの部分文字列が文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えるものとします。
制約
- S は長さ 1 以上 10^6 以下の数字からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の空でない部分文字列であって 1122文字列 であるものの個数を出力せよ。
入力例 1
1122
出力例 1
2
以下の 2 つの部分文字列が条件を満たします。
- S の 2 文字目から 3 文字目を取り出した
12 - S の 1 文字目から 4 文字目を取り出した
1122
したがって、 2 を出力してください。
入力例 2
7788788
出力例 2
3
文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えることに注意してください。
入力例 3
2025
出力例 3
0
1122文字列 となる部分文字列が存在しない場合もあります。
入力例 4
1112222334445556555
出力例 4
11
Score : 300 points
Problem Statement
You are given a string S consisting of digits.
A string T is called a 1122-string if it satisfies all of the following conditions. (The definition is the same as in Problem F.)
- T is a non-empty string consisting of digits.
- |T| is even, where |T| denotes the length of string T.
- All characters from the 1-st through the \frac{|T|}2-th character of T are the same digit.
- All characters from the (\frac{|T|}2+1)-th through the |T|-th character of T are the same digit.
- Adding 1 to the digit of the 1-st character of T gives the digit of the |T|-th character.
For example, 1122, 01, and 444555 are 1122-strings, but 1222 and 90 are not 1122-strings.
Find the number of substrings of S that are 1122-strings.
Two substrings are counted separately if they are extracted from different positions, even if they are identical as strings.
Constraints
- S is a string consisting of digits with length between 1 and 10^6, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Output the number of non-empty substrings of S that are 1122-strings.
Sample Input 1
1122
Sample Output 1
2
The following two substrings satisfy the condition.
12extracted from the 2-nd through 3-rd characters of S1122extracted from the 1-st through 4-th characters of S
Thus, output 2.
Sample Input 2
7788788
Sample Output 2
3
Note that two substrings are counted separately if they are extracted from different positions, even if they are identical as strings.
Sample Input 3
2025
Sample Output 3
0
There may be no substring that is a 1122-string.
Sample Input 4
1112222334445556555
Sample Output 4
11
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君が主催するコンテストに、1 から N までの番号が付けられた N 人の選手が参加しています。 このコンテストは各選手がその得点を競うものであり、現在の得点はどの選手も 0 点です。
未来予知の能力を持つ高橋君は、今から選手たちの得点がどのように変動するかを知っています。 具体的には、i=1,2,\dots,T について、今から i 秒後に選手 A_i の得点が B_i 点増加します。 逆に、それ以外に得点の変動はありません。
得点の多様性を好む高橋君は、各時点における選手たちの得点に何種類の値が現れるかを知りたがっています。 i=1,2,\dots,T それぞれについて、今から i+0.5 秒後の選手たちの得点には何種類の値が現れるか求めてください。
例えば、ある時点における選手たちの得点がそれぞれ 10,20,30,20 点であった場合、この時点での選手たちの得点には 3 種類の値が現れています。
制約
- 1\leq N, T\leq 2\times 10^5
- 1\leq A_i \leq N
- 1\leq B_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N T A_1 B_1 A_2 B_2 \vdots A_T B_T
出力
T 行出力せよ。 i\ (1\leq i \leq T) 行目には、今から i+0.5 秒後の選手たちの得点には何種類の値が現れるかを整数として出力せよ。
入力例 1
3 4 1 10 3 20 2 10 2 10
出力例 1
2 3 2 2
選手 1,2,3 の得点をこの順に並べた数列を S とします。 現在、S=\lbrace 0,0,0\rbrace です。
- 1 秒後に選手 1 の得点が 10 点増加し、S=\lbrace 10,0,0\rbrace になります。よって、1.5 秒後の選手たちの得点には 2 種類の値が現れます。
- 2 秒後に選手 3 の得点が 20 点増加し、S=\lbrace 10,0,20\rbrace になります。よって、2.5 秒後の選手たちの得点には 3 種類の値が現れます。
- 3 秒後に選手 2 の得点が 10 点増加し、S=\lbrace 10,10,20\rbrace になります。よって、3.5 秒後の選手たちの得点には 2 種類の値が現れます。
- 4 秒後に選手 2 の得点が 10 点増加し、S=\lbrace 10,20,20\rbrace になります。よって、4.5 秒後の選手たちの得点には 2 種類の値が現れます。
入力例 2
1 3 1 3 1 4 1 3
出力例 2
1 1 1
入力例 3
10 10 7 2620 9 2620 8 3375 1 3375 6 1395 5 1395 6 2923 10 3375 9 5929 5 1225
出力例 3
2 2 3 3 4 4 5 5 6 5
Score: 400 points
Problem Statement
Takahashi is hosting a contest with N players numbered 1 to N. The players will compete for points. Currently, all players have zero points.
Takahashi's foreseeing ability lets him know how the players' scores will change. Specifically, for i=1,2,\dots,T, the score of player A_i will increase by B_i points at i seconds from now. There will be no other change in the scores.
Takahashi, who prefers diversity in scores, wants to know how many different score values will appear among the players' scores at each moment. For each i=1,2,\dots,T, find the number of different score values among the players' scores at i+0.5 seconds from now.
For example, if the players have 10, 20, 30, and 20 points at some moment, there are three different score values among the players' scores at that moment.
Constraints
- 1\leq N, T\leq 2\times 10^5
- 1\leq A_i \leq N
- 1\leq B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N T A_1 B_1 A_2 B_2 \vdots A_T B_T
Output
Print T lines. The i-th line (1\leq i \leq T) should contain an integer representing the number of different score values among the players' scores at i+0.5 seconds from now.
Sample Input 1
3 4 1 10 3 20 2 10 2 10
Sample Output 1
2 3 2 2
Let S be the sequence of scores of players 1, 2, 3 in this order. Currently, S=\lbrace 0,0,0\rbrace.
- After one second, the score of player 1 increases by 10 points, making S=\lbrace 10,0,0\rbrace. Thus, there are two different score values among the players' scores at 1.5 seconds from now.
- After two seconds, the score of player 3 increases by 20 points, making S=\lbrace 10,0,20\rbrace. Thus, there are three different score values among the players' scores at 2.5 seconds from now.
- After three seconds, the score of player 2 increases by 10 points, making S=\lbrace 10,10,20\rbrace. Therefore, there are two different score values among the players' scores at 3.5 seconds from now.
- After four seconds, the score of player 2 increases by 10 points, making S=\lbrace 10,20,20\rbrace. Therefore, there are two different score values among the players' scores at 4.5 seconds from now.
Sample Input 2
1 3 1 3 1 4 1 3
Sample Output 2
1 1 1
Sample Input 3
10 10 7 2620 9 2620 8 3375 1 3375 6 1395 5 1395 6 2923 10 3375 9 5929 5 1225
Sample Output 3
2 2 3 3 4 4 5 5 6 5
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 475 点
問題文
AtCoder 社はある商品の開発をしようとしています。この商品には K 個のパラメーターがあり、現段階ではすべてのパラメーターの値が 0 です。AtCoder 社の目標は、パラメーターの値を全て P 以上にすることです。
ここで、N 個の開発案があります。i(1 \le i \le N) 個目の開発案を実行すると、1 \le j \le K を満たす整数 j 全てに対して j 個目のパラメーターが A_{i,j} 上がりますが、この開発案を実行するにはコストが C_i かかります。
同じ開発案を 2 回以上実行することは出来ません。AtCoder 社が目標を達成出来るか判定し、出来る場合は目標を達成するのに必要なコストの総和の最小値を求めてください。
制約
- 1 \le N \le 100
- 1 \le K,P \le 5
- 0 \le A_{i,j} \le P(1 \le i \le N,1 \le j \le K)
- 1 \le C_i \le 10^9(1 \le i \le N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K P
C_1 A_{1,1} A_{1,2} \dots A_{1,K}
C_2 A_{2,1} A_{2,2} \dots A_{2,K}
\dots
C_N A_{N,1} A_{N,2} \dots A_{N,K}
出力
AtCoder 社が目標を達成出来るならば目標を達成するのに必要なコストの総和の最小値を、出来ないならば -1 を出力せよ。
入力例 1
4 3 5 5 3 0 2 3 1 2 3 3 2 4 0 1 0 1 4
出力例 1
9
1 個目と 3 個目と 4 個目の開発案を実行すると、それぞれのパラメーターが 3+2+0=5,0+4+1=5,2+0+4=6 で全て 5 以上となるため目標を達成できます。この場合コストの総和は 5 + 3 + 1 = 9 となります。
コストの総和 8 以下で目標を達成することは出来ません。よって答えは 9 です。
入力例 2
7 3 5 85 1 0 1 37 1 1 0 38 2 0 0 45 0 2 2 67 1 1 0 12 2 2 0 94 2 2 1
出力例 2
-1
どのようにしても目標を達成することは出来ません。よって -1 を出力します。
Score : 475 points
Problem Statement
AtCoder Inc. is planning to develop a product. The product has K parameters, whose values are currently all zero. The company aims to raise all parameter values to at least P.
There are N development plans. Executing the i-th development plan (1 \le i \le N) increases the value of the j-th parameter by A_{i,j} for every integer j such that 1 \le j \le K, at the cost of C_i.
A development plan cannot be executed more than once. Determine whether the company can achieve its goal, and if it can, find the minimum total cost required to achieve the goal.
Constraints
- 1 \le N \le 100
- 1 \le K,P \le 5
- 0 \le A_{i,j} \le P(1 \le i \le N,1 \le j \le K)
- 1 \le C_i \le 10^9(1 \le i \le N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K P
C_1 A_{1,1} A_{1,2} \dots A_{1,K}
C_2 A_{2,1} A_{2,2} \dots A_{2,K}
\dots
C_N A_{N,1} A_{N,2} \dots A_{N,K}
Output
If AtCoder Inc. can achieve its goal, print the minimum total cost required to achieve the goal; otherwise, print -1.
Sample Input 1
4 3 5 5 3 0 2 3 1 2 3 3 2 4 0 1 0 1 4
Sample Output 1
9
If you execute the first, third, and fourth development plans, each parameter will be 3+2+0=5,0+4+1=5,2+0+4=6, all of which are at least 5, so the goal is achieved. The total cost in this case is 5 + 3 + 1 = 9.
It is impossible to achieve the goal at a total cost of 8 or less. Thus, the answer is 9.
Sample Input 2
7 3 5 85 1 0 1 37 1 1 0 38 2 0 0 45 0 2 2 67 1 1 0 12 2 2 0 94 2 2 1
Sample Output 2
-1
You cannot achieve the goal no matter what you do. Thus, print -1.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
N 頂点の木 T が与えられます。T の頂点には 1 から N の番号がついており、 i\,(1\leq i \leq N-1) 番目の辺は頂点 u_i と頂点 v_i を双方向に結んでいます。
T を用いて、N 頂点の完全グラフ G を次のように定めます。
- G の頂点 x と頂点 y の間の辺の重み w(x,y) を、T における頂点 x と頂点 y の間の最短距離とする
G の最大重み最大マッチングを一つ求めてください。すなわち、\lfloor N/2 \rfloor 個の頂点のペアの集合 M=\{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})\} であって、各頂点 1,2,\dots, N が M に現れる回数がたかだか 1 回であるようなもののうち、 \displaystyle \sum_{i=1}^{\lfloor N/2 \rfloor} w(x_i,y_i) が最大であるものを一つ求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq u_i < v_i \leq N
- 入力されるグラフは木である
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
出力
答えを \{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})\} として、以下の形式で出力せよ。答えが複数あり得る場合、そのうちどれを出力しても良い。
x_1 y_1
x_2 y_2
\vdots
x_{\lfloor N/2 \rfloor} y_{\lfloor N/2 \rfloor}
入力例 1
4 1 2 2 3 3 4
出力例 1
2 4 1 3
T において、頂点 2,4 間の距離は 2、頂点 1,3 間の距離は 2 なので、マッチング \{(2,4),(1,3)\} の重みは 4 です。重みが 4 より大きいマッチングは存在しないので、これが最大重み最大マッチングの一つです。他にも、
2 3 1 4
などを出力しても正解になります。
入力例 2
3 1 2 2 3
出力例 2
1 3
T において、頂点 1,3 間の距離は 2 なので、マッチング \{(1,3)\} の重みは 2 です。重みが 2 より大きいマッチングは存在しないので、これが最大重み最大マッチングの一つです。他にも、
3 1
を出力しても正解になります。
Score : 550 points
Problem Statement
You are given a tree T with N vertices. The vertices are numbered 1 to N, and the i-th edge (1 \leq i \leq N-1) connects vertices u_i and v_i bidirectionally.
Using T, define a complete graph G with N vertices as follows:
- The weight w(x,y) of the edge between vertices x and y in G is the shortest distance between vertices x and y in T.
Find one maximum weight maximum matching in G. That is, find a set of \lfloor N/2 \rfloor pairs of vertices M=\{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})\} such that each vertex 1,2,\dots, N appears in M at most once, and \displaystyle \sum_{i=1}^{\lfloor N/2 \rfloor} w(x_i,y_i) is maximized.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq u_i < v_i \leq N
- The input graph is a tree.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
Output
Print a solution as \{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})\} in the following format. If multiple solutions exist, any of them is acceptable.
x_1 y_1
x_2 y_2
\vdots
x_{\lfloor N/2 \rfloor} y_{\lfloor N/2 \rfloor}
Sample Input 1
4 1 2 2 3 3 4
Sample Output 1
2 4 1 3
In T, the distance between vertices 2 and 4 is 2, and the distance between vertices 1 and 3 is 2, so the weight of the matching \{(2,4),(1,3)\} is 4. There is no matching with a weight greater than 4, so this is a maximum weight maximum matching. Other acceptable outputs include:
2 3 1 4
Sample Input 2
3 1 2 2 3
Sample Output 2
1 3
In T, the distance between vertices 1 and 3 is 2, so the weight of the matching \{(1,3)\} is 2. There is no matching with a weight greater than 2, so this is a maximum weight maximum matching. Another acceptable output is:
3 1