A - リレー競技 (Relay)

実行時間制限: 1 sec / メモリ制限: 512 MiB

Score: 100 points

Problem Statement

There are N members in the track club of JOI High School, numbered from 1 to N. For the member i (1 \le i \le N), the time of the 100 m sprint is A_{i} msec, and the ability of controlling the baton is B_{i}.

The track club will participate in a national contest for the 300 m relay. Three members will run in the 300 m relay. Each member will run for 100 m. A runner will pass the baton to the next runner. Precisely, if the first runner is the member i (1 \le i \le N), the second runner is the member j (1 \le j \le N), and the third runner is the member k (1 \le k \le N), then the three members will run the relay in the following steps.

  1. The member i runs for 100 m with a baton. It takes A_{i} msec.
  2. The member i gives a baton to the member j. It takes \max(B_{i}, B_{j}) msec.
  3. The member j runs for 100 m with a baton. It takes A_{j} msec.
  4. The member j gives a baton to the member k. It takes \max(B_{j}, B_{k}) msec.
  5. The member k runs for 100 m with a baton. It takes A_{k} msec.

Therefore, the record for the 300 m relay is A_{i} + \max(B_{i}, B_{j}) + A_{j} + \max(B_{j}, B_{k}) + A_{k} msec. Here \max(x, y) is the largest value of x and y. Since you are the coach of the track club, you want to choose three distinct members for the relay and decide the order of the runners so that the record becomes minimum.

Write a program which, given information of the N members of the track club, calculates the minimum possible record of the 300 m relay.

Input

Read the following data from the standard input. Given values are all integers.

N
A_{1} B_{1}
A_{2} B_{2}
\vdots
A_{N} B_{N}

Output

Write one line to the standard output. The output should contain an integer which is the minimum possible record of the 300 m relay counted by msec.

Constraints

  • 3 \le N \le 200\,000.
  • 1 \le A_{i} \le 100\,000\,000 (= 10^{8}) (1 \le i \le N).
  • 1 \le B_{i} \le 100\,000\,000 (= 10^{8}) (1 \le i \le N).

Subtasks

  1. (25 points) N \le 100.
  2. (33 points) N \le 3\,000.
  3. (10 points) A_{1} = A_{2} = \cdots = A_{N}.
  4. (32 points) No additional constraints.

Sample Input 1

4
1070 90
1080 70
1050 60
1020 100

Sample Output 1

3320

If the first runner is the member 4, the second runner is the member 3, and the third runner is the member 2, then the time for the steps 1, 2, 3, 4, 5 of the relay will be 1020, 100, 1050, 70, 1080 msec, respectively. Thus, the record for the 300 m relay will be 1020 + 100 + 1050 + 70 + 1080 = 3320 msec. Since it is the minimum possible record, output 3320.

This sample input satisfies the constraints of Subtasks 1, 2, 4.

Sample Input 2

5
1000 28
1000 14
1000 21
1000 20
1000 14

Sample Output 2

3034

If the first runner is the member 2, the second runner is the member 5, and the third runner is the member 4, then the time for the steps 1, 2, 3, 4, 5 of the relay will be 1000, 14, 1000, 20, 1000 msec, respectively. Thus, the record for the 300 m relay will be 1000 + 14 + 1000 + 20 + 1000 = 3034 msec. Since it is the minimum possible record, output 3034.

This sample input satisfies the constraints of all the subtasks.

Sample Input 3

9
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3
2 3

Sample Output 3

13

If the first runner is the member 1, the second runner is the member 2, and the third runner is the member 9, then the time for the steps 1, 2, 3, 4, 5 of the relay will be 3, 1, 4, 3, 2 msec, respectively. Thus, the record for the 300 m relay will be 3 + 1 + 4 + 3 + 2 = 13 msec. Since it is the minimum possible record, output 13.

This sample input satisfies the constraints of Subtasks 1, 2, 4.

配点 : 100 点

問題文

JOI 高校の陸上部には N 人の部員がおり,1 から N までの番号が付けられている.部員 i (1 \leqq i \leqq N) の 100\:\textrm{m} 走のタイムは A_{i} ミリ秒であり,バトンパスの速さは B_{i} である.

さて,この陸上部は 300\:\textrm{m} リレーの全国大会に出場することになった.300\:\textrm{m} リレーは,3 人の走者がバトンを渡しながら 100\:\textrm{m} ずつ走る競技である.具体的には,第 1 走者が部員 i (1 \leqq i \leqq N),第 2 走者が部員 j (1 \leqq j \leqq N),第 3 走者が部員 k (1 \leqq k \leqq N) であるとき,以下の手順で行われる.

  1. 部員 i がバトンを持って 100\:\textrm{m} 走る.これには A_{i} ミリ秒かかる.
  2. 部員 i から部員 j にバトンを渡す.これには \max(B_{i}, B_{j}) ミリ秒かかる.
  3. 部員 j がバトンを持って 100\:\textrm{m} 走る.これには A_{j} ミリ秒かかる.
  4. 部員 j から部員 k にバトンを渡す.これには \max(B_{j}, B_{k}) ミリ秒かかる.
  5. 部員 k がバトンを持って 100\:\textrm{m} 走る.これには A_{k} ミリ秒かかる.

すなわち,300\:\textrm{m} リレーの記録は A_{i} +\max(B_{i}, B_{j})+A_{j} +\max(B_{j}, B_{k})+A_{k} ミリ秒となる.ここで,\max(x, y) は x と y のうち小さくない方の数とする.あなたは陸上部の顧問であるため,この記録ができるだけ短くなるように 3 人の異なる部員を選び,その走順を決めなければならない.

陸上部の N 人の部員の情報が与えられたとき,300\:\textrm{m} リレーの記録として考えられる最小値を求めるプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.

N
A_{1} B_{1}
A_{2} B_{2}
\vdots
A_{N} B_{N}

出力

標準出力に,300\:\textrm{m} リレーの記録として考えられる最小値をミリ秒単位で表す整数を 1 行で出力せよ.

制約

  • 3 \leqq N \leqq 200\,000.
  • 1 \leqq A_{i} \leqq 100\,000\,000 (= 10^{8}) (1 \leqq i \leqq N).
  • 1 \leqq B_{i} \leqq 100\,000\,000 (= 10^{8}) (1 \leqq i \leqq N).

小課題

  1. (25 点) N \leqq 100.
  2. (33 点) N \leqq 3\,000.
  3. (10 点) A_{1} = A_{2} = \cdots = A_{N}.
  4. (32 点) 追加の制約はない.

入力例 1

4
1070 90
1080 70
1050 60
1020 100

出力例 1

3320

第 1 走者に部員 4,第 2 走者に部員 3,第 3 走者に部員 2 を選ぶと,手順 1, 2, 3, 4, 5 にはそれぞれ 1020, 100, 1050, 70, 1080 ミリ秒かかるため,300\:\textrm{m} リレーの記録は 1020 + 100 + 1050 + 70 + 1080 = 3320 ミリ秒となる.これより記録を短くすることはできないため,3320 を出力する.

この入力例は小課題 1, 2, 4 の制約を満たす.

入力例 2

5
1000 28
1000 14
1000 21
1000 20
1000 14

出力例 2

3034

第 1 走者に部員 2,第 2 走者に部員 5,第 3 走者に部員 4 を選ぶと,手順 1, 2, 3, 4, 5 にはそれぞれ 1000, 14, 1000, 20, 1000 ミリ秒かかるため,300\:\textrm{m} リレーの記録は 1000 + 14 + 1000 + 20 + 1000 = 3034 ミリ秒となる.これより記録を短くすることはできないため,3034 を出力する.

この入力例はすべての小課題の制約を満たす.

入力例 3

9
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3
2 3

出力例 3

13

第 1 走者に部員 1,第 2 走者に部員 2,第 3 走者に部員 9 を選ぶと,手順 1, 2, 3, 4, 5 にはそれぞれ 3, 1, 4, 3, 2 ミリ秒かかるため,300\:\textrm{m} リレーの記録は 3 + 1 + 4 + 3 + 2 = 13 ミリ秒となる.これより記録を短くすることはできないため,13 を出力する.

この入力例は小課題 1, 2, 4 の制約を満たす.


出典

JOIG 2021/2022 春合宿 Contest Day1 問題1
B - JOIG ツアー (JOIG Tour)

実行時間制限: 2 sec / メモリ制限: 512 MiB

Score: 100 points

Problem Statement

Do you know Just Odd Ink Way? It is a national road of length 10^{100} in Republic of EGOI from the east end to the west end. It is famous because there are several painting on the road painted by “Just Odd Ink.” In the following, we abbreviate it, and call it JOI Way.

There are several painting of various sizes on JOI Way. Characters are written on some of them.

Rie is a tour guide working on JOI Way. She plans to guide the participants of JOIG Spring Training Camp. In order to cheer the participants, she plans to choose the paintings on which ‘J’, ‘O’, ‘I’, ‘G’ are written, and visit them in this order. There are N candidates of paintings. The i-th painting (1 \le i \le N) is located at the place on JOI Way at a distance of A_{i} from the west end. In this painting, the character C_{i} is written.

Rie has Q plans. In the j-th plan (1 \le j \le Q), she will travel as follows.

  1. Rie starts a tour from the place on JOI Way at a distance of S_{j} from the west end.
  2. She chooses a painting on which ‘J’ is written, and moves to its location.
  3. She chooses a painting on which ‘O’ is written, and moves to its location.
  4. She chooses a painting on which ‘I’ is written, and moves to its location.
  5. She chooses a painting on which ‘G’ is written, and moves to its location.
  6. She moves to the place on JOI Way at a distance of T_{j} from the west end, and finishes the tour.

During the tour, it is not allowed to go outside JOI Way.

Under the above conditions, Rie wants to minimize the total travel distance for each plan.

Write a program which, given information on the paintings on JOI Way and Rie’s plans, calculates the minimum possible value of the total travel distance for each plan.

Input

Read the following data from the standard input.

N
A_{1} C_{1}
A_{2} C_{2}
\vdots
A_{N} C_{N}
Q
S_1 T_{1}
S_2 T_{2}
\vdots
S_{Q} T_{Q}

Output

Write Q lines to the standard output. The j-th line (1 \le j \le Q) of the output should contain the minimum possible value of the total travel distance for the j-th plan.

Constraints

  • 4 \le N \le 100\,000.
  • 1 \le A_{i} \le 1\,000\,000\,000\,000\,000 (= 10^{15}) (1 \le i \le N).
  • A_{i} < A_{i+1} (1 \le i \le N - 1).
  • C_{i} (1 \le i \le N) is either ‘J’,‘O’,‘I’,or ‘G’.
  • C_{i} is equal to ‘J’ for at least one i (1 \le i \le N).
  • C_{i} is equal to ‘O’ for at least one i (1 \le i \le N).
  • C_{i} is equal to ‘I’ for at least one i (1 \le i \le N).
  • C_{i} is equal to ‘G’ for at least one i (1 \le i \le N).
  • 1 \le Q \le 100\,000.
  • 1 \le S_{j} \le 1\,000\,000\,000\,000\,000 (= 10^{15}) (1 \le j \le Q).
  • 1 \le T_{j} \le 1\,000\,000\,000\,000\,000 (= 10^{15}) (1 \le j \le Q).
  • (S_{j}, T_{j}) \ne (S_{k}, T_{k}) (1 \le j < k \le Q).
  • N, Q are integers.
  • A_{i} is an integer (1 \le i \le N).
  • S_{j}, T_{j} are integers (1 \le j \le Q).

Subtasks

  1. (4 points) N \le 80, Q \le 10.
  2. (10 points) N \le 500, Q \le 10.
  3. (6 points) N \le 3\,000, Q \le 100.
  4. (25 points) N \le 5\,000, Q \le 1\,000.
  5. (12 points) C_{i} is equal to ‘O’ for a unique i (1 \le i \le N), C_{j} is equal to ‘I’ for a unique j (1 \le j \le N), and C_{k} is equal to ‘G’ for a unique k (1 \le k \le N).
  6. (8 points) C_{i} is equal to ‘O’ for a unique i (1 \le i \le N), and C_{j} is equal to ‘I’ for a unique j (1 \le j \le N).
  7. (20 points) C_{i} is equal to ‘O’ for a unique i (1 \le i \le N).
  8. (15 points) No additional constraints.

Sample Input 1

7
1 J
2 O
3 G
4 I
5 O
8 G
10 J
2
3 2
7 5

Sample Output 1

7
12

In the first plan, Rie starts a tour from the place on JOI Way at a distance of 3 from the west end, and finishes the tour from the place on JOI Way at a distance of 2 from the west end. For example, if she travels in the following way, the total travel distance becomes 7.

  1. She starts a tour from the place on JOI Way at a distance of 3 from the west end.
  2. She moves to the west for a distance of 2. She arrives at the place on JOI Way at a distance of 1 from the west end. She visits a painting of ‘J’.
  3. She moves to the east for a distance of 1. She arrives at the place on JOI Way at a distance of 2 from the west end. She visits a painting of ‘O’.
  4. She moves to the east for a distance of 2. She arrives at the place on JOI Way at a distance of 4 from the west end. She visits a painting of ‘I’.
  5. She moves to the west for a distance of 1. She arrives at the place on JOI Way at a distance of 3 from the west end. She visits a painting of ‘G’.
  6. She moves to the west for a distance of 1. She arrives at the place on JOI Way at a distance of 2 from the west end, and finishes the tour.

Since 7 is the minimum possible value of the total travel distance, output 7 in the first line.

In the second plan, she starts a tour from the place on JOI Way at a distance of 7 from the west end, and finishes the tour from the place on JOI Way at a distance of 5 from the west end. For example, if she travels in the following way, the total travel distance becomes 12.

  1. She starts a tour from the place on JOI Way at a distance of 7 from the west end.
  2. She moves to the east for a distance of 3. She arrives at the place on JOI Way at a distance of 10 from the west end. She visits a painting of ‘J’.
  3. She moves to the west for a distance of 5. She arrives at the place on JOI Way at a distance of 5 from the west end. She visits a painting of ‘O’.
  4. She moves to the west for a distance of 1. She arrives at the place on JOI Way at a distance of 4 from the west end. She visits a painting of ‘I’.
  5. She moves to the west for a distance of 1. She arrives at the place on JOI Way at a distance of 3 from the west end. She visits a painting of ‘G’.
  6. She moves to the east for a distance of 2. She arrives at the place on JOI Way at a distance of 5 from the west end, and finishes the tour.

Since 12 is the minimum possible value of the total travel distance, output 12 in the second line.

This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 8.

Sample Input 2

10
5 J
7 O
10 J
11 G
12 J
13 I
17 J
18 J
19 J
20 J
4
4 9
15 14
6 20
7 20

Sample Output 2

13
19
20
21

This sample input satisfies the constraints of all the subtasks.

Sample Input 3

10
1 G
2 J
3 G
4 O
7 G
9 J
10 G
14 I
17 G
19 G
7
11 6
6 3
17 19
1 18
17 17
20 1
20 10

Sample Output 3

25
27
28
17
26
39
30

This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 6, 7, 8.

Sample Input 4

10
3 J
5 G
6 I
7 I
8 J
9 I
10 O
14 G
16 I
19 J
6
4 4
20 3
18 5
15 4
20 11
10 8

Sample Output 4

12
17
15
15
19
12

This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 7, 8.

Sample Input 5

12
179948747891578 I
263779425244614 I
320153642407146 G
383698990675423 J
478483318441339 J
505589213620811 G
507468309040564 O
530441288489671 J
730036011088087 O
896127332008998 I
899298512463927 O
915990785839829 J
10
744829561026263 366031656398270
700496830781726 684771674298690
314138534887378 222241904398827
695615197615084 632164325876673
418419052313523 409258287819812
932490604948180 62799105708059
738126150487131 45378717857226
320047965627255 918203067583346
859632377126681 967370566306944
115848334010451 834089404672067

Sample Output 5

583302366935305
805077987955000
591304613119987
757352272699625
478217003098189
869691499240121
805495866954969
1085532869547991
928541333618299
1205618838253516

This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 8.

配点 : 100 点

問題文

あなたは Just Odd Ink 街道を知っているだろうか?この街道は EGOI 国を東西に横断する長さ 10^{100} の街道であり,「ただ奇妙なインク (just odd ink)」によって描かれたたくさんのアートで有名である.ここでは略して JOI 街道と呼ぶ.

さて,JOI 街道には大小様々なアートが描かれているが,そのうちいくつかは文字が描かれているように見える.

JOI 街道のツアーガイドである理恵さんは,JOIG 春合宿の参加者を案内することになった.JOIG 春合宿の参加者を喜ばせたい理恵さんは,JOI 街道に描かれているアートのうち,‘J’, ‘O’, ‘I’, ‘G’ と読めるアートをこの順に訪れるツアーの計画を考えている.訪れる候補となるアートは N 個あり,i 番目 (1 \leqq i \leqq N) のアートは JOI 街道の西端から距離 A_{i} の地点にあり,このアートは C_{i} と読める.

理恵さんは Q 個の計画を考えている.j 番目 (1 \leqq j \leqq Q) の計画におけるツアーでは,以下の順に移動を行う.

  1. JOI 街道の西端から距離 S_{j} の地点からツアーを開始する.
  2. ‘J’ と読めるアートがある地点を 1 つ選び,その地点に移動する.
  3. ‘O’ と読めるアートがある地点を 1 つ選び,その地点に移動する.
  4. ‘I’ と読めるアートがある地点を 1 つ選び,その地点に移動する.
  5. ‘G’ と読めるアートがある地点を 1 つ選び,その地点に移動する.
  6. JOI 街道の西端から距離 T_{j} の地点に移動し,ツアーを終了する.

ただし,ツアーの経路は JOI 街道を外れないものとする.

理恵さんはこの条件のもと,それぞれの計画についてなるべくツアーの総移動距離を短くしたい.

JOI 街道のアートの情報と理恵さんの計画の情報が与えられたとき,それぞれの計画について,ツアーの総移動距離の最小値を求めるプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる.

N
A_{1} C_{1}
A_{2} C_{2}
\vdots
A_{N} C_{N}
Q
S_1 T_{1}
S_2 T_{2}
\vdots
S_{Q} T_{Q}

出力

標準出力に Q 行で出力せよ.j 行目 (1 \leqq j \leqq Q) には,理恵さんの j 番目の計画におけるツアーの総移動距離の最小値を出力せよ.

制約

  • 4 \leqq N \leqq 100\,000.
  • 1 \leqq A_{i} \leqq 1\,000\,000\,000\,000\,000 (= 10^{15}) (1 \leqq i \leqq N).
  • A_{i} < A_{i+1} (1 \leqq i \leqq N - 1).
  • C_{i} (1 \leqq i \leqq N) は ‘J’,‘O’,‘I’,‘G’ のいずれかである.
  • C_{i} が ‘J’ であるような i (1 \leqq i \leqq N) は 1 つ以上存在する.
  • C_{i} が ‘O’ であるような i (1 \leqq i \leqq N) は 1 つ以上存在する.
  • C_{i} が ‘I’ であるような i (1 \leqq i \leqq N) は 1 つ以上存在する.
  • C_{i} が ‘G’ であるような i (1 \leqq i \leqq N) は 1 つ以上存在する.
  • 1 \leqq Q \leqq 100\,000.
  • 1 \leqq S_{j} \leqq 1\,000\,000\,000\,000\,000 (= 10^{15}) (1 \leqq j \leqq Q).
  • 1 \leqq T_{j} \leqq 1\,000\,000\,000\,000\,000 (= 10^{15}) (1 \leqq j \leqq Q).
  • (S_{j}, T_{j}) \ne (S_{k}, T_{k}) (1 \leqq j < k \leqq Q).
  • N, Q は整数である.
  • A_{i} は整数である (1 \leqq i \leqq N).
  • S_{j}, T_{j} は整数である (1 \leqq j \leqq Q).

小課題

  1. (4 点) N \leqq 80,Q \leqq 10.
  2. (10 点) N \leqq 500,Q \leqq 10.
  3. (6 点) N \leqq 3\,000,Q \leqq 100.
  4. (25 点) N \leqq 5\,000,Q \leqq 1\,000.
  5. (12 点) C_{i} が ‘O’ であるような i (1 \leqq i \leqq N),C_{j} が ‘I’ であるような j (1 \leqq j \leqq N),C_{k} が ‘G’ であるような k (1 \leqq k \leqq N) はそれぞれただ 1 つ存在する.
  6. (8 点) C_{i} が ‘O’ であるような i (1 \leqq i \leqq N) ,C_{j} が ‘I’ であるような j (1 \leqq j \leqq N) はそれぞれただ 1 つ存在する.
  7. (20 点) C_{i} が ‘O’ であるような i (1 \leqq i \leqq N) はただ 1 つ存在する.
  8. (15 点) 追加の制約はない.

入力例 1

7
1 J
2 O
3 G
4 I
5 O
8 G
10 J
2
3 2
7 5

出力例 1

7
12

1 番目の計画は,JOI 街道の西端から距離 3 の地点からツアーを開始し,西端から距離 2 の地点でツアーを終了するというものである.例えば,以下のように移動することで,ツアーの総移動距離を 7 とすることができる.

  1. JOI 街道の西端から距離 3 の地点からツアーを開始する.
  2. 西に距離 2 だけ移動し,JOI 街道の西端から距離 1 の地点にある ‘J’ と読めるアートを訪れる.
  3. 東に距離 1 だけ移動し,JOI 街道の西端から距離 2 の地点にある ‘O’ と読めるアートを訪れる.
  4. 東に距離 2 だけ移動し,JOI 街道の西端から距離 4 の地点にある ‘I’ と読めるアートを訪れる.
  5. 西に距離 1 だけ移動し,JOI 街道の西端から距離 3 の地点にある ‘G’ と読めるアートを訪れる.
  6. 西に距離 1 だけ移動し,JOI 街道の西端から距離 2 の地点でツアーを終了する.

ツアーの総移動距離を 7 未満にすることはできないため,7 を 1 行目に出力する.

2 番目の計画は,JOI 街道の西端から距離 7 の地点からツアーを開始し,西端から距離 5 の地点でツアーを終了するというものである.例えば,以下のように移動することで,ツアーの総移動距離を 12 とすることができる.

  1. JOI 街道の西端から距離 7 の地点からツアーを開始する.
  2. 東に距離 3 だけ移動し,JOI 街道の西端から距離 10 の地点にある ‘J’ と読めるアートを訪れる.
  3. 西に距離 5 だけ移動し,JOI 街道の西端から距離 5 の地点にある ‘O’ と読めるアートを訪れる.
  4. 西に距離 1 だけ移動し,JOI 街道の西端から距離 4 の地点にある ‘I’ と読めるアートを訪れる.
  5. 西に距離 1 だけ移動し,JOI 街道の西端から距離 3 の地点にある ‘G’ と読めるアートを訪れる.
  6. 東に距離 2 だけ移動し,JOI 街道の西端から距離 5 の地点でツアーを終了する.

ツアーの総移動距離を 12 未満にすることはできないため,12 を 2 行目に出力する.

この入力例は小課題 1, 2, 3, 4, 8 の制約を満たす.

入力例 2

10
5 J
7 O
10 J
11 G
12 J
13 I
17 J
18 J
19 J
20 J
4
4 9
15 14
6 20
7 20

出力例 2

13
19
20
21

この入力例はすべての小課題の制約を満たす.

入力例 3

10
1 G
2 J
3 G
4 O
7 G
9 J
10 G
14 I
17 G
19 G
7
11 6
6 3
17 19
1 18
17 17
20 1
20 10

出力例 3

25
27
28
17
26
39
30

この入力例は小課題 1, 2, 3, 4, 6, 7, 8 の制約を満たす.

入力例 4

10
3 J
5 G
6 I
7 I
8 J
9 I
10 O
14 G
16 I
19 J
6
4 4
20 3
18 5
15 4
20 11
10 8

出力例 4

12
17
15
15
19
12

この入力例は小課題 1, 2, 3, 4, 7, 8 の制約を満たす.

入力例 5

12
179948747891578 I
263779425244614 I
320153642407146 G
383698990675423 J
478483318441339 J
505589213620811 G
507468309040564 O
530441288489671 J
730036011088087 O
896127332008998 I
899298512463927 O
915990785839829 J
10
744829561026263 366031656398270
700496830781726 684771674298690
314138534887378 222241904398827
695615197615084 632164325876673
418419052313523 409258287819812
932490604948180 62799105708059
738126150487131 45378717857226
320047965627255 918203067583346
859632377126681 967370566306944
115848334010451 834089404672067

出力例 5

583302366935305
805077987955000
591304613119987
757352272699625
478217003098189
869691499240121
805495866954969
1085532869547991
928541333618299
1205618838253516

この入力例は小課題 1, 2, 3, 4, 8 の制約を満たす.


出典

JOIG 2021/2022 春合宿 Contest Day1 問題2
C - チーム戦 (Team Contest)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

Score: 100 points

Problem Statement

There are N beavers in JOI University. All of them are working on competitive programming. Each beaver has three abilities: consideration skill, implementation skill, and luck. If the value of an ability is large, it means the level of the ability is high. For each i (1 \le i \le N), the consideration skill of the beaver i is X_{i}, the implementation skill of the beaver i is Y_{i}, and the luck of the beaver i is Z_{i}.

This year, the beavers of JOI University will attend a programming contest for teams. In this contest, the participants solve programming tasks, and each team consists of three beavers. Bitaro is a coach of JOI University. Since teamwork is very important, Bitaro decided to choose three beavers among the N beavers and make a team so that the following condition is satisfied.

  • Condition Every member in the team has an advantage. This means every member has an ability whose value is strictly larger than the values of the same ability of the other two members.

Among possible teams satisfying the above condition, Bitaro wants to choose a team whose total ability is as large as possible. Here, the total ability of a team is defined as the sum of the maximum value of the consideration skill of the members of the team, the maximum value of the implementation skill of the members of the team, and the maximum value of the luck of the members of the team.

Write a program which, given information of the abilities of each beaver, determines whether it is possible to make a team satisfying the above condition, and, if it is possible to make a team, calculate the maximum possible value of the total ability of a team.

Input

Read the following data from the standard input. Given values are all integers.

N
X_{1} Y_{1} Z_{1}
X_{2} Y_{2} Z_{2}
\vdots
X_{N} Y_{N} Z_{N}

Output

Write one line to the standard output. The output should contain the maximum possible value of the total ability of a team. If it is impossible to make a team satisfying the condition, output -1.

Constraints

  • 3 \le N \le 150\,000.
  • 1 \le X_{i} \le 100\,000\,000 (= 10^{8}) (1 \le i \le N).
  • 1 \le Y_{i} \le 100\,000\,000 (= 10^{8}) (1 \le i \le N).
  • 1 \le Z_{i} \le 100\,000\,000 (= 10^{8}) (1 \le i \le N).

Subtasks

  1. (8 points) N \le 300.
  2. (29 points) N \le 4\,000.
  3. (9 points) X_{i} \le 5,Y_{i} \le 5,Z_{i} \le 5 (1 \le i \le N).
  4. (9 points) X_{i} \le 20,Y_{i} \le 20,Z_{i} \le 20 (1 \le i \le N).
  5. (9 points) X_{i} \le 300,Y_{i} \le 300,Z_{i} \le 300 (1 \le i \le N).
  6. (9 points) X_{i} \le 4\,000,Y_{i} \le 4\,000,Z_{i} \le 4\,000 (1 \le i \le N).
  7. (27 points) No additional constraints.

Sample Input 1

5
3 1 4
2 3 1
1 5 5
4 4 2
5 2 3

Sample Output 1

13

If we make a team consisting of the beaver 1, the beaver 4, and the beaver 5, the condition of the task is satisfied.

  • The value of the luck of the beaver 1 is strictly larger than the values of the luck of the other two members.
  • The value of the implementation skill of the beaver 4 is strictly larger than the values of the implementation skill of the other two members.
  • The value of the consideration skill of the beaver 5 is strictly larger than the values of the consideration skill of the other two members.

Then, the maximum values of the consideration skill, implementation skill, luck of the members of the team are 5, 4, 4, respectively. The total ability of the team is 13. Since it is impossible to make a team whose total ability is larger than or equal to 14, output 13.

Note that if we make a team consisting of the beaver 1, the beaver 3, and the beaver 5, the total ability becomes 15. However, since the beaver 1 does not have an ability whose value is strictly larger than the values of the same ability of the other two members, the condition of the task is not satisfied.

This sample input satisfies the constraints of all the subtasks.

Sample Input 2

8
1 1 1
1 1 5
1 5 1
5 1 1
1 5 5
5 1 5
5 5 1
5 5 5

Sample Output 2

15

If we make a team consisting of the beaver 2, the beaver 3, and the beaver 4, the total ability of the team is 15. Since it is impossible to make a team whose total ability is larger than or equal to 16, output 15. This sample input satisfies the constraints of all the subtasks.

Sample Input 3

4
1 2 3
1 2 3
1 2 3
1 2 3

Sample Output 3

-1

Since it is impossible to make a team satisfying the condition of the task, output -1.

This sample input satisfies the constraints of all the subtasks.

配点 : 100 点

問題文

JOI 大学には N 匹のビーバーが在籍しており,その全員が競技プログラミングに取り組んでいる.各ビーバーには考察力・実装力・運という 3 種類の能力を表す数値が定められており,それらの値が大きいほど能力が高いことを示す.i 匹目 (1 \leqq i \leqq N) のビーバーの考察力は X_{i},実装力は Y_{i},運は Z_{i} である.

今年,JOI 大学のビーバーたちはチーム対抗のプログラミングコンテストに出場することになった.このコンテストでは,3 匹でチームを組んで競技プログラミングの問題に取り組む.ここで,JOI 大学のコーチであるビ太郎は,チームワークを意識して,以下の条件を満たすように N 匹の中から 3 匹を選んでチームを組むことにした.

  • 条件 どのチームメンバーにも長所がある.すなわち,どのチームメンバーも,他の 2 匹より値が真に大きいような能力を持っている.

ビ太郎は,この条件を満たすなかで可能な限り総合力が高いチームを組みたいと思っている.ここで,チームの総合力は,3 匹のチームメンバーの考察力の最大値,実装力の最大値,運の最大値の 3 つの値の合計として計算される.

各ビーバーの能力の情報が与えられたとき,条件を満たすチームを作ることが可能か判定し,もし可能ならばチームの総合力として考えられる最大の値を求めるプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.

N
X_{1} Y_{1} Z_{1}
X_{2} Y_{2} Z_{2}
\vdots
X_{N} Y_{N} Z_{N}

出力

標準出力に,チームの総合力として考えられる最大の値を 1 行で出力せよ.ただし,問題文中の条件を満たすようにチームを組むことが不可能な場合は,-1 を出力せよ.

制約

  • 3 \leqq N \leqq 150\,000.
  • 1 \leqq X_{i} \leqq 100\,000\,000 (= 10^{8}) (1 \leqq i \leqq N).
  • 1 \leqq Y_{i} \leqq 100\,000\,000 (= 10^{8}) (1 \leqq i \leqq N).
  • 1 \leqq Z_{i} \leqq 100\,000\,000 (= 10^{8}) (1 \leqq i \leqq N).

小課題

  1. (8 点) N \leqq 300.
  2. (29 点) N \leqq 4\,000.
  3. (9 点) X_{i} \leqq 5,Y_{i} \leqq 5,Z_{i} \leqq 5 (1 \leqq i \leqq N).
  4. (9 点) X_{i} \leqq 20,Y_{i} \leqq 20,Z_{i} \leqq 20 (1 \leqq i \leqq N).
  5. (9 点) X_{i} \leqq 300,Y_{i} \leqq 300,Z_{i} \leqq 300 (1 \leqq i \leqq N).
  6. (9 点) X_{i} \leqq 4\,000,Y_{i} \leqq 4\,000,Z_{i} \leqq 4\,000 (1 \leqq i \leqq N).
  7. (27 点) 追加の制約はない.

入力例 1

5
3 1 4
2 3 1
1 5 5
4 4 2
5 2 3

出力例 1

13

1, 4, 5 匹目のビーバーでチームを組むと,以下のように問題文中の条件を満たす.

  • 1 匹目のビーバーは他の 2 匹よりも運の値が大きい.
  • 4 匹目のビーバーは他の 2 匹よりも実装力の値が大きい.
  • 5 匹目のビーバーは他の 2 匹よりも考察力の値が大きい.

このとき,チームメンバーの考察力・実装力・運の最大値はそれぞれ 5, 4, 4 であるため,チームの総合力は 13 である.総合力を 14 以上にするチームの組み方は存在しないので,13 を出力する.

なお,例えば 1, 3, 5 匹目のビーバーでチームを組むと,チームの総合力は 15 となるものの,1 匹目のビーバーには他のメンバーよりも値が真に大きい能力がないため,問題文中の条件を満たさないことに注意せよ.

この入力例はすべての小課題の制約を満たす.

入力例 2

8
1 1 1
1 1 5
1 5 1
5 1 1
1 5 5
5 1 5
5 5 1
5 5 5

出力例 2

15

2, 3, 4 匹目のビーバーでチームを組むと,問題文中の条件を満たし,チームの総合力は 15 となる.総合力を 16 以上にするチームの組み方は存在しないので,15 を出力する.

この入力例はすべての小課題の制約を満たす.

入力例 3

4
1 2 3
1 2 3
1 2 3
1 2 3

出力例 3

-1

問題文中の条件を満たすようにチームを組むことはできない.よって -1 を出力する.

この入力例はすべての小課題の制約を満たす.


出典

JOIG 2021/2022 春合宿 Contest Day1 問題3
D - コピー & ペースト 3 (Copy and Paste 3)

実行時間制限: 3 sec / メモリ制限: 2048 MiB

Score: 100 points

Problem Statement

JOI, Ltd. is a company known for their “just odd inventions.” Recently, JOI, Ltd. developed a text editor called “Just Odd Editor.”

Using this text editor, we can input a string of characters by performing the following operations several times. Let X be the string displayed on the screen of the text editor. Let Y be the string saved in the clipboard. In the beginning, both of X and Y are the empty string.

  • Operation A : We add one character in the end of the string. Namely, we choose a character c, and update X to be X + c.
  • Operation B : We select all the characters and cut them. Namely, we update Y to be X. After that, we set X to be the empty string.
  • Operation C : We paste the string from the clipboard at the end of the string. Namely, we update X to be X + Y.

Here, for characters or strings x, y, the string x + y means the string obtained by connecting x with y in this order. Performing an operation takes time. If we perform the operation A, B, C once, it takes A, B,C unit time, respectively.

You installed Just Odd Editor. You want to input a string S of length N as soon as possible. Performing operations, you want to make the string on the display be S as soon as possible.

Write a program which, given the length N, the string S, and the amount of unit time needed to perform an operation, calculates the least amount of time needed to input the string S.

Input

Read the following data from the standard input.

N
S
A
B
C

Output

Write one line to the standard output. The output should contain the least amount of time needed to input the string S.

Constraints

  • 1 \le N \le 2\,500.
  • S is a string of length N. Each character of S is a lower-case alphabet (’a’ - ’z’).
  • 1 \le A \le 1\,000\,000\,000 (= 10^{9}).
  • 1 \le B \le 1\,000\,000\,000 (= 10^{9}).
  • 1 \le C \le 1\,000\,000\,000 (= 10^{9}).
  • N, A, B,C are integers.

Subtasks

  1. (7 points) N = 3.
  2. (18 points) Every character of S is ’a’.
  3. (18 points) N \le 30.
  4. (11 points) N \le 200.
  5. (22 points) N \le 1\,000.
  6. (24 points) No additional constraints.

Sample Input 1

11
mississippi
10
5
2

Sample Output 1

88

By performing the following operations, we can input mississippi by 88 unit time. Since it is the least amount of time needed to input mississippi, output 88.

Order Operation Explanation X Y Time Total Time
- - - "" "" - 0
1 Operation A Add a character in end "s" "" 10 10
2 Operation B Select all & Cut "" "s" 5 15
3 Operation C Paste at end "s" "s" 2 17
4 Operation C Paste at end "ss" "s" 2 19
5 Operation A Add a character in end "ssi" "s" 10 29
6 Operation B Select all & Cut "" "ssi" 5 34
7 Operation A Add a character in end "m" "ssi" 10 44
8 Operation A Add a character in end "mi" "ssi" 10 54
9 Operation C Paste at end "missi" "ssi" 2 56
10 Operation C Paste at end "mississi" "ssi" 2 58
11 Operation A Add a character in end "mississip" "ssi" 10 68
12 Operation A Add a character in end "mississipp" "ssi" 10 78
13 Operation A Add a character in end "mississippi" "ssi" 10 88

This sample input satisfies the constraints of Subtasks 3, 4, 5, 6.

Sample Input 2

16
aaaaaaaaaaaaaaaa
1
1
1

Sample Output 2

9

By performing the following operations, we can input aaaaaaaaaaaaaaaa by 9 unit time. Since it is the least amount of time needed to input aaaaaaaaaaaaaaaa, output 9.

Order Operation Explanation X Y Time Total Time
- - - "" "" - 0
1 Operation A Add a character in end "a" "" 1 1
2 Operation A Add a character in end "aa" "" 1 2
3 Operation A Add a character in end "aaa" "" 1 3
4 Operation A Add a character in end "aaaa" "" 1 4
5 Operation B Select all & Cut "" "aaaa" 1 5
6 Operation C Paste at end "aaaa" "aaaa" 1 6
7 Operation C Paste at end "aaaaaaaa" "aaaa" 1 7
8 Operation C Paste at end "aaaaaaaaaaaa" "aaaa" 1 8
9 Operation C Paste at end "aaaaaaaaaaaaaaaa" "aaaa" 1 9

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6.

Sample Input 3

18
aababbbababbbaabbb
1000000000
100000
10000000

Sample Output 3

8060200000

This sample input satisfies the constraints of Subtasks 3, 4, 5, 6.

配点 : 100 点

問題文

ただ奇妙な発明で知られる JOI 社は,最近 Just Odd Editor というテキストエディタを開発した.

このテキストエディタでは,以下の操作のいずれかを繰り返すことで,文字列を入力することができる.説明の都合上,現在テキストエディタの画面に表示されている文字列を X,クリップボードに保存されている文字列を Y とする.最初の時点では,X と Y はどちらも空文字列である.

  • 操作 A:末尾に 1 文字入力する.すなわち,ある文字 c を決めて,X を X + c に更新する.
  • 操作 B:全選択して切り取りする.すなわち,Y を X に更新した後,X を空文字列に更新する.
  • 操作 C:末尾に貼り付けする.すなわち,X を X + Y に更新する.

ただし,文字または文字列 x, y に対し,x + y は「x, y をこの順で連結した文字列」を表すものとする.また,各操作には一定の時間がかかり,具体的には操作 A, B, C を 1 回行うのにそれぞれ A, B,C 単位時間かかる.

あなたは Just Odd Editor をインストールしたので,できるだけ早く長さ N の文字列 S を入力したいと思っている.すなわち,操作手順を工夫することで,できるだけ短い時間で画面に表示されている文字列を S に一致させたい.

文字列の長さ N,文字列 S および各操作に必要な時間が与えられるので,文字列 S を入力するのに必要な時間の最小値を求めるプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる.

N
S
A
B
C

出力

標準出力に,文字列 S を入力するのに必要な時間の最小値を 1 行で出力せよ.

制約

  • 1 \leqq N \leqq 2\,500.
  • S は英小文字 (’a’ - ’z’) からなる長さ N の文字列である.
  • 1 \leqq A \leqq 1\,000\,000\,000 (= 10^{9}).
  • 1 \leqq B \leqq 1\,000\,000\,000 (= 10^{9}).
  • 1 \leqq C \leqq 1\,000\,000\,000 (= 10^{9}).
  • N, A, B,C は整数である.

小課題

  1. (7 点) N = 3.
  2. (18 点) S のすべての文字は ’a’ である.
  3. (18 点) N \leqq 30.
  4. (11 点) N \leqq 200.
  5. (22 点) N \leqq 1\,000.
  6. (24 点) 追加の制約はない.

入力例 1

11
mississippi
10
5
2

出力例 1

88

以下の表のように操作すると,88 単位時間で mississippi を入力できる.これより少ない時間で mississippi を入力することはできないので,88 を出力する.

順番 種類 操作内容 X Y 時間 累計時間
- - - "" "" - 0
1 操作 A 末尾に 1 文字入力 "s" "" 10 10
2 操作 B 全選択して切り取り "" "s" 5 15
3 操作 C 末尾に貼り付け "s" "s" 2 17
4 操作 C 末尾に貼り付け "ss" "s" 2 19
5 操作 A 末尾に 1 文字入力 "ssi" "s" 10 29
6 操作 B 全選択して切り取り "" "ssi" 5 34
7 操作 A 末尾に 1 文字入力 "m" "ssi" 10 44
8 操作 A 末尾に 1 文字入力 "mi" "ssi" 10 54
9 操作 C 末尾に貼り付け "missi" "ssi" 2 56
10 操作 C 末尾に貼り付け "mississi" "ssi" 2 58
11 操作 A 末尾に 1 文字入力 "mississip" "ssi" 10 68
12 操作 A 末尾に 1 文字入力 "mississipp" "ssi" 10 78
13 操作 A 末尾に 1 文字入力 "mississippi" "ssi" 10 88

この入力例は小課題 3, 4, 5, 6 の制約を満たす.

入力例 2

16
aaaaaaaaaaaaaaaa
1
1
1

出力例 2

9

以下の表のように操作すると,9 単位時間で aaaaaaaaaaaaaaaa を入力できる.これより少ない時間で aaaaaaaaaaaaaaaa を入力することはできないので,9 を出力する.

順番 種類 操作内容 X Y 時間 累計時間
- - - "" "" - 0
1 操作 A 末尾に 1 文字入力 "a" "" 1 1
2 操作 A 末尾に 1 文字入力 "aa" "" 1 2
3 操作 A 末尾に 1 文字入力 "aaa" "" 1 3
4 操作 A 末尾に 1 文字入力 "aaaa" "" 1 4
5 操作 B 全選択して切り取り "" "aaaa" 1 5
6 操作 C 末尾に貼り付け "aaaa" "aaaa" 1 6
7 操作 C 末尾に貼り付け "aaaaaaaa" "aaaa" 1 7
8 操作 C 末尾に貼り付け "aaaaaaaaaaaa" "aaaa" 1 8
9 操作 C 末尾に貼り付け "aaaaaaaaaaaaaaaa" "aaaa" 1 9

この入力例は小課題 2, 3, 4, 5, 6 の制約を満たす.

入力例 3

18
aababbbababbbaabbb
1000000000
100000
10000000

出力例 3

8060200000

この入力例は小課題 3, 4, 5, 6 の制約を満たす.


出典

JOIG 2021/2022 春合宿 Contest Day1 問題4
E - メロンの出荷 (Melons)

実行時間制限: 1.5 sec / メモリ制限: 512 MiB

Score: 100 points

Problem Statement

In EGOI Farm, the employees are receiving and shipping melons. This morning, N melons are received. The melons are numbered from 1 to N. The weight of melon i (1 \le i \le N) is A_{i}.

Rie is working at EGOI Farm. Her job is packing melons into boxes. Now, an integer x (1 \le x \le N) is determined in EGOI Farm. After that, she will receive the melons x, x + 1, \ldots, N, in this order. She will pack them into boxes by repeating the following process.

  • Rie will take an empty box. She will repeat putting the melons into the box. However, if the total weight of the melons in the box will exceeds L after putting the next melon into the box, she will not put it into the box. Then, she will ship the box. (In this case, she will put the next melon into a new box.) After putting the melon N into a box, she will ship the box, and her job will be finished.

Rie wants to prepare for her job for all possible values of x. Write a program which, given information of the melons and the maximum possible weight L of a box, calculates the number of boxes shipped by her and the total weight of the melons in the last box for all possible values of x.

Input

Read the following data from the standard input. Given values are all integers.

N L
A_{1}
A_{2}
\vdots
A_{N}

Output

Write N lines to the standard output. The i-th line (1 \le i \le N) of output corresponds to the case x = i. This line should contain the number of shipped boxes and the total weight of the melons in the last box if x = i. These two values should be separated by a space.

Constraints

  • 1 \le N \le 200\,000.
  • 1 \le L \le 1\,000\,000\,000 (= 10^{9}).
  • 1 \le A_{i} \le L (1 \le i \le N).

Subtasks

  1. (6 points) A_{1} = A_{2} = \cdots = A_{N}.
  2. (21 points) N \le 1\,000.
  3. (29 points) For every x, the number of boxes shipped by Rie will be less than or equal to 10.
  4. (33 points) For every x, Rie will put at most 10 melons into a box.
  5. (11 points) No additional constraints.

Sample Input 1

7 100
20
80
50
40
20
80
10

Sample Output 1

4 10
4 10
3 10
2 90
2 10
1 90
1 10

For example, if x = 1, Rie will pack melons into boxes as follows.

  1. Rie puts the melon 1 into a box. The total weight of the box is 20.
  2. Rie puts the melon 2 into the same box. The total weight of the box is 100.
  3. If Rie puts the melon 3 into the same box, the total weight of the box will be 150. Therefore, Rie ships the current box, and puts the melon 3 into a new box. The total weight of the new box is 50.
  4. Rie puts the melon 4 into the box. The total weight of the box is 90.
  5. If Rie puts the melon 5 into the box, the total weight of the box will be 110. Therefore, Rie ships the current box, and puts the melon 5 into a new box. The total weight of the new box is 20.
  6. Rie puts the melon 6 into the box. The total weight of the box is 100.
  7. If Rie puts the melon 7 into the box, the total weight of the box will be 110. Therefore, Rie ships the current box, and puts the melon 7 into a new box. The total weight of the new box is 10.
  8. Finally, Rie ships the current box.

If x = 1, Rie ships 4 boxes, and the total weight of the melons in the last box is 10. Therefore, output 4 and 10 in this order. These two values should be separated by a space.

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5.

Sample Input 2

6 160
63
63
63
63
63
63

Sample Output 2

3 126
3 63
2 126
2 63
1 126
1 63

For example, if x = 1, Rie puts the melons 1, 2 into the first box, the melons 3, 4 into the second box, and the melons 5, 6 into the third box. Rie ships 3 boxes, and the total weight of the melons in the last box is 126. Therefore, output 3 and 126 in the first line in this order. These two values should be separated by a space.

This sample input satisfies the constraints of all the subtasks.

Sample Input 3

5 20
7
10
4
6
8

Sample Output 3

2 18
2 8
1 18
1 14
1 8

For example, if x = 2, Rie puts the melons 2, 3, 4 into the first box. Rie puts only the melon 5 into the second box. Rie ships 2 boxes, and the total weight of the melons in the last box is 8. Therefore, output 2 and 8 in the second line in this order. These two values should be separated by a space.

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5.

配点 : 100 点

問題文

EGOI 農場はメロンの入荷と出荷を行っており,今朝 N 個のメロンを入荷した.メロンには入荷した順に 1 から N までの番号が付けられており,メロン i (1 \leqq i \leqq N) の重さは A_{i} である.

EGOI 農場で働く理恵さんは,メロンの箱詰めを担当している.今から,EGOI 農場で整数 x (1 \leqq x \leqq N) が決定される.その後,理恵さんにはメロン x, x + 1, \ldots, N がこの順に渡され,以下を繰り返して箱詰めを行うことになっている.

  • 空の箱を用意し,その箱に渡されたメロンを入れ続ける.ただし,渡されたメロンを入れたらその箱に入っているメロンの重さの合計が L を超えてしまう場合は,そのメロンを入れずに箱を出荷する. (そのメロンは次の箱に入れることになる.)メロン N を箱に入れたら,その箱を出荷して理恵さんの作業は終了する.

理恵さんは x がどの値に決定されても大丈夫なように準備をしたいと思った.入荷するメロンの情報と箱の重量制限 L が与えられるので,すべての x の場合について,出荷する箱の個数と,最後に出荷する箱に入れるメロンの重さの合計を求めるプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.

N L
A_{1}
A_{2}
\vdots
A_{N}

出力

標準出力に N 行で出力せよ.i 行目 (1 \leqq i \leqq N) には,x = i の場合について,出荷する箱の個数と最後に出荷する箱に入れるメロンの重さの合計をこの順に空白区切りで出力せよ.

制約

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq L \leqq 1\,000\,000\,000 (= 10^{9}).
  • 1 \leqq A_{i} \leqq L (1 \leqq i \leqq N).

小課題

  1. (6 点) A_{1} = A_{2} = \cdots = A_{N}.
  2. (21 点) N \leqq 1\,000.
  3. (29 点) どの x に対しても,理恵さんが出荷する箱の数は 10 個以下になる.
  4. (33 点) どの x に対しても,理恵さんが 1 つの箱に入れるメロンの個数は 10 個以下になる.
  5. (11 点) 追加の制約はない.

入力例 1

7 100
20
80
50
40
20
80
10

出力例 1

4 10
4 10
3 10
2 90
2 10
1 90
1 10

例えば x = 1 の場合,理恵さんは以下のように箱詰めを行うことになる.

  1. メロン 1 を箱に入れる.箱のメロンの重さの合計は 20 となる.
  2. メロン 2 を箱に入れる.箱のメロンの重さの合計は 100 となる.
  3. もしメロン 3 を箱に入れたら,箱のメロンの重さの合計は 150 となってしまう.そのため,現在の箱を出荷し,メロン 3 は新しい箱に入れる.新しい箱のメロンの重さの合計は 50 となる.
  4. メロン 4 を箱に入れる.箱のメロンの重さの合計は 90 となる.
  5. もしメロン 5 を箱に入れたら,箱のメロンの重さの合計は 110 となってしまう.そのため,現在の箱を出荷し,メロン 5 は新しい箱に入れる.新しい箱のメロンの重さの合計は 20 となる.
  6. メロン 6 を箱に入れる.箱のメロンの重さの合計は 100 となる.
  7. もしメロン 7 を箱に入れたら,箱のメロンの重さの合計は 110 となってしまう.そのため,現在の箱を出荷し,メロン 7 は新しい箱に入れる.新しい箱のメロンの重さの合計は 10 となる.
  8. 最後に現在の箱を出荷する.

そのため,x = 1 の場合,出荷する箱の個数は 4 個であり,最後の箱に入れるメロンの重さの合計は 10 となる.したがって,1 行目には 4 と 10 をこの順に空白区切りで出力する.

この入力例は小課題 2, 3, 4, 5 の制約を満たす.

入力例 2

6 160
63
63
63
63
63
63

出力例 2

3 126
3 63
2 126
2 63
1 126
1 63

例えば x = 1 の場合,最初の箱にはメロン 1, 2 を入れ,次の箱にはメロン 3, 4 を入れ,その次の箱にはメロン 5, 6 を入れることになる.そのため,出荷する箱の個数は 3 個であり,最後に出荷する箱に入れるメロンの重さの合計は 126 となる.したがって,1 行目には 3 と 126 をこの順に空白区切りで出力する.

この入力例はすべての小課題の制約を満たす.

入力例 3

5 20
7
10
4
6
8

出力例 3

2 18
2 8
1 18
1 14
1 8

例えば x = 2 の場合,最初の箱にはメロン 2, 3, 4 を入れ,次の箱にはメロン 5 のみを入れることになる.そのため,出荷する箱の個数は 2 個であり,最後に出荷する箱に入れるメロンの重さの合計は 8 となる.したがって,2 行目には 2 と 8 をこの順に空白区切りで出力する.

この入力例は小課題 2, 3, 4, 5 の制約を満たす.


出典

JOIG 2021/2022 春合宿 Contest Day2 問題1
F - 空港 (Airport)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

Score: 100 points

Problem Statement

In EGOI Airport, there are N runways, numbered from 1 to N. In this airport, for an airplane, it takes K minutes to take off, and L minutes to land. During a takeoff or landing of an airplane, a runway is occupied by the airplane for a duration of K or L minutes.

JOI-kun is working at EGOI Airport. His job is to arrange the schedule of takeoffs and landings for a contiguous time slot of T minutes. The beginning of the time slot is time 0. The time when t minutes passed after the beginning of the time slot is time t. The end of the time slot is time T.

In the time slot, M airplanes will arrive at EGOI Airport. They are numbered from 1 to M. The (1 \le i \le M) will start landing at time A_{i}. But the runway used by airplane i is not yet fixed. It will be fixed by JOI-kun. The schedule for the takeoffs is not fixed at all. JOI-kun will decide the number of airplanes which will take off, the time of a takeoff of each airplane, and the runway used by it.

In summary, the schedule has to obey the following rules.

  • It is not allowed that more than one airplane take off or land at the same time in the same runway. However, it is allowed that an airplane starts taking off or landing, just after another airplane finished taking off or landing in the same runway.
  • All takeoffs and landings should be finished in the time slot of T minutes. Namely, it is not allowed for an airplane to start taking off or landing before time 0. It is not allowed for an airplane to finish taking off or landing after time T.

JOI-kun wants to arrange the schedule so that it obeys the above rules, and the number of airplanes which will take off is maximized.

Write a program which, given the number of runways, the number of airplanes which will land, the length of the time slot, the time required for a takeoff, the time required for a landing, and the time when each airplane will start landing, calculates the maximum possible number of airplanes which will take off from EGOI Airport. If it is not possible to arrange the schedule so that it obeys the rules, your program should report it.

Input

Read the following data from the standard input. Given values are all integers.

N M T K L
A_{1} A_{2} \cdots A_{M}

Output

Write one line to the standard output. The output should contain the maximum possible number of airplanes which will take off from EGOI Airport. If it is not possible to arrange the schedule so that it obeys the rules, output -1.

Constraints

  • 1 \le N \le 100\,000.
  • 1 \le M \le 100\,000.
  • 1 \le T \le 1\,000\,000\,000 (= 10^{9}).
  • 1 \le K \le T.
  • 1 \le L \le T.
  • 0 \le A_{i} \le T - L (1 \le i \le M).

Subtasks

  1. (7 points) N = 1.
  2. (12 points) N = 2, M \le 20.
  3. (17 points) N = 2, K = 2, L = 2.
  4. (28 points) N = 2.
  5. (11 points) N \le 100.
  6. (25 points) No additional constraints.

Sample Input 1

2 4 15 3 2
4 1 5 12

Sample Output 1

5

For example, if JOI-kun arranges the schedule as follows, 5 airplanes will take off.

  1. At time 0, an airplane will start taking off in the runway 1.
  2. At time 1, the airplane 2 will start landing in the runway 2.
  3. At time 4, the airplane 1 will start landing in the runway 2.
  4. At time 5, the airplane 3 will start landing in the runway 1.
  5. At time 6, an airplane will start taking off in the runway 2.
  6. At time 7, an airplane will start taking off in the runway 1.
  7. At time 9, an airplane will start taking off in the runway 2.
  8. At time 10, an airplane will start taking off in the runway 1.
  9. At time 12, the airplane 4 will start landing in the runway 2.

It is not possible to arrange the schedule so that it obeys the rules and more than 5 airplanes will take off. Therefore, output 5.

This sample input satisfies the constraints of Subtasks 2, 4, 5, 6.

Sample Input 2

2 6 23 3 6
9 13 1 16 4 8

Sample Output 2

-1

It is not possible to arrange the schedule so that it obeys the rules. Therefore, output -1.

This sample input satisfies the constraints of Subtasks 2, 4, 5, 6.

Sample Input 3

1 5 20 2 1
2 8 11 15 5

Sample Output 3

7

This sample input satisfies the constraints of Subtasks 1, 5, 6.

Sample Input 4

2 6 13 2 2
7 0 1 10 7 4

Sample Output 4

5

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6.

Sample Input 5

4 4 14 2 3
5 6 3 9

Sample Output 5

21

This sample input satisfies the constraints of Subtasks 5, 6.

Sample Input 6

8 15 100 4 7
93 10 74 46 37 64 68 5 38 67 6 48 76 36 21

Sample Output 6

170

This sample input satisfies the constraints of Subtasks 5, 6.

配点 : 100 点

問題文

EGOI 空港には N 本の滑走路があり,1 から N までの番号が付けられている.この空港では,飛行機の離陸開始から終了まで K 分かかり,着陸開始から終了まで L 分かかる.この連続する K 分または L 分の間,飛行機は 1 つの滑走路を占有することになる.

EGOI 空港で働いている JOI 君は,ある T 分間の期間における離着陸のスケジュールを立てる仕事を任された.期間の開始時刻を時刻 0 とし,時刻 0 から t 分経過した時刻を時刻 t と表す.期間が終わるのは時刻 T である.

期間中に着陸するのは,1 から M まで番号付けられた M 機の飛行機である.飛行機 i (1 \leqq i \leqq M) は時刻 A_{i} に着陸を開始することが決まっているが,使用する滑走路はこれから JOI 君が決めることになっている.また,離陸のスケジュールは全く決められていないため,離陸する飛行機の数,各飛行機の離陸開始時刻と使用する滑走路はすべて JOI 君が決めることになる.

以上を踏まえて,スケジュールは以下のルールをすべて守るように作らなければならない.

  • 1 つの滑走路で複数の飛行機が同時に離着陸を行っている状態にしてはならない.ただし,ある飛行機が離着陸を終えると同時に,同じ滑走路で別の飛行機が離着陸を開始することは許される.
  • すべての離着陸は T 分間の期間中に行われなければならない.すなわち,時刻 0 より前に離着陸を開始したり,時刻 T より後に離着陸を終了したりしてはならない.

JOI 君はこのルールをすべて守ったうえで,できるだけ多くの飛行機が離陸できるようなスケジュールを立てたいと思った.

滑走路の数,着陸する飛行機の数,期間の長さ,離陸にかかる時間,着陸にかかる時間,各飛行機が着陸を開始する時刻が与えられたとき,期間中に EGOI 空港を離陸できる飛行機の数の最大値を求めるプログラムを作成せよ.ただし,ルールをすべて守ったスケジュールを作ることが不可能である場合は,そのことを報告せよ.

入力

入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.

N M T K L
A_{1} A_{2} \cdots A_{M}

出力

標準出力に,期間中に EGOI 空港を離陸できる飛行機の数の最大値を 1 行で出力せよ.ただし,ルールをすべて守ったスケジュールを作ることが不可能である場合は,-1 を出力せよ.

制約

  • 1 \leqq N \leqq 100\,000.
  • 1 \leqq M \leqq 100\,000.
  • 1 \leqq T \leqq 1\,000\,000\,000 (= 10^{9}).
  • 1 \leqq K \leqq T.
  • 1 \leqq L \leqq T.
  • 0 \leqq A_{i} \leqq T - L (1 \leqq i \leqq M).

小課題

  1. (7 点) N = 1.
  2. (12 点) N = 2,M \leqq 20.
  3. (17 点) N = 2,K = 2,L = 2.
  4. (28 点) N = 2.
  5. (11 点) N \leqq 100.
  6. (25 点) 追加の制約はない.

入力例 1

2 4 15 3 2
4 1 5 12

出力例 1

5

例えば,以下のようなスケジュールを立てることで,5 機の飛行機が離陸することができる.

  1. 時刻 0 に,滑走路 1 で飛行機の離陸を開始する.
  2. 時刻 1 に,滑走路 2 で飛行機 2 の着陸を開始する.
  3. 時刻 4 に,滑走路 2 で飛行機 1 の着陸を開始する.
  4. 時刻 5 に,滑走路 1 で飛行機 3 の着陸を開始する.
  5. 時刻 6 に,滑走路 2 で飛行機の離陸を開始する.
  6. 時刻 7 に,滑走路 1 で飛行機の離陸を開始する.
  7. 時刻 9 に,滑走路 2 で飛行機の離陸を開始する.
  8. 時刻 10 に,滑走路 1 で飛行機の離陸を開始する.
  9. 時刻 12 に,滑走路 2 で飛行機 4 の着陸を開始する.

どのようなスケジュールを立てても,ルールをすべて守ったうえで 6 機以上が離陸することはできないため,5 を出力する.

この入出力例は小課題 2, 4, 5, 6 の制約を満たす.

入力例 2

2 6 23 3 6
9 13 1 16 4 8

出力例 2

-1

ルールをすべて守ったスケジュールを作ることが不可能であるため,-1 を出力する.

この入出力例は小課題 2, 4, 5, 6 の制約を満たす.

入力例 3

1 5 20 2 1
2 8 11 15 5

出力例 3

7

この入出力例は小課題 1, 5, 6 の制約を満たす.

入力例 4

2 6 13 2 2
7 0 1 10 7 4

出力例 4

5

この入出力例は小課題 2, 3, 4, 5, 6 の制約を満たす.

入力例 5

4 4 14 2 3
5 6 3 9

出力例 5

21

この入出力例は小課題 5, 6 の制約を満たす.

入力例 6

8 15 100 4 7
93 10 74 46 37 64 68 5 38 67 6 48 76 36 21

出力例 6

170

この入出力例は小課題 5, 6 の制約を満たす.


出典

JOIG 2021/2022 春合宿 Contest Day2 問題2
G - 一流の団子職人 (Super Dango Maker)

実行時間制限: 10 sec / メモリ制限: 1024 MiB

Submission on AtCoder

Distributed files

Using C++

Include dango3.h and implement all functions in a single source file.

Using standard input and output

First, N, M are given in this order on one line.

Query

Consider an array A of length N \times M, with A[i] = 1 if dango i is selected and A[i] = 0 otherwise. Print the character Q, immediately followed by A as packed binary bytes, then a newline. Pack eight elements in each byte, starting with the least significant bit. Do not print a string of ASCII 0 and 1 characters.

For example, if A = (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0), print Q 4 followed by a newline. The two bytes after Q have values 32 and 52, which appear as a space and the character 4. Do not add a separator between Q and the binary data.

The return value of Query is then given on one line.

Answer

Define the selection array A in the same way. Print the character A, immediately followed by A in the same binary format, then a newline. The integer 0 is then given on one line.

Other instructions

  • If the output format is incorrect or a Wrong Answer condition is met, the input you receive is -1. Terminate your program immediately in this case.
  • After M calls to Answer, print the character F.
  • Flush after every output.

Score: 100 points

Problem Statement

JOI-kun is a professional confectioner making dangos (Japanese dumplings). In JOI-kun’s shop, the colors of dangos are specified. There are N colors of dangos, numbered from 1 to N.

A beautiful dango stick is a famous item in JOI-kun’s shop. A beautiful dango stick is made of N dangos of different colors skewered with a stick.

For each of the N colors, JOI-kun has M dangos of that color. Therefore, JOI-kun has N \times M dangos in total. These dangos are numbered from 1 to N \times M. Using these dangos and M sticks, JOI-kun wants to make M beautiful skewered dango sticks.

To avoid a mistake about the colors of the dangos, JOI-kun will use a dango checker. If JOI-kun inputs the indices of some dangos, the dango checker answers the maximum number of beautiful dango sticks he can make using the dangos in the input and sufficiently many sticks.

Using the dango checker several times, JOI-kun wants to divide the N \times M dangos into M groups. Every group should consist of N dangos, and contain a dango of each color.

JOI-kun wants to divide the N \times M dangos into M groups using the dango checker at most 50 000 times.

Write a program which, given information of the dangos, implements JOI-kun’s strategy to divide the dangos into groups using the the dango checker at most 50 000 times.

Implementation Details

You need to submit one file. The name of the file is dango3.cpp. It should implement the following function. The program should include dango3.h using the preprocessing directive #include.

  • void Solve(int N, int M) This function is called once for each test case.
    • The parameter N is the number of colors of dangos N.
    • The parameter M is the number of beautiful dango sticks M JOI-kun wants to make.

Your program may call the following functions.

  • int Query(const std::vector<int> &x) Using this function, your program asks questions to the dango checker.
    • The parameter x is the list of the indices of the dangos sent to the dango checker.
    • The return value is the maximum number of beautiful dango sticks JOI-kun can make using the dangos specified by the parameter x and sufficiently many sticks.
    • Each element of the parameter x should be between 1 and N \times M, inclusive. If this condition is not satisfied, your program is judged as Wrong Answer [1].
    • The elements of the parameter x should be different from each other. If this condition is not satisfied, your program is judged as Wrong Answer [2].
    • It is not allowed to call the function Query more than 50 000 times. If the function Query is called more than 50 000 times, your program is judged as Wrong Answer [3].
  • void Answer(const std::vector<int> &a) Using this function, your program answers groups of dangos to make beautiful dango sticks.
    • The parameter a is the list of the indices of dangos for a beautiful dango stick.
    • The length of the parameter a should be N. If this condition is not satisfied, your program is judged as Wrong Answer [4].
    • Every element of the parameter a should be between 1 and N \times M, inclusive. If this condition is not satisfied, your program is judged as Wrong Answer [5].
    • Throughout the process, no value should appear in a more than once. If this condition is not satisfied, your program is judged as Wrong Answer [6].
    • If it is impossible to make a beautiful dango stick using the dangos specified by a and a stick, your program is judged as Wrong Answer [7].
    • The function Answer should be called exactly M times. If the number of function calls to Answer is different from M when the function Solve terminates, your program is judged as Wrong Answer [8].

Important Notices

  • Your program can implement other functions for internal use, or use global variables.
  • Your program must not use the standard input and the standard output. Your program must not communicate with other files by any methods. However, your program may output debugging information to the standard error.

Compilation and Test Run

You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program.

The sample grader is the file grader.cpp. In order to test your program, put grader.cpp, dango3.cpp, dango3.h in the same directory, and run the following command to compile your programs.

g++ -std=gnu++17 -O2 -o grader grader.cpp dango3.cpp

When the compilation succeeds, the executable file grader is generated.

Note that the actual grader is different from the sample grader. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output.

Input for the Sample Grader

The sample grader reads the following data from the standard input.

N M
C_{1} C_{2} \cdots C_{N\times M}

Here C_{i} (1 \le i \le N \times M) is the color of the dango i. It is an integer between 1 and N, inclusive.

Output of the Sample Grader

The sample grader outputs the following information to the standard output (quotes for clarity).

  • If your program is judged as correct, it writes the number of times of the function calls to Query as “Accepted: 2022”.
  • If your program is judged as any one of Wrong Answer, the sample grader writes its type as “Wrong Answer [4]”.

If your program satisfies the conditions of several types of Wrong Answer, the sample grader reports only one of them.

Constraints

All input data satisfy the following constraints. For the values of C, see Input for the Sample Grader.

  • 1 \le C_{i} \le N (1 \le i \le N \times M).
  • For each j (1 \le j \le N), there are exactly M indices i (1 \le i \le N \times M) satisfying C_{i} = j.
  • N, M are integers.
  • C_{i} (1 \le i \le N \times M) is an integer.

Subtasks

  1. (5 points) N = 4, M = 4.
  2. (12 points) N = 100, M = 10.
  3. (22 points) N = 200, M = 25.
  4. (61 points) N = 400, M = 25.

Sample Communication

Here is a sample input for the sample grader and corresponding function calls.

Sample Input 1

3 2
3 3 1 2 1 2

Sample Function Calls

Call Call Return Value
Solve(3, 2)
Query([]) 0
Query([4, 2, 1 ,3]) 1
Query([3, 4, 5]) 0
Query([2, 6, 5]) 1
Query([6, 5, 4, 3, 2, 1]) 2
Answer([1, 6, 5])
Answer([2, 3, 4])

Note that this sample input does not satisfy the constraints of any subtask.

Among the files which can be downloaded from the contest webpage, sample-02.txt satisfies the constraints of Subtask 1.

AtCoder での提出方法

配布ファイル

C++ を使用する場合

dango3.h をインクルードし,すべての関数を 1 つのファイル内で実装して提出してください.

標準入出力を使用する場合

はじめに,N, M がこの順に 1 行で与えられます.

Query

団子 i を選ぶとき A[i] = 1,選ばないとき A[i] = 0 とする長さ N \times M の配列 A を考えます.文字 Q を出力し,その後空白を空けずに A をバイナリで出力し,最後に改行してください.8 要素を 1 バイトにまとめ,下位ビットから順に詰めます.ASCII の 0 と 1 を並べた文字列ではありません.

例えば A = (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0) のとき,Q 4 を出力し,改行してください.この例では Q に続く 2 バイトの値が 32 と 52 なので,見た目は空白と文字 4 になります.Q とバイナリデータの間に区切りの空白は加えません.

その後,Query の戻り値が 1 行で与えられます.

Answer

同様に選択を表す配列 A を考えます.文字 A を出力し,その後空白を空けずに A を同じバイナリ形式で出力し,最後に改行してください.その後,0 が 1 行で与えられます.

その他

  • 出力形式が正しくない場合や不正解の条件に当てはまった場合,与えられる入力は -1 になります.この場合,ただちにプログラムを終了してください.
  • M 回の Answer の後,文字 F を出力してください.
  • 各出力の後には必ず flush をしてください.

配点 : 100 点

問題文

JOI 君は団子職人である.JOI 君の店で用いられる団子にはそれぞれ色が定まっており,色は N 種類ある.色には 1 から N までの番号が付けられている.

JOI 君の店の人気メニューはきれいな串団子である.きれいな串団子とは,色が相異なる合計 N 個の団子に 1 本の串を刺したものである.

JOI 君は色 1 から色 N までの団子をそれぞれ M 個ずつ,合計 N \times M 個の団子を用意している.これらの団子には 1 から N \times M までの番号が付けられている.JOI 君はこれらの団子と M 本の串からきれいな串団子を M 本作りたい.

団子の色を間違えてはならないため,JOI 君は団子チェッカーを用いることにした.団子チェッカーにいくつかの団子の番号を指定して質問すると,それらの団子と十分な量の串を用いて最大何本のきれいな串団子を作れるかを知ることができる.

JOI 君は団子チェッカーに何度か質問をすることで,M 本のきれいな串団子を作るために,N \times M 個ある団子を N 個ずつ M 組に分けたい.このとき,それぞれの組には色 1 から色 N までの団子が 1 つずつ含まれていなければならない.

JOI 君は団子チェッカーに 50\,000 回以下の質問を行うことで,団子を組分けしたい.

団子の情報が与えられたとき,団子チェッカーに 50\,000 回以下の質問を行うことで団子を組分けする JOI 君の戦略を実装したプログラムを作成せよ.

実装の詳細

あなたは 1 つのファイルを提出しなければならない.

あなたの提出するファイルは dango3.cpp という名前である.このファイルは以下の関数を実装していなければならない.そのプログラムは #include プリプロセッサ指令によって dango3.h を読み込むこと.

  • void Solve(int N, int M) この関数は各テストケースにおいて 1 回だけ呼び出される.
    • 引数 N は団子の色の種類の数 N である.
    • 引数 M は JOI 君が作りたいきれいな串団子の本数 M である.

あなたのプログラムは以下の関数を呼び出すことができる.

  • int Query(const std::vector<int> &x) この関数を用いて,団子チェッカーに質問を行う.
    • 引数 x は,団子チェッカーに質問する団子の番号のリストである.
    • 戻り値は,指定した団子と十分な量の串を用いて作れるきれいな串団子の本数の最大値である.
    • 引数 x の各要素は,1 以上 N \times M 以下でなければならない.これが満たされていない場合,不正解 [1] と判定される.
    • 引数 x の各要素はすべて異ならなければならない.これが満たされていない場合,不正解 [2] と判定される.
    • 関数 Query を 50\,000 回を超えて呼び出してはならない.50\,000 回を超えて呼び出した場合,不正解 [3] と判定される.
  • void Answer(const std::vector<int> &a) この関数を用いて,きれいな串団子を作るための団子の組を解答する.
    • 引数 a は, きれいな串団子を作るための団子の番号のリストである.
    • 引数 a の長さは,N でなければならない.これが満たされていない場合,不正解 [4] と判定される.
    • 引数 a の各要素は,1 以上 N \times M 以下でなければならない.これが満たされていない場合,不正解 [5] と判定される.
    • a の要素に同じ値を累計で 2 回以上指定してはならない.これが満たされていない場合,不正解 [6] と判定される.
    • a で指定された各団子と 1 本の串を用いてきれいな串団子を作ることができない場合,不正解 [7] と判定される.
    • 関数 Answer はちょうど M 回呼び出される必要がある.関数 Solve の実行の終了時に関数 Answer の呼び出し回数が M 回でなかった場合,不正解 [8] と判定される.

重要な注意

  • 内部での使用のために他の関数を実装したり,グローバル変数を宣言するのは自由である.
  • あなたの提出したプログラムは,標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.ただし,標準エラー出力にデバッグ情報等を出力することは許される.

コンパイル・実行の方法

作成したプログラムをテストするための,採点プログラムのサンプルが,コンテストサイトからダウンロードできるアーカイブの中に含まれている.このアーカイブには,提出しなければならないファイルのサンプルも含まれている.

採点プログラムのサンプルは 1 つのファイルからなる. そのファイルは grader.cpp である.作成したプログラムをテストするには,これらのファイル grader.cpp, dango3.cpp, dango3.h を同じディレクトリに置き,次のようにコマンドを実行する.

g++ -std=gnu++17 -O2 -o grader grader.cpp dango3.cpp

コンパイルが成功すれば,grader という実行ファイルが生成される.

実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること.採点プログラムのサンプルは単一のプロセスとして起動する.このプログラムは,標準入力から入力を読み込み,標準出力に結果を出力する.

採点プログラムのサンプルの入力

採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む.

N M
C_{1} C_{2} \cdots C_{N\times M}

C_{i} (1 \leqq i \leqq N \times M) は,団子 i の色を表す,1 以上 N 以下の整数である.

採点プログラムのサンプルの出力

採点プログラムのサンプルは標準出力へ以下の情報を出力する (引用符は実際には出力されない).

  • 正解の場合,関数 Query の呼び出し回数が “Accepted: 2022” のように出力される.
  • 不正解の場合,不正解の種類が “Wrong Answer [4]” のように出力される.

実行するプログラムが複数の不正解の条件を満たした場合,表示される不正解の種類はそれらのうち 1 つのみである.

制約

すべての入力データは以下の条件を満たす.C の意味については「採点プログラムのサンプルの入力」の項目を参照せよ.

  • 1 \leqq C_{i} \leqq N (1 \leqq i \leqq N \times M).
  • 各 j (1 \leqq j \leqq N) に対し,C_{i} = j となる i (1 \leqq i \leqq N \times M) がちょうど M 個存在する.
  • N, M は整数である.
  • C_{i} (1 \leqq i \leqq N \times M) は整数である.

小課題

  1. (5 点) N = 4,M = 4.
  2. (12 点) N = 100,M = 10.
  3. (22 点) N = 200,M = 25.
  4. (61 点) N = 400,M = 25.

やりとりの例

採点プログラムのサンプルが読み込む入力の例と,それに対応する関数の呼び出しの例を以下に示す.

入力例 1

3 2
3 3 1 2 1 2

関数の呼び出しの例

呼び出し 呼び出し 戻り値
Solve(3, 2)
Query([]) 0
Query([4, 2, 1 ,3]) 1
Query([3, 4, 5]) 0
Query([2, 6, 5]) 1
Query([6, 5, 4, 3, 2, 1]) 2
Answer([1, 6, 5])
Answer([2, 3, 4])

この入力例はどの小課題の制約も満たさないことに注意すること.

コンテストサイトからダウンロードできるファイルのうち,sample-02.txt は小課題 1 の制約を満たす.


出典

JOIG 2021/2022 春合宿 Contest Day2 問題3
H - 復興事業 (Reconstruction Project)

実行時間制限: 5 sec / メモリ制限: 1024 MiB

Score: 100 points

Problem Statement

JOI Town is an industrial area which had flourished some time ago. In order to transport products, many stations and railway tracks were constructed. Though it declined, there remain the stations and the railway tracks which are not used any more.

There are N stations in JOI Town, numbered from 1 to N. There remain M railway tracks. The i-th railway track (1 \le i \le M) connects the station A_{i} and the station B_{i} bidirectionally. The width of the i-th railway track is W_{i}. It is possible to travel from any station to any other station using railway tracks.

You are the mayor of JOI Town. You are planning to attract a railroad company using the remaining stations and railway tracks, and revive the JOI Town as the town of railway. Then, Q railroad companies applied for this revival project. However, the width of the railway track for trains varies for different companies. It turns out that they need to reconstruct the railway tracks so that the width of the railway tracks of JOI Town matches the width of the railway tracks for the trains of a company.

The width of the railway tracks for the trains of the railroad company j (1 \le j \le Q) is X_{j}. To attract the railroad company j, it is required that the following condition is satisfied.

  • Condition It is possible to travel from any station to any other station using railway tracks of width X_{j} only.

In order to satisfy the above condition, you can reconstruct the railway tracks as many times as needed.

  • Reconstruction You choose a railway track. Then you reconstruct the chosen track so that its width will be increased or decreased by 1. The cost is 1. However, if the width of a railway track is 1, it is impossible to decrease the width further.

In order to decide on the company to be attracted, you want to estimate the minimum cost to attract each railroad company.

White a program which, given information on the stations, the railway tracks, and the railroad companies, calculates the minimum cost to attract each railroad company.

Input

Read the following data from the standard input. Given values are all integers.

N M
A_{1} B_{1} W_{1}
A_{2} B_{2} W_{2}
\vdots
A_{M} B_{M} W_{M}
Q
X_{1}
X_{2}
\vdots
X_{Q}

Output

Write Q lines to the standard output. The j-th line (1 \le j \le Q) of output should contain the minimum cost to attract the railroad company j.

Constraints

  • 2 \le N \le 500.
  • N - 1 \le M \le 100\,000.
  • 1 \le Q \le 1\,000\,000.
  • 1 \le A_{i} < B_{i} \le N (1 \le i \le M).
  • 1 \le W_{i} \le 1\,000\,000\,000 (= 10^{9}) (1 \le i \le M).
  • (A_{i}, B_{i}, W_{i}) \ne (A_{j}, B_{j}, W_{j}) (1 \le i < j \le M).
  • It is possible to travel from any station to any other station using railway tracks.
  • 1 \le X_{j} \le 1\,000\,000\,000 (= 10^{9}) (1 \le j \le Q).
  • X_{j} < X_{j+1} (1 \le j \le Q - 1).

Subtasks

  1. (9 points) M \le 16, Q \le 10.
  2. (11 points) Q \le 10.
  3. (18 points) B_{i} = A_{i} + 1 (1 \le i \le M).
  4. (23 points) M \le 1\,000.
  5. (28 points) Q \le 20\,000.
  6. (11 points) No additional constraints.

Sample Input 1

5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
6
3
6
8
10
13
17

Sample Output 1

8
2
5
10
9
21

For example, to attract the railroad company 1, it will cost 8 if you reconstruct the railway tracks as follows.

  1. Decrease the width of the 6-th railway track by 4. The cost is 4.
  2. Decrease the width of the 9-th railway track by 3. The cost is 3.
  3. Increase the width of the 10-th railway track by 1. The cost is 1.

It is impossible to attract the railroad company 1 at cost less than 8. Therefore, output 8 in the first line.

This sample input satisfies the constraints of Subtasks 1, 2, 4, 5, 6.

Sample Input 2

3 4
1 2 1
1 2 4
2 3 2
2 3 4
4
1
2
3
4

Sample Output 2

1
1
2
0

This sample input satisfies the constraints of all the subtasks.

Sample Input 3

10 20
6 7 914727791
1 8 771674531
3 5 632918108
5 9 329296846
1 7 237501112
4 9 303328173
2 6 216298255
2 10 504024991
3 8 158236886
1 10 10176179
8 9 918271145
3 6 217165898
3 6 624543444
4 9 70147274
8 9 976983490
6 9 210108505
2 9 972711062
1 10 564567289
3 7 411395464
4 7 952470985
10
115721165
198969744
356664401
429802521
513343279
610443927
741016686
786597783
898772266
903568946

Sample Output 3

1121073688
761832468
1026806785
1316097872
1321500065
1445238392
1637513141
1621778548
1733953031
1738749711

This sample input satisfies the constraints of Subtasks 2, 4, 5, 6.

配点 : 100 点

問題文

JOI 町はかつて栄えた工業地域であり,物資の運搬のために数多くの駅や線路が建設された.現在は衰退してしまったが,使われなくなった駅や線路は今もなお残されたままである.

JOI 町には N 個の駅が残されており,1 から N までの番号が付けられている.また M 本の線路が残されており,i 本目 (1 \leqq i \leqq M) の線路は駅 A_{i} と駅 B_{i} を双方向に結び,そのレール幅は W_{i} である.どの駅からどの駅へもいくつかの線路を通って到達できる.

JOI 町の町長であるあなたは,この残された駅と線路を用いて鉄道会社を誘致し,JOI 町を鉄道の町として復興させることにした.するとこの復興事業に Q 社の鉄道会社が名乗りを挙げた.しかし鉄道会社ごとに,保有する列車に対応するレール幅が決まっているため,線路のレール幅を列車に合わせるための工事が必要であることが分かった.

j 番目 (1 \leqq j \leqq Q) の鉄道会社の列車に対応するレール幅は X_{j} である.j 番目の鉄道会社を誘致するには次の条件を満たす必要がある.

  • 条件 どの駅からどの駅へも,レール幅が X_{j} である線路のみを通って到達できる.

この条件を満たすようにするために,あなたは次の工事を好きなだけ行える.

  • 工事 線路を 1 つ選び,その線路のレール幅を 1 だけ増やすまたは減らす.これにはコストが 1 だけかかる.ただし,レール幅が 1 である線路のレール幅をさらに減らすことはできない.

あなたは誘致する鉄道会社を決めるために,各鉄道会社を誘致するのにそれぞれ最小でいくらコストがかかるのかを見積もりたい.

駅と線路,鉄道会社の情報が与えられたとき,各鉄道会社を誘致するためにかかるコストの最小値を求めるプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.

N M
A_{1} B_{1} W_{1}
A_{2} B_{2} W_{2}
\vdots
A_{M} B_{M} W_{M}
Q
X_{1}
X_{2}
\vdots
X_{Q}

出力

標準出力に Q 行で出力せよ.j 行目 (1 \leqq j \leqq Q) には j 番目の鉄道会社を誘致するためにかかるコストの最小値を出力せよ.

制約

  • 2 \leqq N \leqq 500.
  • N - 1 \leqq M \leqq 100\,000.
  • 1 \leqq Q \leqq 1\,000\,000.
  • 1 \leqq A_{i} < B_{i} \leqq N (1 \leqq i \leqq M).
  • 1 \leqq W_{i} \leqq 1\,000\,000\,000 (= 10^{9}) (1 \leqq i \leqq M).
  • (A_{i}, B_{i}, W_{i}) \ne (A_{j}, B_{j}, W_{j}) (1 \leqq i < j \leqq M)
  • どの駅からどの駅へもいくつかの線路を通って到達できる.
  • 1 \leqq X_{j} \leqq 1\,000\,000\,000 (= 10^{9}) (1 \leqq j \leqq Q).
  • X_{j} < X_{j+1} (1 \leqq j \leqq Q - 1).

小課題

  1. (9 点) M \leqq 16,Q \leqq 10.
  2. (11 点) Q \leqq 10.
  3. (18 点) B_{i} = A_{i} + 1 (1 \leqq i \leqq M).
  4. (23 点) M \leqq 1\,000.
  5. (28 点) Q \leqq 20\,000.
  6. (11 点) 追加の制約はない.

入力例 1

5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
6
3
6
8
10
13
17

出力例 1

8
2
5
10
9
21

例えば 1 番目の鉄道会社を誘致するとき,以下のように工事を行うとコストが 8 かかる.

  1. 6 本目の線路のレール幅を 4 だけ減らす.これにはコストが 4 だけかかる.
  2. 9 本目の線路のレール幅を 3 だけ減らす.これにはコストが 3 だけかかる.
  3. 10 本目の線路のレール幅を 1 だけ増やす.これにはコストが 1 だけかかる.

コスト 8 未満で 1 番目の鉄道会社を誘致することはできないので,1 行目には 8 を出力する.

この入力例は小課題 1, 2, 4, 5, 6 の制約を満たす.

入力例 2

3 4
1 2 1
1 2 4
2 3 2
2 3 4
4
1
2
3
4

出力例 2

1
1
2
0

この入力例はすべての小課題の制約を満たす.

入力例 3

10 20
6 7 914727791
1 8 771674531
3 5 632918108
5 9 329296846
1 7 237501112
4 9 303328173
2 6 216298255
2 10 504024991
3 8 158236886
1 10 10176179
8 9 918271145
3 6 217165898
3 6 624543444
4 9 70147274
8 9 976983490
6 9 210108505
2 9 972711062
1 10 564567289
3 7 411395464
4 7 952470985
10
115721165
198969744
356664401
429802521
513343279
610443927
741016686
786597783
898772266
903568946

出力例 3

1121073688
761832468
1026806785
1316097872
1321500065
1445238392
1637513141
1621778548
1733953031
1738749711

この入力例は小課題 2, 4, 5, 6 の制約を満たす.


出典

JOIG 2021/2022 春合宿 Contest Day2 問題4