JOI 2015 Final Camp - Ngày 4

Ông JOI, một đại gia sở hữu toàn bộ đường sắt của quốc gia IOI, đã qua đời. Các tuyến đường sắt sẽ được chia thừa kế theo di chúc của ông.

Quốc gia IOI có \(N\) thành phố và \(M\) tuyến đường sắt. Các thành phố được đánh số từ \(1\) đến \(N\), các tuyến đường sắt được đánh số từ \(1\) đến \(M\). Tuyến \(i\) nối hai chiều thành phố \(A_i\) và \(B_i\), đồng thời mang lại doanh thu \(C_i\) yên mỗi năm. Vì lượng hành khách và giá vé khác nhau, các giá trị \(C_1,\ldots,C_M\) đôi một khác nhau. Có thể có nhiều tuyến nối cùng một cặp thành phố.

Di chúc quy định cách chia thừa kế như sau:

• Các tuyến đường sắt được chia cho \(K\) người con, đánh số từ \(1\) đến \(K\) theo thứ tự từ lớn tuổi đến nhỏ tuổi.
• Mỗi người con thừa kế một số tuyến trong \(M\) tuyến, có thể là không tuyến nào.
• Đầu tiên, người con \(1\) chọn một số tuyến làm phần thừa kế. Sau đó người con \(2\) chọn trong các tuyến còn lại, rồi tiếp tục như vậy đến người con \(K\).
• Không ai được chọn một tuyến đã có người lớn tuổi hơn chọn.
• Khi chọn phần của mình, mỗi người phải bảo đảm các tuyến mình nhận không chứa chu trình. Nói cách khác, nếu có thể dùng mỗi tuyến trong một tập các tuyến phân biệt đúng một lần để xuất phát và quay lại cùng một thành phố, thì không người con nào được thừa kế toàn bộ tập đó.
• Các tuyến không ai nhận sẽ được hiến tặng cho quốc gia IOI.

Giống cha mình, mỗi người con đều tham lam và chọn phần thừa kế sao cho tổng doanh thu hằng năm lớn nhất có thể. Có thể chứng minh rằng đối với mỗi người, cách chọn đạt tổng doanh thu lớn nhất là duy nhất.

Yêu cầu

Hãy xác định người thừa kế của từng tuyến đường sắt.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên \(N,M,K\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(A_i,B_i,C_i\).

Dữ liệu ra

In ra \(M\) dòng. Dòng thứ \(i\) chứa số hiệu người con thừa kế tuyến \(i\); nếu tuyến đó được hiến tặng cho quốc gia IOI, in ra 0.

Ràng buộc

• \(2 \le N \le 1\,000\).
• \(1 \le M \le 300\,000\).
• \(1 \le K \le 10\,000\).
• \(1 \le A_i,B_i \le N\) và \(A_i \ne B_i\) với mọi \(1 \le i \le M\).
• \(1 \le C_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le M\).
• \(C_i \ne C_j\) với mọi \(1 \le i<j \le M\).

Phân nhóm

• Nhóm 1 (15 điểm): \(K \le 10\)
• Nhóm 2 (85 điểm): Không có ràng buộc bổ sung

Ví dụ

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

1
0
2
1
2

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

4
3
2
1
2
1

JOI-chan được chọn vào đội tuyển Nhật Bản dự thi Olympic Tin học Quốc tế. Để nâng cao kỹ năng xử lý thông tin của cô, chủ tịch K của Ủy ban Olympic Tin học Nhật Bản giao cho cô bài toán sau.

Chủ tịch K bí mật viết một chuỗi \(S\) vào sổ. Chuỗi chỉ gồm bốn ký tự <, >, [, ]. Ông đưa cho JOI-chan một tờ giấy ghi nội dung bài toán và độ dài của \(S\).

JOI-chan phải xác định \(S\) có phải một chuỗi tốt hay không. Chuỗi tốt được định nghĩa như sau:

• Chuỗi rỗng là chuỗi tốt.
• Nếu \(x\) là chuỗi tốt thì <x> là chuỗi tốt.
• Nếu \(x\) là chuỗi tốt thì [x] là chuỗi tốt.
• Nếu \(x,y\) là các chuỗi tốt thì chuỗi nối \(xy\) cũng là chuỗi tốt.
• Chỉ những chuỗi được tạo bởi các quy tắc trên mới là chuỗi tốt.

Ví dụ, <>[] và [<>]<> là chuỗi tốt; >< và [<]> không phải chuỗi tốt.

Mỗi ngày vào buổi trưa, JOI-chan được gọi cho chủ tịch K nhiều nhất một lần. Trong cuộc gọi, cô chỉ định một số nguyên \(I\) và được biết ký tự thứ \(I\) của \(S\).

JOI-chan không được ghi chép. Mỗi tối cô đi ngủ lúc 22 giờ và thức dậy lúc 6 giờ; qua giấc ngủ cô chỉ có thể ghi nhớ \(22\) bit thông tin. Chính xác hơn, trước khi ngủ cô có thể ghi nhớ một số nguyên từ \(0\) đến \(2^{22}-1\), và ngày hôm sau chỉ được dựa vào số đã nhớ. Cô luôn có thể xem độ dài \(S\) trên tờ giấy.

Thay vì ghi nhớ một số trước khi ngủ, JOI-chan có thể gửi email trả lời rằng \(S\) là hoặc không phải là chuỗi tốt; khi đó bài toán kết thúc. Nếu không gửi câu trả lời trong vòng \(15\,000\) ngày kể từ khi bắt đầu, cô bị chấm sai.

Yêu cầu

Cài đặt chiến lược của JOI-chan để luôn trả lời đúng.

Giao diện nộp bài

Nộp một tệp C++ cài đặt hàm sau:

#include "Memory_lib.h"

int Memory(int N, int M);

Hệ thống cung cấp:

char Get(int I);

Hàm Memory

int Memory(int N, int M);

Hàm mô tả hành động của JOI-chan trong một ngày:

• N là độ dài chuỗi \(S\).
• M là số được ghi nhớ từ đêm trước. Khi bắt đầu bài toán, M = 0.
• Trong mỗi lần gọi Memory, được gọi Get nhiều nhất một lần.
• Giá trị trả về phải thuộc \([0,2^{22}-1]\), hoặc bằng -1, hoặc bằng -2. Trả giá trị khác gây Wrong Answer [1].
• Trả một số trong \([0,2^{22}-1]\) nghĩa là ghi nhớ số đó trước khi ngủ.
• Trả -1 nghĩa là kết luận \(S\) là chuỗi tốt.
• Trả -2 nghĩa là kết luận \(S\) không phải chuỗi tốt.

Hành vi của Memory phải chỉ phụ thuộc vào N, M và giá trị trả về của Get nếu hàm này được gọi. Trong chấm chính thức, Memory được gọi tổng cộng \(2^{22}\cdot 4\) lần ở giai đoạn dựng bảng chuyển trạng thái.

Hàm Get

char Get(int I);

• Chỉ được gọi nhiều nhất một lần trong mỗi lần gọi Memory; gọi từ hai lần trở lên gây Wrong Answer [2].
• Phải có \(1 \le I \le N\); nếu không, gây Wrong Answer [3].
• Hàm trả về ký tự thứ \(I\) của \(S\).

Quy trình chấm

Mỗi tệp chấm chứa nhiều testcase có cùng độ dài \(N\). Nếu phát hiện lỗi, việc chấm dừng ngay.

1. Dựng bảng hành vi

Với mỗi \(M\) thỏa \(0 \le M \le 2^{22}-1\), bộ chấm thực hiện:

1. Với từng \(c\) trong <, >, [, ], gọi Memory(N,M). Nếu Memory gọi Get, bộ chấm cho Get trả về \(c\). Gọi giá trị Memory trả về là \(m(M,c)\).
2. Trong bốn lần gọi ứng với cùng \(M\), quyết định có gọi Get hay không phải giống nhau. Nếu có gọi, cả bốn lần phải gọi với cùng chỉ số \(I\). Nếu không gọi, cả bốn lần phải trả cùng một giá trị. Vi phạm gây Wrong Answer [4]. Gọi chỉ số đó là \(i(M)\); nếu không gọi Get, quy ước \(i(M)=1\).

2. Mô phỏng từng chuỗi

Với mỗi testcase \(S\):

1. Đặt \(M=0\).
2. Lặp các bước sau:
3. Đặt \(c=S_{i(M)}\).
4. Thay \(M\) bằng \(m(M,c)\).
5. Nếu \(M=-1\) hoặc \(M=-2\), chuyển sang kiểm tra kết luận.
6. Nếu đã thực hiện \(15\,000\) bước mà chưa kết luận, gây Wrong Answer [5].
7. Gây Wrong Answer [6] nếu \(S\) tốt nhưng \(M=-2\), hoặc \(S\) không tốt nhưng \(M=-1\).

Nếu tất cả testcase đều hợp lệ, bài nộp được chấp nhận.

Chỉ giai đoạn dựng bảng hành vi được tính thời gian và bộ nhớ trong cách chấm chính thức. Tất cả \(2^{22}\cdot4\) lần gọi Memory ở giai đoạn này phải tránh Wrong Answer [1], [2], [3] và lỗi thực thi.

Ràng buộc

• \(1 \le |S| \le 100\).
• Mọi ký tự của \(S\) thuộc tập {<, >, [, ]}.

Phân nhóm

• Nhóm 1 (10 điểm): \(|S| \le 8\)
• Nhóm 2 (10 điểm): \(|S| \le 14\)
• Nhóm 3 (5 điểm): \(|S| \le 24\)
• Nhóm 4 (5 điểm): \(|S| \le 30\)
• Nhóm 5 (10 điểm): Mọi ký tự của \(S\) là < hoặc >
• Nhóm 6 (60 điểm): Không có ràng buộc bổ sung

Ví dụ

4 1
<>[]

-1

Bạn vừa mua một trò chơi điện tử do công ty JOI phát hành. Một ngày nọ, màn chơi được gọi là "Laser" xuất hiện. Màn này cực kỳ khó, ngay cả người chơi giỏi cũng chỉ có xác suất rất nhỏ vượt qua. Sau nhiều lần thử, bạn nhận ra rằng có thể thắng nếu đưa ra quyết định đủ nhanh và nghĩ đến việc viết chương trình hỗ trợ.

Màn chơi có \(N\) bức tường chắn. Sân chơi là một hình chữ nhật chia thành các ô vuông \(1\times1\). Mỗi ô được biểu diễn bởi cặp số nguyên không âm \((x,y)\). Ô \((0,0)\) nằm ở góc dưới bên trái; ô \((x,y)\) cách đó \(x\) ô sang phải và \(y\) ô lên trên.

Khi màn chơi bắt đầu, kẻ địch thực hiện lần lượt \(M\) đợt tấn công. Trong đợt thứ \(j\), kẻ địch bắn một tia laser thẳng từ ô \((P_j,N+1)\) đến ô \((P_j,0)\).

Mỗi bức tường chiếm một số ô liên tiếp có cùng tọa độ \(y\). Tường \(i\) có chiều ngang \(B_i-A_i+1\), chiều dọc \(1\) và ban đầu chiếm các ô từ \((A_i,i)\) đến \((B_i,i)\). Ngay trước đợt tấn công đầu tiên và giữa hai đợt tấn công liên tiếp, bạn có thể di chuyển các bức tường sang trái hoặc phải bao nhiêu lần tùy ý. Mỗi lần di chuyển, bạn chọn một bức tường và dịch nó đúng một ô sang trái hoặc sang phải.

Laser yếu đi khi va vào tường. Bạn muốn di chuyển các tường sao cho mọi tia laser đều va vào tất cả \(N\) bức tường, đồng thời giảm số lần di chuyển.

Yêu cầu

Với từng bức tường, hãy tìm số lần di chuyển nhỏ nhất của riêng bức tường đó để mọi tia laser đều va vào nó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N,M\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\), mô tả vị trí ban đầu của tường \(i\).
• \(M\) dòng tiếp theo, dòng thứ \(j\) chứa số nguyên \(P_j\), mô tả vị trí tia laser của đợt tấn công thứ \(j\).

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(i\) chứa số lần di chuyển nhỏ nhất của tường \(i\).

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le M \le 200\,000\).
• \(0 \le A_i \le B_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
• \(0 \le P_j \le 1\,000\,000\,000\) với mọi \(1 \le j \le M\).

Phân nhóm

• Nhóm 1 (10 điểm): \(N=1\)
• Nhóm 2 (45 điểm): \(A_i=0\) với mọi \(1 \le i \le N\)
• Nhóm 3 (45 điểm): Không có ràng buộc bổ sung

Ví dụ

4 4
0 3
4 4
2 7
8 11
6
4
3
8

5
10
1
7

7 11
12 39
22 23
5 38
6 47
10 43
0 50
18 46
38
19
15
1
12
29
29
0
6
40
6

34
178
13
6
18
0
36