Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
整数 R,C と 2 行 2 列からなる行列 A が与えられるので、 A_{R,C} を出力してください。
制約
- 入力は全て整数
- 1 \le R,C \le 2
- 0 \le A_{i,j} \le 100
入力
入力は以下の形式で標準入力から与えられる。
R C
A_{1,1} A_{1,2}
A_{2,1} A_{2,2}
出力
答えを整数として出力せよ。
入力例 1
1 2 1 0 0 1
出力例 1
0
A_{1,2}=0 です。
入力例 2
2 2 1 2 3 4
出力例 2
4
A_{2,2}=4 です。
入力例 3
2 1 90 80 70 60
出力例 3
70
A_{2,1}=70 です。
Score : 100 points
Problem Statement
Given integers R, C, and a 2 \times 2 matrix A, print A_{R,C}.
Constraints
- All values in input are integers.
- 1 \le R,C \le 2
- 0 \le A_{i,j} \le 100
Input
Input is given from Standard Input in the following format:
R C
A_{1,1} A_{1,2}
A_{2,1} A_{2,2}
Output
Print the answer as an integer.
Sample Input 1
1 2 1 0 0 1
Sample Output 1
0
We have A_{1,2}=0.
Sample Input 2
2 2 1 2 3 4
Sample Output 2
4
We have A_{2,2}=4.
Sample Input 3
2 1 90 80 70 60
Sample Output 3
70
We have A_{2,1}=70.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
高橋君は、レストランで「AtCoder ドリンク」というドリンクを飲もうとしています。 AtCoder ドリンクは定価である P 円を払えば飲むことができます。
また、高橋君は割引券を持っており、それを使うと AtCoder ドリンクを定価より安い価格である Q 円で飲むことができますが、 その場合には AtCoder ドリンクの他に、N 品ある料理の中から 1 つを追加で注文しなければなりません。 i = 1, 2, \ldots, N について、i 番目の料理の価格は D_i 円です。
高橋君がドリンクを飲むため支払う合計金額の最小値を出力してください。
制約
- 1 \leq N \leq 100
- 1 \leq Q \lt P \leq 10^5
- 1 \leq D_i \leq 10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N P Q D_1 D_2 \ldots D_N
出力
答えを出力せよ。
入力例 1
3 100 50 60 20 40
出力例 1
70
割引券を使用して 2 番目の料理を注文することで、ドリンク代 50 円と料理代 20 円の合計 70 円の支払いで AtCoder ドリンクを飲むことができ、支払う合計金額が最小となります。
入力例 2
3 100 50 60000 20000 40000
出力例 2
100
割引券を使用せず定価の 100 円で AtCoder ドリンクを飲むことで、支払う合計金額が最小となります。
Score : 100 points
Problem Statement
Takahashi wants a beverage called AtCoder Drink in a restaurant. It can be ordered at a regular price of P yen.
He also has a discount coupon that allows him to order it at a lower price of Q yen. However, he must additionally order one of the restaurant's N dishes to use that coupon. For each i = 1, 2, \ldots, N, the price of the i-th dish is D_i yen.
Print the minimum total amount of money that he must pay to get the drink.
Constraints
- 1 \leq N \leq 100
- 1 \leq Q \lt P \leq 10^5
- 1 \leq D_i \leq 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P Q D_1 D_2 \ldots D_N
Output
Print the answer.
Sample Input 1
3 100 50 60 20 40
Sample Output 1
70
If he uses the coupon and orders the second dish, he can get the drink by paying 50 yen for it and 20 yen for the dish, for a total of 70 yen, which is the minimum total payment needed.
Sample Input 2
3 100 50 60000 20000 40000
Sample Output 2
100
The total payment will be minimized by not using the coupon and paying the regular price of 100 yen.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
以下の図で表される正五角形 P があります。
P の点 S_1 と点 S_2 を結ぶ線分と、点 T_1 と点 T_2 を結ぶ線分の長さが等しいか判定してください。
制約
- S_1,S_2,T_1,T_2 は
A,B,C,D,Eのいずれかの文字 - S_1 \neq S_2
- T_1 \neq T_2
入力
入力は以下の形式で標準入力から与えられる。
S_1S_2 T_1T_2
出力
P の点 S_1 と点 S_2 を結ぶ線分と、点 T_1 と点 T_2 を結ぶ線分の長さが等しい場合 Yes を、等しくない場合 No を出力せよ。
入力例 1
AC EC
出力例 1
Yes
P の点 A と点 C を結ぶ線分と、P の点 E と点 C を結ぶ線分の長さは等しいです。
入力例 2
DA EA
出力例 2
No
P の点 D と点 A を結ぶ線分と、P の点 E と点 A を結ぶ線分の長さは等しくありません。
入力例 3
BD BD
出力例 3
Yes
Score : 200 points
Problem Statement
A regular pentagon P is shown in the figure below.
Determine whether the length of the line segment connecting points S_1 and S_2 of P equals the length of the line segment connecting points T_1 and T_2.
Constraints
- Each of S_1, S_2, T_1, and T_2 is one of the characters
A,B,C,D, andE. - S_1 \neq S_2
- T_1 \neq T_2
Input
The input is given from Standard Input in the following format:
S_1S_2 T_1T_2
Output
If the length of the line segment connecting points S_1 and S_2 of P equals the length of the line segment connecting points T_1 and T_2, print Yes; otherwise, print No.
Sample Input 1
AC EC
Sample Output 1
Yes
The length of the line segment connecting point A and point C of P equals the length of the line segment connecting point E and point C.
Sample Input 2
DA EA
Sample Output 2
No
The length of the line segment connecting point D and point A of P does not equal the length of the line segment connecting point E and point A.
Sample Input 3
BD BD
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
縦 R 行横 C 列の盤面があります。上から i 行目、左から j 列目のマスを (i,j) と表します。
(i,j) の現在の状態が文字 B_{i,j} として与えられます。
. は空きマス、# は壁があるマスを表し、
1, 2,\dots, 9 はそれぞれ威力 1,2,\dots,9 の爆弾があるマスを表します。
次の瞬間に、全ての爆弾が同時に爆発します。 爆弾が爆発すると、爆弾があるマスからのマンハッタン距離がその爆弾の威力以下であるような全てのマス（その爆弾があるマス自体を含む）が空きマスに変わります。 ここで、(r_1,c_1) から (r_2,c_2) までのマンハッタン距離は |r_1-r_2|+|c_1-c_2| です。
爆発後の盤面を出力してください。
制約
- 1\leq R,C \leq 20
- R,C は整数
- B_{i,j} は
.,#,1,2,\dots,9のいずれかである
入力
入力は以下の形式で標準入力から与えられる。
R C
B_{1,1}B_{1,2}\dots B_{1,C}
\vdots
B_{R,1}B_{R,2}\dots B_{R,C}
出力
爆発後の盤面を R 行で出力せよ。盤面の表し方は入力と同じ形式を用いること (R と C を出力する必要はない)。
入力例 1
4 4 .1.# ###. .#2. #.##
出力例 1
...# #... .... #...
- (1,2) にある爆弾の爆発によって、上図の青いマスと紫のマスが空きマスに変わります。
- (3,3) にある爆弾の爆発によって、上図の赤いマスと紫のマスが空きマスに変わります。
この例のように、爆弾が効果を及ぼす範囲に被りがあることもあります。
入力例 2
2 5 ..#.# ###.#
出力例 2
..#.# ###.#
爆弾が 1 つもないこともあります。
入力例 3
2 3 11# ###
出力例 3
... ..#
入力例 4
4 6 #.#3#. ###.#. ##.### #1..#.
出力例 4
...... #..... #....# ....#.
Score : 200 points
Problem Statement
We have a board with R rows running horizontally and C columns running vertically. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.
You are given characters B_{i,j} representing the current states of (i,j).
. represents an empty square; # represents a square with a wall; 1, 2,\dots, 9 represent a square with a bomb of power 1,2,\dots,9, respectively.
At the next moment, all bombs will explode simultaneously. When a bomb explodes, every square whose Manhattan distance from the square with the bomb is not greater than the power of the bomb will turn into an empty square. Here, the Manhattan distance from (r_1,c_1) to (r_2,c_2) is |r_1-r_2|+|c_1-c_2|.
Print the board after the explosions.
Constraints
- 1\leq R,C \leq 20
- R and C are integers.
- Each B_{i,j} is one of
.,#,1,2, \dots,9.
Input
The input is given from Standard Input in the following format:
R C
B_{1,1}B_{1,2}\dots B_{1,C}
\vdots
B_{R,1}B_{R,2}\dots B_{R,C}
Output
Print R lines representing the board after the explosions. Use the format used in the input (do not print R or C).
Sample Input 1
4 4 .1.# ###. .#2. #.##
Sample Output 1
...# #... .... #...
- The explosion of the bomb at (1,2) will turn the blue squares and purple squares in the above figure into empty squares.
- The explosion of the bomb at (3,3) will turn the red squares and purple squares in the above figure into empty squares.
As seen in this sample, the explosion ranges of bombs may overlap.
Sample Input 2
2 5 ..#.# ###.#
Sample Output 2
..#.# ###.#
There may be no bombs.
Sample Input 3
2 3 11# ###
Sample Output 3
... ..#
Sample Input 4
4 6 #.#3#. ###.#. ##.### #1..#.
Sample Output 4
...... #..... #....# ....#.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の数列 A = (A_1, A_2, \ldots, A_N) が与えられます。 K = 0, 1, 2, \ldots, N-1 のそれぞれについて、下記の問題を解いてください。
1 以上 N 以下の整数 i であって、次の条件を満たすものの個数を求めよ。
- A に含まれる整数のうち A_i より大きいものはちょうど K 種類である。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
N 行出力せよ。 i = 1, 2, \ldots, N について、i 行目には K = i-1 の場合の問題の答えを出力せよ。
入力例 1
6 2 7 1 8 2 8
出力例 1
2 1 2 1 0 0
例として、K = 2 の場合の問題の答えを以下で求めます。
- A_1 = 2 に関して、A に含まれる整数のうち A_1 より大きいものは、7, 8 の 2 種類です。
- A_2 = 7 に関して、A に含まれる整数のうち A_2 より大きいものは、8 の 1 種類です。
- A_3 = 1 に関して、A に含まれる整数のうち A_3 より大きいものは、2, 7, 8 の 3 種類です。
- A_4 = 8 に関して、A に含まれる整数のうち A_4 より大きいものは、0 種類です（存在しません）。
- A_5 = 2 に関して、A に含まれる整数のうち A_5 より大きいものは、7, 8 の 2 種類です。
- A_6 = 8 に関して、A に含まれる整数のうち A_6 より大きいものは、0 種類です（存在しません）。
よって、A に含まれる整数のうちA_i より大きいものがちょうど K = 2 種類であるような i は、i = 1 と i = 5 の 2 つです。よって、K = 2 の場合の答えは 2 です。
入力例 2
1 1
出力例 2
1
入力例 3
10 979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527
出力例 3
2 1 2 1 2 1 1 0 0 0
Score : 300 points
Problem Statement
You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N. For each K = 0, 1, 2, \ldots, N-1, solve the following problem.
Find the number of integers i between 1 and N (inclusive) such that:
- A contains exactly K distinct integers greater than A_i.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print N lines. For i = 1, 2, \ldots, N, the i-th line should contain the answer for K = i-1.
Sample Input 1
6 2 7 1 8 2 8
Sample Output 1
2 1 2 1 0 0
For example, we will find the answer for K=2.
- Regarding A_1 = 2, A contains 2 distinct integers greater than A_1: 7 and 8.
- Regarding A_2 = 7, A contains 1 distinct integer greater than A_2: 8.
- Regarding A_3 = 1, A contains 3 distinct integers greater than A_3: 2, 7, and 8.
- Regarding A_4 = 8, A contains 0 distinct integers greater than A_4 (there is no such integer).
- Regarding A_5 = 2, A contains 2 distinct integers greater than A_5: 7 and 8.
- Regarding A_6 = 8, A contains 0 distinct integers greater than A_6 (there is no such integer).
Thus, there are two i's, i = 1 and i = 5, such that A contains exactly K = 2 distinct integers greater than A_i. Therefore, the answer for K = 2 is 2.
Sample Input 2
1 1
Sample Output 2
1
Sample Input 3
10 979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527
Sample Output 3
2 1 2 1 2 1 1 0 0 0
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
整数列 A=(A_1,A_2,\dots,A_N) があります。 あなたは次の操作を好きな回数（0 回でもよい）行うことができます。
- 1\leq i,j \leq N を満たす整数 i,j を選ぶ。A_i を 1 減らし、A_j を 1 増やす。
A の最小値と最大値の差を 1 以下にするために必要な最小の操作回数を求めてください。
制約
- 1\leq N \leq 2\times 10^5
- 1\leq A_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
4 4 7 3 7
出力例 1
3
以下のように 3 回の操作を行うことで、A の最小値と最大値の差を 1 以下にすることができます。
- i=2,j=3 として操作を行う。A=(4,6,4,7) になる。
- i=4,j=1 として操作を行う。A=(5,6,4,6) になる。
- i=4,j=3 として操作を行う。A=(5,6,5,5) になる。
3 回未満の操作で A の最小値と最大値の差を 1 以下にすることはできません。よって答えは 3 です。
入力例 2
1 313
出力例 2
0
入力例 3
10 999999997 999999999 4 3 2 4 999999990 8 999999991 999999993
出力例 3
2499999974
Score : 400 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\dots,A_N). You can perform the following operation any number of times (possibly zero).
- Choose integers i and j with 1\leq i,j \leq N. Decrease A_i by one and increase A_j by one.
Find the minimum number of operations required to make the difference between the minimum and maximum values of A at most one.
Constraints
- 1\leq N \leq 2\times 10^5
- 1\leq A_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
Output
Print the answer as an integer.
Sample Input 1
4 4 7 3 7
Sample Output 1
3
By the following three operations, the difference between the minimum and maximum values of A becomes at most one.
- Choose i=2 and j=3 to make A=(4,6,4,7).
- Choose i=4 and j=1 to make A=(5,6,4,6).
- Choose i=4 and j=3 to make A=(5,6,5,5).
You cannot make the difference between maximum and minimum values of A at most one by less than three operations, so the answer is 3.
Sample Input 2
1 313
Sample Output 2
0
Sample Input 3
10 999999997 999999999 4 3 2 4 999999990 8 999999991 999999993
Sample Output 3
2499999974
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
N_1+N_2 頂点 M 辺の無向グラフがあります。i=1,2,\ldots,M に対し、i 番目の辺は頂点 a_i と頂点 b_i を結びます。
また、以下を満たすことが保障されます。
- 1 \leq u,v \leq N_1 を満たす整数 u,v に対し、頂点 u と頂点 v は連結
- N_1+1 \leq u,v \leq N_1+N_2 を満たす整数 u,v に対し、頂点 u と頂点 v は連結
- 頂点 1 と頂点 N_1+N_2 は非連結
次の操作をちょうど 1 回行います。
- 1 \leq u \leq N_1 を満たす整数 u と N_1+1 \leq v \leq N_1+N_2 を満たす整数 v を選び、頂点 u と頂点 v を結ぶ辺を追加する
操作後のグラフにおいて、頂点 1 と頂点 N_1+N_2 は必ず連結であることが示せます。そこで、頂点 1 と頂点 N_1+N_2 を結ぶ経路の長さ(辺の本数)の最小値を d とします。
操作で追加する辺を適切に選んだ時にありえる d の最大値を求めてください。
連結とは？
無向グラフの頂点 u,v が連結であるとは、頂点 u と頂点 v を結ぶ経路が存在することをいいます。制約
- 1 \leq N_1,N_2 \leq 1.5 \times 10^5
- 0 \leq M \leq 3 \times 10^5
- 1 \leq a_i \leq b_i \leq N_1+N_2
- i \neq j ならば (a_i,b_i) \neq (a_j,b_j)
- 1 \leq u,v \leq N_1 を満たす整数 u,v に対し、頂点 u と頂点 v は連結
- N_1+1 \leq u,v \leq N_1+N_2 を満たす整数 u,v に対し、頂点 u と頂点 v は連結
- 頂点 1 と頂点 N_1+N_2 は非連結
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N_1 N_2 M a_1 b_1 \vdots a_M b_M
出力
答えを出力せよ。
入力例 1
3 4 6 1 2 2 3 4 5 4 6 1 3 6 7
出力例 1
5
u=2,v=5 として操作することで d=5 と出来ます。これが最大値です。
入力例 2
7 5 20 10 11 4 5 10 12 1 2 1 5 5 6 2 4 3 5 9 10 2 5 1 4 11 12 9 12 8 9 5 7 3 7 3 6 3 4 8 12 9 11
出力例 2
4
Score : 400 points
Problem Statement
We have an undirected graph with (N_1+N_2) vertices and M edges. For i=1,2,\ldots,M, the i-th edge connects vertex a_i and vertex b_i.
The following properties are guaranteed:
- Vertex u and vertex v are connected, for all integers u and v with 1 \leq u,v \leq N_1.
- Vertex u and vertex v are connected, for all integers u and v with N_1+1 \leq u,v \leq N_1+N_2.
- Vertex 1 and vertex (N_1+N_2) are disconnected.
Consider performing the following operation exactly once:
- choose an integer u with 1 \leq u \leq N_1 and an integer v with N_1+1 \leq v \leq N_1+N_2, and add an edge connecting vertex u and vertex v.
We can show that vertex 1 and vertex (N_1+N_2) are always connected in the resulting graph; so let d be the minimum length (number of edges) of a path between vertex 1 and vertex (N_1+N_2).
Find the maximum possible d resulting from adding an appropriate edge to add.
Definition of "connected"
Two vertices u and v of an undirected graph are said to be connected if and only if there is a path between vertex u and vertex v.Constraints
- 1 \leq N_1,N_2 \leq 1.5 \times 10^5
- 0 \leq M \leq 3 \times 10^5
- 1 \leq a_i \leq b_i \leq N_1+N_2
- (a_i,b_i) \neq (a_j,b_j) if i \neq j.
- Vertex u and vertex v are connected for all integers u and v such that 1 \leq u,v \leq N_1.
- Vertex u and vertex v are connected for all integers u and v such that N_1+1 \leq u,v \leq N_1+N_2.
- Vertex 1 and vertex (N_1+N_2) are disconnected.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N_1 N_2 M a_1 b_1 \vdots a_M b_M
Output
Print the answer.
Sample Input 1
3 4 6 1 2 2 3 4 5 4 6 1 3 6 7
Sample Output 1
5
If we set u=2 and v=5, the operation yields d=5, which is the maximum possible.
Sample Input 2
7 5 20 10 11 4 5 10 12 1 2 1 5 5 6 2 4 3 5 9 10 2 5 1 4 11 12 9 12 8 9 5 7 3 7 3 6 3 4 8 12 9 11
Sample Output 2
4
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
長さ N の整数列 A=(A_1,\ldots,A_N) が与えられます。次の式の値を求めてください。
ビット単位 xor とは
非負整数 A, B のビット単位 xor 、A \oplus B は、以下のように定義されます。- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の整数 p_1, \dots, p_k の排他的論理和は (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k) と定義され、これは p_1, \dots, p_k の順番によらないことが証明できます。
制約
- 2\leq N\leq 2\times 10^5
- 1\leq A_i \leq 10^8
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \ldots A_{N}
出力
答えを出力せよ。
入力例 1
3 1 3 2
出力例 1
3
A_1\oplus A_2 = 2, A_1 \oplus A_2\oplus A_3 = 0, A_2\oplus A_3 = 1 なので答えは 2+0+1=3 です。
入力例 2
7 2 5 6 5 2 1 7
出力例 2
83
Score : 450 points
Problem Statement
You are given an integer sequence A=(A_1,\ldots,A_N) of length N. Find the value of the following expression:
Notes on bitwise XOR
The bitwise XOR of non-negative integers A and B, denoted as A \oplus B, is defined as follows:- In the binary representation of A \oplus B, the digit at the 2^k (k \geq 0) position is 1 if and only if exactly one of the digits at the 2^k position in the binary representations of A and B is 1; otherwise, it is 0.
In general, the bitwise XOR of k integers p_1, \dots, p_k is defined as (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k). It can be proved that this is independent of the order of p_1, \dots, p_k.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^8
- 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
Print the answer.
Sample Input 1
3 1 3 2
Sample Output 1
3
A_1 \oplus A_2 = 2, A_1 \oplus A_2 \oplus A_3 = 0, and A_2 \oplus A_3 = 1, so the answer is 2 + 0 + 1 = 3.
Sample Input 2
7 2 5 6 5 2 1 7
Sample Output 2
83
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
N 頂点の木があります。 1 番目の頂点が根であり、i 番目 (2\leq i\leq N) の頂点の親は p _ i\ (1\leq p _ i\lt i) です。
根でない頂点には、敵か薬のどちらか一方が配置されています。 高橋くんは、すべての敵を倒したいです。 はじめ、高橋くんの強さは 1 で、頂点 1 にいます。 i=2,\ldots,N について、i 番目の頂点の情報は整数の組 (t _ i,s _ i,g _ i) を用いて次のように表されます。
- t _ i=1 ならば i 番目の頂点には敵がいます。この頂点に高橋くんが初めて訪れたとき、高橋くんの強さが s _ i 未満だった場合高橋くんは敵に倒されて敗北し、高橋くんは他の頂点に移動できなくなります。そうでなかった場合、高橋くんは敵を倒し、強さが g _ i 上昇します。
- t _ i=2 ならば i 番目の頂点には薬があります。この頂点に高橋くんが初めて訪れたとき、高橋くんは薬を飲み、強さが g _ i 倍になります。（薬がある頂点では、s _ i=0 です。）
薬がある頂点はたかだか 10 個です。
高橋くんは、隣接する頂点に移動することができます。 高橋くんがすべての敵を倒すことができるか判定してください。
制約
- 2\leq N\leq 500
- 1\leq p _ i\lt i\ (2\leq i\leq N)
- t _ i\in\lbrace1,2\rbrace\ (2\leq i\leq N)
- t _ i=1\implies1\leq s _ i\leq 10 ^ 9\ (2\leq i\leq N)
- t _ i=2\implies s _ i=0\ (2\leq i\leq N)
- 1\leq g _ i\leq 10 ^ 9\ (2\leq i\leq N)
- t _ i=2 である頂点は 10 個以下
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N p _ 2 t _ 2 s _ 2 g _ 2 p _ 3 t _ 3 s _ 3 g _ 3 \vdots p _ N t _ N s _ N g _ N
出力
答え（Yes または No）を 1 行で出力せよ。
入力例 1
8 1 2 0 3 2 1 3 3 1 2 0 4 4 1 2 2 1 2 0 5 6 1 5 5 5 1 140 1
出力例 1
Yes
はじめ、木は以下のようになっています。
高橋くんは、頂点 1 から 2,3,2,1,6,7,6,1,4,5,8 の順に移動することで、すべての敵を倒すことができます。 このとき、高橋くんがいる頂点と高橋くんの強さは以下の図のように変化します（図では、すでに訪れたことのある頂点への移動は省略しています）。
例えば、頂点 1 から 4,5,8 の順に移動すると、頂点 8 に訪れた時点での強さが s _ 8=140 より小さいので高橋くんは敗北してしまい、すべての敵を倒すことができません。
入力例 2
12 1 1 166 619 1 1 17 592 2 1 222 983 2 1 729 338 5 1 747 62 3 1 452 815 3 2 0 1 4 2 0 40 4 1 306 520 6 1 317 591 1 1 507 946
出力例 2
No
入力例 3
12 1 1 1 791 2 2 0 410 2 1 724 790 2 1 828 599 5 2 0 13 3 1 550 803 1 1 802 506 5 1 261 587 6 1 663 329 8 1 11 955 9 1 148 917
出力例 3
Yes
入力例 4
12 1 2 0 1000000000 2 2 0 1000000000 3 2 0 1000000000 4 2 0 1000000000 5 2 0 1000000000 6 2 0 1000000000 7 2 0 1000000000 8 2 0 1000000000 9 2 0 1000000000 10 2 0 1000000000 11 1 1 1
出力例 4
Yes
Score : 550 points
Problem Statement
There is a tree with N vertices. The 1-st vertex is the root, and the parent of the i-th vertex (2\leq i\leq N) is p _ i\ (1\leq p _ i\lt i).
Each non-root vertex has an enemy or a medicine on it. Takahashi wants to defeat all the enemies. Initially, his strength is 1, and he is at vertex 1. For i=2,\ldots,N, the information of the i-th vertex is represented by a triple of integers (t _ i,s _ i,g _ i) as follows.
- If t _ i=1, there is an enemy at the i-th vertex. When Takahashi visits this vertex for the first time, if his strength is less than s _ i, Takahashi is defeated by the enemy and loses, after which he cannot move to other vertices. Otherwise, he defeats the enemy, and his strength increases by g _ i.
- If t _ i=2, there is a medicine at the i-th vertex. When Takahashi visits this vertex for the first time, he takes the medicine, and his strength is multiplied by g _ i. (For a vertex with a medicine, s _ i=0.)
There are at most 10 vertices with a medicine.
Takahashi can repeatedly move to an adjacent vertex. Determine if he can defeat all the enemies.
Constraints
- 2\leq N\leq 500
- 1\leq p _ i\lt i\ (2\leq i\leq N)
- t _ i\in\lbrace1,2\rbrace\ (2\leq i\leq N)
- t _ i=1\implies1\leq s _ i\leq 10 ^ 9\ (2\leq i\leq N)
- t _ i=2\implies s _ i=0\ (2\leq i\leq N)
- 1\leq g _ i\leq 10 ^ 9\ (2\leq i\leq N)
- There are at most 10 vertices with t _ i=2.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N p _ 2 t _ 2 s _ 2 g _ 2 p _ 3 t _ 3 s _ 3 g _ 3 \vdots p _ N t _ N s _ N g _ N
Output
Print the answer (Yes or No) in one line.
Sample Input 1
8 1 2 0 3 2 1 3 3 1 2 0 4 4 1 2 2 1 2 0 5 6 1 5 5 5 1 140 1
Sample Output 1
Yes
Initially, the tree looks like this:
Takahashi can defeat all the enemies by moving from vertex 1 to 2,3,2,1,6,7,6,1,4,5,8 in this order. Here, his position and strength change as shown in the following figure (movements to vertices that have already been visited are omitted).
On the other hand, if he moves from vertex 1 to 4,5,8 in this order, for example, his strength when visiting vertex 8 will be less than s _ 8=140, so he will lose without defeating all the enemies.
Sample Input 2
12 1 1 166 619 1 1 17 592 2 1 222 983 2 1 729 338 5 1 747 62 3 1 452 815 3 2 0 1 4 2 0 40 4 1 306 520 6 1 317 591 1 1 507 946
Sample Output 2
No
Sample Input 3
12 1 1 1 791 2 2 0 410 2 1 724 790 2 1 828 599 5 2 0 13 3 1 550 803 1 1 802 506 5 1 261 587 6 1 663 329 8 1 11 955 9 1 148 917
Sample Output 3
Yes
Sample Input 4
12 1 2 0 1000000000 2 2 0 1000000000 3 2 0 1000000000 4 2 0 1000000000 5 2 0 1000000000 6 2 0 1000000000 7 2 0 1000000000 8 2 0 1000000000 9 2 0 1000000000 10 2 0 1000000000 11 1 1 1
Sample Output 4
Yes