Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
2^n \gt n^2 ですか?
制約
- n は 1 以上 10^9 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
n
出力
2^n \gt n^2 なら Yes を、そうでないなら No を出力せよ。
入力例 1
5
出力例 1
Yes
2^5=32,\ 5^2=25 より 2^n \gt n^2 であるため、Yes を出力します。
入力例 2
2
出力例 2
No
n=2 の場合 2^n=n^2=2^2 となり、故に 2^n \gt n^2 ではありません。よって No を出力します。
入力例 3
623947744
出力例 3
Yes
Score : 100 points
Problem Statement
Does 2^n \gt n^2 hold?
Constraints
- n is an integer between 1 and 10^9 (inclusive).
Input
Input is given from Standard Input in the following format:
n
Output
If 2^n \gt n^2, print Yes; otherwise, print No.
Sample Input 1
5
Sample Output 1
Yes
Since 2^5=32,\ 5^2=25, we have 2^n \gt n^2, so Yes should be printed.
Sample Input 2
2
Sample Output 2
No
For n=2, we have 2^n=n^2=2^2, so 2^n \gt n^2 does not hold. Thus, No should be printed.
Sample Input 3
623947744
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
4 種類の牡蠣 1,2,3,4 があります。 このうちちょうど 1 種類の牡蠣については、食べるとお腹を壊してしまいます。 それ以外の牡蠣については、食べてもお腹を壊しません。
高橋君が牡蠣 1,2 を食べ、青木君が牡蠣 1,3 を食べました。
二人がこれによってお腹を壊したかどうかの情報が二つの文字列 S_1,S_2 によって与えられます。
具体的には、S_1= sick であるとき高橋君がお腹を壊したことを、S_1= fine であるとき高橋君がお腹を壊さなかったことを表します。
同様に、S_2= sick であるとき青木君がお腹を壊したことを、S_2= fine であるとき青木君がお腹を壊さなかったことを表します。
与えられた情報をもとに、どの種類の牡蠣を食べるとお腹を壊すか判定してください。
制約
- S_1, S_2 はそれぞれ
sickまたはfine
入力
入力は以下の形式で標準入力から与えられる。
S_1 S_2
出力
食べるとお腹を壊す牡蠣の種類の番号を出力せよ。
入力例 1
sick fine
出力例 1
2
牡蠣 1,2 を食べた高橋君はお腹を壊し、牡蠣 1,3 を食べた青木君はお腹を壊さなかったので、牡蠣 2 を食べるとお腹を壊すことがわかります。
入力例 2
fine fine
出力例 2
4
牡蠣 1,2 を食べた高橋君も牡蠣 1,3 を食べた青木君もお腹を壊さなかったので、残る牡蠣 4 を食べるとお腹を壊すことがわかります。
Score : 100 points
Problem Statement
There are four types of oysters, labeled 1, 2, 3, and 4. Exactly one of these types causes stomach trouble if eaten. The other types do not cause stomach trouble when eaten.
Takahashi ate oysters 1 and 2, and Aoki ate oysters 1 and 3. The information on whether each person got sick is given as two strings S_1 and S_2. Specifically, S_1 = sick means Takahashi got sick, and S_1 = fine means Takahashi did not get sick. Likewise, S_2 = sick means Aoki got sick, and S_2 = fine means Aoki did not get sick.
Based on the given information, find which type of oyster causes stomach trouble.
Constraints
- Each of S_1 and S_2 is
sickorfine.
Input
The input is given from Standard Input in the following format:
S_1 S_2
Output
Print the label of the oyster that causes stomach trouble if eaten.
Sample Input 1
sick fine
Sample Output 1
2
Takahashi (who ate oysters 1 and 2) got sick, and Aoki (who ate oysters 1 and 3) did not get sick, so it can be concluded that oyster 2 causes stomach trouble.
Sample Input 2
fine fine
Sample Output 2
4
Neither Takahashi (who ate oysters 1 and 2) nor Aoki (who ate oysters 1 and 3) got sick, so it can be concluded that oyster 4 causes stomach trouble.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
AtCoder社のオフィスは H 行 W 列のマス目で表されます。上から i 行目、左から j 列目のマスを (i, j) と表します。
各マスの状態は文字 S_{i,j} で表され、 S_{i,j} が # のときそのマスは机、. のときそのマスは床です。床のマスは 2 つ以上存在することが保証されます。
あなたは床のマスから異なる 2 マスを選び、加湿器を設置します。
加湿器が設置されたとき、あるマス (i,j) は加湿器があるマス (i',j') からのマンハッタン距離が D 以下であるとき、またその時に限り加湿されます。 なお、マス (i,j) からマス (i',j') までのマンハッタン距離は |i-i'|+|j-j'| で表されます。 ここで、加湿器が置かれた床のマスは必ず加湿されていることに注意してください。
加湿される 床のマス の個数として考えられる最大値を求めてください。
制約
- 1 \leq H \leq 10
- 1 \leq W \leq 10
- 2 \leq H \times W
- 0 \leq D \leq H+W-2
- H,W,D は整数
- S_{i,j} は
#または.である (1 \leq i \leq H, 1 \leq j \leq W) - 床のマスは 2 つ以上存在する
入力
入力は以下の形式で標準入力から与えられる。
H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}
出力
答えを出力せよ。
入力例 1
2 5 1 .###. .#.##
出力例 1
3
マス (1,1) とマス (1,5) に加湿器を置いた時:
- マス (1,1) の加湿器によってマス (1,1),(2,1) の 2 マスが加湿されます。
- マス (1,5) の加湿器によってマス (1,5) の 1 マスが加湿されます。
よって、合計 3 マス加湿されています。また、4 マス以上加湿するような加湿器の置き方は存在しないため、答えは 3 です。
入力例 2
5 5 2 .#.#. ..... .#.#. #.#.# .....
出力例 2
15
マス (2,4) とマス (5,3) に加湿器を置いた時、15 個の床のマスが加湿されます。
入力例 3
4 4 2 .... .##. .##. ....
出力例 3
10
Score : 250 points
Problem Statement
The AtCoder company office can be represented as a grid of H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
The state of each cell is represented by a character S_{i,j}. If S_{i,j} is #, that cell contains a desk; if S_{i,j} is ., that cell is a floor. It is guaranteed that there are at least two floor cells.
You will choose two distinct floor cells and place a humidifier on each.
After placing the humidifiers, a cell (i,j) is humidified if and only if it is within a Manhattan distance D from at least one of the humidifier cells (i',j'). The Manhattan distance between (i,j) and (i',j') is defined as |i - i'| + |j - j'|. Note that any floor cell on which a humidifier is placed is always humidified.
Find the maximum possible number of humidified floor cells.
Constraints
- 1 \leq H \leq 10
- 1 \leq W \leq 10
- 2 \leq H \times W
- 0 \leq D \leq H+W-2
- H,W,D are integers.
- S_{i,j} is
#or.. (1 \leq i \leq H, 1 \leq j \leq W) - There are at least two floor cells.
Input
The input is given from Standard Input in the following format:
H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}
Output
Print the answer.
Sample Input 1
2 5 1 .###. .#.##
Sample Output 1
3
When placing humidifiers on (1,1) and (1,5):
- From the humidifier on (1,1), two cells (1,1) and (2,1) are humidified.
- From the humidifier on (1,5), one cell (1,5) is humidified.
In total, three cells are humidified. No configuration can humidify four or more floor cells, so the answer is 3.
Sample Input 2
5 5 2 .#.#. ..... .#.#. #.#.# .....
Sample Output 2
15
When placing humidifiers on (2,4) and (5,3), 15 floor cells are humidified.
Sample Input 3
4 4 2 .... .##. .##. ....
Sample Output 3
10
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N 人の人がいます。N 人の人には人 1, 人 2,\dots, 人 N と番号がついています。
人 i(2 \le i \le N) の親は人 P_i です。ここで、P_i < i が保証されます。
人 1 が人 N の何代前か求めてください。
制約
- 2 \le N \le 50
- 1 \le P_i < i(2 \le i \le N)
- 入力は全て整数。
入力
入力は以下の形式で標準入力から与えられる。
N P_2 P_3 \dots P_N
出力
答えを整数として出力せよ。
入力例 1
3 1 2
出力例 1
2
人 2 は人 3 の親であるため、人 3 の 1 代前です。
人 1 は人 2 の親であるため、人 3 の 2 代前です。
よって解は 2 です。
入力例 2
10 1 2 3 4 5 6 7 8 9
出力例 2
9
Score : 200 points
Problem Statement
There are N people, called Person 1, Person 2, \ldots, Person N.
The parent of Person i (2 \le i \le N) is Person P_i. Here, it is guaranteed that P_i < i.
How many generations away from Person N is Person 1?
Constraints
- 2 \le N \le 50
- 1 \le P_i < i(2 \le i \le N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_2 P_3 \dots P_N
Output
Print the answer as a positive integer.
Sample Input 1
3 1 2
Sample Output 1
2
Person 2 is a parent of Person 3, and thus is one generation away from Person 3.
Person 1 is a parent of Person 2, and thus is two generations away from Person 3.
Therefore, the answer is 2.
Sample Input 2
10 1 2 3 4 5 6 7 8 9
Sample Output 2
9
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は黒いマスと透明なマスからなるシート A,B を 1 枚ずつと、透明なマスのみからなる無限に広がるシート C を持っています。
また、高橋君には黒いマスと透明なマスからなる、理想とするシート X が存在します。
シート A,B,X の大きさはそれぞれ縦 H_A マス \times 横 W_A マス、縦 H_B マス \times 横 W_B マス、縦 H_X マス \times 横 W_X マスです。
シート A の各マスは . と # からなる長さ W_A の文字列 H_A 個 A_1,A_2,\ldots,A_{H_A} によって表され、
A_i (1\leq i\leq H_A) の j 文字目 (1\leq j\leq W_A) が、
. のときシート A の上から i 行目かつ左から j 列目のマスは透明なマスであり、
# のとき黒いマスです。
シート B,X の各マスも、同様に長さ W_B の文字列 H_B 個 B_1,B_2,\ldots,B_{H_B} および長さ W_X の文字列 H_X 個 X_1,X_2,\ldots,X_{H_X} によって表されます。
高橋君の目標は、次の手順で、シート A,B,C から、A,B に存在する すべての黒いマスを使って シート X を作り出すことです。
- シート A,B をマス目に沿ってシート C に貼り付ける。この時、シート A,B はそれぞれ好きな場所に平行移動させて貼って良いが、シートを切り分けたり、回転させたりしてはいけない。
- シート C からマス目に沿って H_X\times W_X マスの領域を切り出す。ここで、切り出されたシートの各マスは、シート A または B の黒いマスが貼り付けられていれば黒いマスに、そうでなければ透明なマスとなる。
このとき、貼り付ける位置と切り出す領域をうまくとることで高橋君は目標を達成できるか、すなわち次の条件をともにみたすことにできるか判定してください。
- 切り出されたシートはシート A,B の 黒いマスをすべて 含む。切り出されたシートの上でシート A,B の黒いマスどうしが重なって存在していても構わない。
- 切り出されたシートは、回転させたり裏返したりすることなくシート X と一致する。
制約
- 1\leq H_A,W_A,H_B,W_B,H_X,W_X\leq 10
- H_A,W_A,H_B,W_B,H_X,W_X は整数
- A_i は
.と#のみからなる長さ W_A の文字列 - B_i は
.と#のみからなる長さ W_B の文字列 - X_i は
.と#のみからなる長さ W_X の文字列 - シート A,B,X はそれぞれ少なくとも 1 つ以上の黒いマスを含む。
入力
入力は以下の形式で標準入力から与えられる。
H_A W_A
A_1
A_2
\vdots
A_{H_A}
H_B W_B
B_1
B_2
\vdots
B_{H_B}
H_X W_X
X_1
X_2
\vdots
X_{H_X}
出力
高橋君が問題文中の目標を達成できるならば Yes を、できないならば No を出力せよ。
入力例 1
3 5 #.#.. ..... .#... 2 2 #. .# 5 3 ... #.# .#. .#. ...
出力例 1
Yes
まず、シート A をシート C に貼り付けると下図のようになります。
\vdots
.......
.#.#...
\cdots.......\cdots
..#....
.......
\vdots
さらに、シート B をシート A と左上を合わせて貼ってみると下図のようになります。
\vdots
.......
.#.#...
\cdots..#....\cdots
..#....
.......
\vdots
ここで、上で具体的に図示されている範囲のうち、上から 1 行目かつ左から 2 列目のマスを左上として 5\times 3 マスを切り出すと下図のようになります。
... #.# .#. .#. ...
これはシート A,B のすべての黒いマスを含んでおり、また、シート X と一致しているため条件を満たしています。
よって、Yes を出力します。
入力例 2
2 2 #. .# 2 2 #. .# 2 2 ## ##
出力例 2
No
シート A や B を回転させて貼ってはいけないことに注意してください。
入力例 3
1 1 # 1 2 ## 1 1 #
出力例 3
No
どのように貼ったり切り出したりしても、シート B の黒いマスをすべて含むように切り出すことはできないため、1 つめの条件をみたすことができません。
よって、No を出力します。
入力例 4
3 3 ### ... ... 3 3 #.. #.. #.. 3 3 ..# ..# ###
出力例 4
Yes
Score : 300 points
Problem Statement
Takahashi has two sheets A and B, each composed of black squares and transparent squares, and an infinitely large sheet C composed of transparent squares.
There is also an ideal sheet X for Takahashi composed of black squares and transparent squares.
The sizes of sheets A, B, and X are H_A rows \times W_A columns, H_B rows \times W_B columns, and H_X rows \times W_X columns, respectively.
The squares of sheet A are represented by H_A strings of length W_A, A_1, A_2, \ldots, A_{H_A} consisting of . and #.
If the j-th character (1\leq j\leq W_A) of A_i (1\leq i\leq H_A) is ., the square at the i-th row from the top and j-th column from the left is transparent; if it is #, that square is black.
Similarly, the squares of sheets B and X are represented by H_B strings of length W_B, B_1, B_2, \ldots, B_{H_B}, and H_X strings of length W_X, X_1, X_2, \ldots, X_{H_X}, respectively.
Takahashi's goal is to create sheet X using all black squares in sheets A and B by following the steps below with sheets A, B, and C.
- Paste sheets A and B onto sheet C along the grid. Each sheet can be pasted anywhere by translating it, but it cannot be cut or rotated.
- Cut out an H_X\times W_X area from sheet C along the grid. Here, a square of the cut-out sheet will be black if a black square of sheet A or B is pasted there, and transparent otherwise.
Determine whether Takahashi can achieve his goal by appropriately choosing the positions where the sheets are pasted and the area to cut out, that is, whether he can satisfy both of the following conditions.
- The cut-out sheet includes all black squares of sheets A and B. The black squares of sheets A and B may overlap on the cut-out sheet.
- The cut-out sheet coincides sheet X without rotating or flipping.
Constraints
- 1\leq H_A, W_A, H_B, W_B, H_X, W_X\leq 10
- H_A, W_A, H_B, W_B, H_X, W_X are integers.
- A_i is a string of length W_A consisting of
.and#. - B_i is a string of length W_B consisting of
.and#. - X_i is a string of length W_X consisting of
.and#. - Sheets A, B, and X each contain at least one black square.
Input
The input is given from Standard Input in the following format:
H_A W_A
A_1
A_2
\vdots
A_{H_A}
H_B W_B
B_1
B_2
\vdots
B_{H_B}
H_X W_X
X_1
X_2
\vdots
X_{H_X}
Output
If Takahashi can achieve the goal described in the problem statement, print Yes; otherwise, print No.
Sample Input 1
3 5 #.#.. ..... .#... 2 2 #. .# 5 3 ... #.# .#. .#. ...
Sample Output 1
Yes
First, paste sheet A onto sheet C, as shown in the figure below.
\vdots
.......
.#.#...
\cdots.......\cdots
..#....
.......
\vdots
Next, paste sheet B so that its top-left corner aligns with that of sheet A, as shown in the figure below.
\vdots
.......
.#.#...
\cdots..#....\cdots
..#....
.......
\vdots
Now, cut out a 5\times 3 area with the square in the first row and second column of the range illustrated above as the top-left corner, as shown in the figure below.
... #.# .#. .#. ...
This includes all black squares of sheets A and B and matches sheet X, satisfying the conditions.
Therefore, print Yes.
Sample Input 2
2 2 #. .# 2 2 #. .# 2 2 ## ##
Sample Output 2
No
Note that sheets A and B may not be rotated or flipped when pasting them.
Sample Input 3
1 1 # 1 2 ## 1 1 #
Sample Output 3
No
No matter how you paste or cut, you cannot cut out a sheet that includes all black squares of sheet B, so you cannot satisfy the first condition.
Therefore, print No.
Sample Input 4
3 3 ### ... ... 3 3 #.. #.. #.. 3 3 ..# ..# ###
Sample Output 4
Yes
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
配点 : 400 点
問題文
頭と体からなるロボットがあります。 このロボットには、同時に取り付けられる部品が種類 1, 種類 2,\ldots, 種類 N の N 種類あります。 種類 i\ (1\le i\le N) の部品の重さは W _ i です。 それぞれの部品には、頭に取り付けたときと体に取り付けたときで異なる嬉しさがあります。 種類 i\ (1\le i\le N) の部品を頭に取り付けたときの嬉しさは H _ i 、体に取り付けたときの嬉しさは B _ i です。
ロボットは頭の重さが体の重さより大きいと倒れてしまいます。 ここで、頭の重さおよび体の重さはそれぞれ頭もしくは体に取り付けられた部品の重さの合計とします。
高橋くんは、N 種類の部品をすべて 1 個ずつロボットに取り付けたいと思っています。 ロボットを倒さないように部品を取り付けたときの、すべての部品の嬉しさの合計としてありえる最大値を求めてください。
制約
- 1\le N\le500
- 1\le W _ i\le500\ (1\le i\le N)
- 1\le H _ i\le10 ^ 9\ (1\le i\le N)
- 1\le B _ i\le10 ^ 9\ (1\le i\le N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N W _ 1 H _ 1 B _ 1 W _ 2 H _ 2 B _ 2 \vdots W _ N H _ N B _ N
出力
ロボットを倒さないように部品を取り付けたときの、すべての部品の嬉しさの合計としてありえる最大値を出力せよ。
入力例 1
3 1 41 59 2 65 35 8 97 93
出力例 1
217
種類 1 と種類 3 の部品を体に、種類 2 の部品を頭に取り付けることで、ロボットを倒さないようにしつつ嬉しさの合計を 217 にすることができます。
ロボットを倒さないように部品を取り付けて嬉しさの合計を 218 以上にすることはできないため、217 を出力してください。
入力例 2
1 1 1000000000 1
出力例 2
1
唯一の部品を体に取り付けないとロボットは倒れてしまいます。 頭にひとつも部品を取り付けなくてもよいことに注意してください。
入力例 3
2 1 1000000000 1 1 1 1000000000
出力例 3
2000000000
頭の重さと体の重さが等しい場合、ロボットは倒れないことに注意してください。
入力例 4
20 483 984529882 299667119 372 428935469 104847758 467 709733529 102461200 421 659244277 110859936 231 786224280 773073478 351 334234040 193222121 119 404159408 772024933 302 519596088 432627257 433 910226244 337833733 184 406236461 530198622 335 465203041 353047747 418 656273464 114923636 482 972364803 329650748 453 748321854 169441643 105 138464898 587159653 401 832952051 506021805 403 810916971 468755944 231 798801044 749313343 292 631278033 556088607 366 567211596 374825770
出力例 4
12091388792
答えが 2 ^ {32} を超える場合があることに注意してください。
Score : 400 points
Problem Statement
There is a robot consisting of a head and a body. This robot has N types of parts that can be attached simultaneously: type 1, type 2,\ldots, type N. The weight of the type i\ (1\le i\le N) part is W _ i. Each part has a different happiness when attached to the head versus when attached to the body. The happiness when the type i\ (1\le i\le N) part is attached to the head is H _ i, and the happiness when attached to the body is B _ i.
The robot falls over if the weight of the head is greater than the weight of the body. Here, the weight of the head and the weight of the body are the sums of the weights of the parts attached to the head or body, respectively.
Takahashi wants to attach all N types of parts to the robot, one of each. Find the maximum possible sum of the happiness of all parts when the parts are attached without causing the robot to fall over.
Constraints
- 1\le N\le500
- 1\le W _ i\le500\ (1\le i\le N)
- 1\le H _ i\le10 ^ 9\ (1\le i\le N)
- 1\le B _ i\le10 ^ 9\ (1\le i\le N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N W _ 1 H _ 1 B _ 1 W _ 2 H _ 2 B _ 2 \vdots W _ N H _ N B _ N
Output
Print the maximum possible sum of the happiness of all parts when the parts are attached without causing the robot to fall over.
Sample Input 1
3 1 41 59 2 65 35 8 97 93
Sample Output 1
217
By attaching type 1 and type 3 parts to the body and type 2 part to the head, the robot does not fall over and the sum of happiness can be made 217.
It is not possible to attach the parts without causing the robot to fall over and make the sum of happiness 218 or more, so print 217.
Sample Input 2
1 1 1000000000 1
Sample Output 2
1
The robot will fall over if the only part is not attached to the body. Note that it is acceptable to attach no parts to the head.
Sample Input 3
2 1 1000000000 1 1 1 1000000000
Sample Output 3
2000000000
Note that the robot does not fall over if the head and body have equal weights.
Sample Input 4
20 483 984529882 299667119 372 428935469 104847758 467 709733529 102461200 421 659244277 110859936 231 786224280 773073478 351 334234040 193222121 119 404159408 772024933 302 519596088 432627257 433 910226244 337833733 184 406236461 530198622 335 465203041 353047747 418 656273464 114923636 482 972364803 329650748 453 748321854 169441643 105 138464898 587159653 401 832952051 506021805 403 810916971 468755944 231 798801044 749313343 292 631278033 556088607 366 567211596 374825770
Sample Output 4
12091388792
Note that the answer can exceed 2 ^ {32}.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
高橋くんは冒険に出ようとしています。
冒険では、N 個の出来事が起こります。 i 番目 (1\leq i\leq N) の出来事は整数の組 (t _ i,x _ i) (1\leq t _ i\leq 2,1\leq x _ i\leq N) で表され、次のような出来事です。
- t _ i=1 のとき、タイプ x _ i のポーションを 1 つ発見する。高橋くんは、発見したポーションを拾うか捨てるかのどちらかを選択する。
- t _ i=2 のとき、タイプ x _ i のモンスター 1 体と遭遇する。高橋くんがタイプ x _ i のポーションを持っている場合、それを 1 つ消費することでモンスターを撃退することができる。モンスターを撃退しなかった場合、高橋くんは敗北する。
高橋くんが敗北することなく全てのモンスターを撃退することができるか判定してください。
高橋くんが全てのモンスターを撃退することができない場合、-1 を出力してください。
高橋くんが全てのモンスターを撃退することができる場合、高橋君が冒険の途中で持っているポーションの個数の最大値を K とします。 高橋くんが敗北しないような戦略全体にわたる K の最小値を K _ {\min} とします。 K _ {\min} の値と、K _ {\min} を達成する高橋くんの行動を出力してください。
制約
- 1\leq N\leq2\times10^5
- 1\leq t _ i\leq2\ (1\leq i\leq N)
- 1\leq x _ i\leq N\ (1\leq i\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N t _ 1 x _ 1 t _ 2 x _ 2 \vdots t _ N x _ N
出力
高橋くんが全てのモンスターを撃退することができない場合、-1 を出力せよ。
高橋くんが全てのモンスターを撃退することができる場合、1 行目には K _ {\min} の値を、2 行目には t _ i=1 であるような i すべてについて昇順に、i 番目の出来事で発見したポーションを拾うなら 1 を、拾わないなら 0 を空白区切りで出力せよ。
K _ {\min} を達成し、高橋くんが敗北せず冒険を終えられるような行動が複数ある場合、どれを出力しても構わない。
入力例 1
13 1 2 1 3 1 1 1 3 1 2 2 3 1 3 1 3 2 3 1 3 2 2 2 3 2 1
出力例 1
3 1 1 1 0 0 1 0 1
出力例は、次のような行動に対応しています。
- タイプ 2,3,1 のポーションをこの順に発見する。これらのポーションをすべて拾う。
- タイプ 3,2 のポーションをこの順に発見する。これらのポーションをいずれも拾わない。
- タイプ 3 のモンスターと遭遇する。持っているタイプ 3 のポーションを 1 つ消費してモンスターを撃退する。
- タイプ 3 のポーションを発見する。このポーションを拾う。
- タイプ 3 のポーションを発見する。このポーションを拾わない。
- タイプ 3 のモンスターと遭遇する。持っているタイプ 3 のポーションを 1 つ消費してモンスターを撃退する。
- タイプ 3 のポーションを発見する。このポーションを拾う。
- タイプ 2 のモンスターと遭遇する。持っているタイプ 2 のポーションを 1 つ消費してモンスターを撃退する。
- タイプ 3 のモンスターと遭遇する。持っているタイプ 3 のポーションを 1 つ消費してモンスターを撃退する。
- タイプ 1 のモンスターと遭遇する。持っているタイプ 1 のポーションを 1 つ消費してモンスターを撃退する。
この行動では、K の値は 3 となります。
K\leq 2 として敗北しない方法はないので、求める K _ {\min} の値は 3 です。 K=3 を満たして高橋くんが敗北しない行動は複数ありますが、どれを出力しても構いません。
入力例 2
4 2 3 1 4 2 1 1 2
出力例 2
-1
高橋くんはかならず最初に遭遇するモンスターに敗北してしまいます。
入力例 3
30 1 25 1 2 1 10 1 18 2 18 1 11 2 11 1 21 1 6 2 2 2 10 1 11 1 24 1 11 1 3 1 2 1 18 2 25 1 8 1 10 1 11 2 18 2 10 1 10 2 2 1 24 1 10 2 10 1 25 2 6
出力例 3
4 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0
Score : 450 points
Problem Statement
Takahashi will embark on an adventure.
During the adventure, N events will occur. The i-th event (1\leq i\leq N) is represented by a pair of integers (t _ i,x _ i) (1\leq t _ i\leq 2,1\leq x _ i\leq N) and is as follows:
- If t _ i=1, he finds one potion of type x _ i. He can choose to pick it up or discard it.
- If t _ i=2, he encounters one monster of type x _ i. If he has a potion of type x _ i, he can use one to defeat the monster. If he does not defeat it, he will be defeated.
Determine whether he can defeat all the monsters without being defeated.
If he cannot defeat all the monsters, print -1.
Otherwise, let K be the maximum number of potions he has at some point during the adventure. Let K _ {\min} be the minimum value of K across all strategies where he will not be defeated. Print the value of K _ {\min} and the actions of Takahashi that achieve K _ {\min}.
Constraints
- 1\leq N\leq2\times10^5
- 1\leq t _ i\leq2\ (1\leq i\leq N)
- 1\leq x _ i\leq N\ (1\leq i\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N t _ 1 x _ 1 t _ 2 x _ 2 \vdots t _ N x _ N
Output
If Takahashi cannot defeat all the monsters, print -1.
If he can, print the value of K _ {\min} in the first line, and in the second line, for each i such that t _ i=1 in ascending order, print 1 if he picks up the potion found at the i-th event, and 0 otherwise, separated by spaces.
If multiple sequences of actions achieve K _ {\min} and allow him to finish the adventure without being defeated, you may print any of them.
Sample Input 1
13 1 2 1 3 1 1 1 3 1 2 2 3 1 3 1 3 2 3 1 3 2 2 2 3 2 1
Sample Output 1
3 1 1 1 0 0 1 0 1
The sample output corresponds to the following actions:
- Find potions of types 2,3,1 in this order. Pick up all of them.
- Find potions of types 3,2 in this order. Do not pick up any of them.
- Encounter a type-3 monster. Use one type-3 potion to defeat it.
- Find a type-3 potion. Pick it up.
- Find a type-3 potion. Do not pick it up.
- Encounter a type-3 monster. Use one type-3 potion to defeat it.
- Find a type-3 potion. Pick it up.
- Encounter a type-2 monster. Use one type-2 potion to defeat it.
- Encounter a type-3 monster. Use one type-3 potion to defeat it.
- Encounter a type-1 monster. Use one type-1 potion to defeat it.
In this sequence of actions, the value of K is 3.
There is no way to avoid defeat with K\leq 2, so the sought value of K _ {\min} is 3. There are multiple sequences of actions that satisfy K=3 and allow him to avoid defeat; you may print any of them.
Sample Input 2
4 2 3 1 4 2 1 1 2
Sample Output 2
-1
He will inevitably be defeated by the first monster he encounters.
Sample Input 3
30 1 25 1 2 1 10 1 18 2 18 1 11 2 11 1 21 1 6 2 2 2 10 1 11 1 24 1 11 1 3 1 2 1 18 2 25 1 8 1 10 1 11 2 18 2 10 1 10 2 2 1 24 1 10 2 10 1 25 2 6
Sample Output 3
4 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
N\times N のマス目があり、上から i 行目、左から j 列目 (1\leq i,j\leq N) のマスには整数 A _ {i,j} が書かれています。
整数 M が与えられます。 M\times M のマス目を重ならないように 3 つ選ぶときの、選んだマス目に書かれている整数の総和としてありえる最大値を求めてください。
問題の厳密な定義
整数の 6 つ組 (i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3) が次の 3 つの条件を満たしているとき、良い 6 つ組ということにします。- 1\leq i _ k\leq N-M+1\ (k=1,2,3)
- 1\leq j _ k\leq N-M+1\ (k=1,2,3)
- k\neq l\ (k,l\in\lbrace1,2,3\rbrace) ならば、\lbrace(i,j)\mid i _ k\leq i\lt i _ k+M\wedge j _ k\leq j\lt j _ k+M\rbrace と \lbrace(i,j)\mid i _ l\leq i\lt i _ l+M\wedge j _ l\leq j\lt j _ l+M\rbrace に共通部分はない
制約
- 2\leq N\leq 1000
- 1\leq M\leq N/2
- 0\leq A _ {i,j}\leq10 ^ 9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
A _ {1,1} A _ {1,2} \ldots A _ {1,N}
A _ {2,1} A _ {2,2} \ldots A _ {2,N}
\vdots \ \vdots \ddots \vdots
A _ {N,1} A _ {N,2} \ldots A _ {N,N}
出力
答えを出力せよ。
入力例 1
7 3 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7 5
出力例 1
154
与えられたグリッドから、以下の図のように 3\times3 のマス目を 3 つ選ぶと(これは (i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3)=(1,5,2,1,5,2) とすることに対応します)、選んだマス目に書かれている数の合計は 154 となります。

問題文の条件を満たす選び方であって選んだマス目に書かれている数の合計が 155 以上であるものは存在しないため、154 を出力してください。
入力例 2
7 1 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7 5
出力例 2
27
以下のように選ぶのが最適です。

入力例 3
16 4 74 16 58 32 97 52 43 51 40 58 13 24 65 11 63 29 98 75 40 77 15 50 83 85 35 46 38 37 56 38 63 55 95 42 10 70 53 40 25 10 70 32 33 19 52 79 74 58 33 91 53 11 65 63 78 77 81 46 81 63 11 82 55 62 39 95 92 69 77 89 14 84 53 78 71 81 66 39 96 29 74 26 60 55 89 35 32 64 17 26 74 92 84 33 59 82 23 69 10 95 94 14 58 58 97 95 62 58 72 55 71 43 93 77 27 87 74 72 91 37 53 80 51 71 37 35 97 46 81 88 26 79 78 30 53 68 83 28 59 28 74 55 20 86 93 13 25 19 53 53 17 24 69 14 67 81 10 19 69 90 88 83 62 92 22 31 27 34 67 48 42 32 68 14 96 87 44 69 25 48 68 42 53 82 44 42 96 31 13 56 68 83 63 87 24 75 16 70 63 99 95 10 63 26 56 12 77 49 94 83 69 95 48 41 40 97 45 61 26 38 83 91 44 31 43 69 54 64 20 60 17 15 62 25 58 50 59 63 88 70 72 95 21 28 41 14 77 22 64 78 33 55 67 51 78 40
出力例 3
3295
以下のように選ぶのが最適です。

Score: 525 points
Problem Statement
There is an N\times N grid, and the cell at the i-th row from the top and the j-th column from the left (1\leq i,j\leq N) contains the integer A _ {i,j}.
You are given an integer M. When choosing three non-overlapping M\times M grids, find the maximum possible sum of the integers written in the chosen grids.
Formal definition of the problem
A 6-tuple of integers (i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3) is called a good 6-tuple when it satisfies the following three conditions:- 1\leq i _ k\leq N-M+1\ (k=1,2,3)
- 1\leq j _ k\leq N-M+1\ (k=1,2,3)
- If k\neq l\ (k,l\in\lbrace1,2,3\rbrace), the sets \lbrace(i,j)\mid i _ k\leq i\lt i _ k+M\wedge j _ k\leq j\lt j _ k+M\rbrace and \lbrace(i,j)\mid i _ l\leq i\lt i _ l+M\wedge j _ l\leq j\lt j _ l+M\rbrace do not intersect.
Constraints
- 2\leq N\leq 1000
- 1\leq M\leq N/2
- 0\leq A _ {i,j}\leq10 ^ 9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
A _ {1,1} A _ {1,2} \ldots A _ {1,N}
A _ {2,1} A _ {2,2} \ldots A _ {2,N}
\vdots \ \vdots \ddots \vdots
A _ {N,1} A _ {N,2} \ldots A _ {N,N}
Output
Print the answer.
Sample Input 1
7 3 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7 5
Sample Output 1
154
From the given grid, if we choose three 3\times3 grids as shown in the figure below (this corresponds to setting (i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3)=(1,5,2,1,5,2)), the sum of the numbers written in the chosen grids will be 154.

There is no way to make the sum 155 or greater while satisfying the conditions in the problem statement, so print 154.
Sample Input 2
7 1 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7 5
Sample Output 2
27
The following choice is optimal.

Sample Input 3
16 4 74 16 58 32 97 52 43 51 40 58 13 24 65 11 63 29 98 75 40 77 15 50 83 85 35 46 38 37 56 38 63 55 95 42 10 70 53 40 25 10 70 32 33 19 52 79 74 58 33 91 53 11 65 63 78 77 81 46 81 63 11 82 55 62 39 95 92 69 77 89 14 84 53 78 71 81 66 39 96 29 74 26 60 55 89 35 32 64 17 26 74 92 84 33 59 82 23 69 10 95 94 14 58 58 97 95 62 58 72 55 71 43 93 77 27 87 74 72 91 37 53 80 51 71 37 35 97 46 81 88 26 79 78 30 53 68 83 28 59 28 74 55 20 86 93 13 25 19 53 53 17 24 69 14 67 81 10 19 69 90 88 83 62 92 22 31 27 34 67 48 42 32 68 14 96 87 44 69 25 48 68 42 53 82 44 42 96 31 13 56 68 83 63 87 24 75 16 70 63 99 95 10 63 26 56 12 77 49 94 83 69 95 48 41 40 97 45 61 26 38 83 91 44 31 43 69 54 64 20 60 17 15 62 25 58 50 59 63 88 70 72 95 21 28 41 14 77 22 64 78 33 55 67 51 78 40
Sample Output 3
3295
The following choice is optimal.
