JOI 2019 - Trại huấn luyện, ngày 1

Có \(N\) học sinh tham gia một kỳ thi gồm hai môn Toán và Tin học. Học sinh thứ \(i\) (\(1 \le i \le N\)) đạt \(S_i\) điểm Toán và \(T_i\) điểm Tin học. Giáo sư T và giáo sư I quyết định học sinh nào đỗ theo các tiêu chí sau:

• Giáo sư T coi trọng cả hai môn, nên muốn học sinh đạt ít nhất \(A\) điểm Toán và ít nhất \(B\) điểm Tin học được đỗ.
• Giáo sư I chỉ coi trọng tổng điểm, nên muốn học sinh có tổng điểm ít nhất \(C\) được đỗ.
• Một học sinh chỉ đỗ nếu cả hai giáo sư đều muốn học sinh đó được đỗ.

Bạn chưa biết các giá trị \(A,B,C\). Cho \(Q\) bộ ba số nguyên \((X_j,Y_j,Z_j)\) (\(1 \le j \le Q\)), hãy tính số học sinh đỗ khi \(A=X_j\), \(B=Y_j\) và \(C=Z_j\) cho từng bộ ba.

Dữ liệu vào

Đọc từ đầu vào chuẩn các số nguyên theo định dạng:

N Q
S_1 T_1
...
S_N T_N
X_1 Y_1 Z_1
...
X_Q Y_Q Z_Q

Dữ liệu ra

Ghi \(Q\) dòng. Dòng thứ \(j\) chứa số học sinh đỗ theo bộ tiêu chí \((X_j,Y_j,Z_j)\).

Ràng buộc

• \(1 \le N,Q \le 100\,000\).
• \(0 \le S_i,T_i \le 10^9\) với \(1 \le i \le N\).
• \(0 \le X_j,Y_j \le 10^9\) với \(1 \le j \le Q\).
• \(0 \le Z_j \le 2\times 10^9\) với \(1 \le j \le Q\).
• Tất cả dữ liệu vào là số nguyên.

Phân nhóm

1. (2 điểm) \(N \le 3000\), \(Q \le 3000\).
2. (20 điểm) \(S_i,T_i \le 100\,000\) với mọi \(1 \le i \le N\); \(X_j,Y_j \le 100\,000\) và \(Z_j=0\) với mọi \(1 \le j \le Q\).
3. (21 điểm) \(S_i,T_i \le 100\,000\) với mọi \(1 \le i \le N\); \(X_j,Y_j \le 100\,000\) và \(Z_j \le 200\,000\) với mọi \(1 \le j \le Q\).
4. (57 điểm) Không có ràng buộc bổ sung.

Ví dụ

5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100

2
4
1
1

10 10
41304 98327
91921 28251
85635 59191
30361 72671
28949 96958
99041 37826
10245 2726
19387 20282
60366 87723
95388 49726
52302 69501 66009
43754 45346 3158
25224 58881 18727
7298 24412 63782
24107 10583 61508
65025 29140 7278
36104 56758 2775
23126 67608 122051
56910 17272 62933
39675 15874 117117

1
3
5
8
8
3
3
3
5
6

Nguồn

JOI 2018/2019 Spring Training Camp, ngày 1. Đề gốc tiếng Anh, do Japanese Committee for the International Olympiad in Informatics công bố. Bản dịch tiếng Việt theo CC BY-SA 4.0.

Có \(N\) hòn đảo, đánh số từ \(0\) đến \(N-1\), được nối bằng \(N-1\) cây cầu hai chiều. Có thể đi từ bất kỳ đảo nào đến bất kỳ đảo nào bằng cầu. Mỗi đảo nối trực tiếp với không quá \(18\) cây cầu, và có một chú hải ly sinh sống.

Khi đúng ba chú hải ly gặp nhau, chúng chọn hòn đảo làm tổng số cầu mà cả ba phải đi qua nhỏ nhất. Hòn đảo như vậy luôn tồn tại duy nhất và có thể là nơi ở của một trong ba chú.

Bạn muốn xác định tất cả các cây cầu nhưng không thể kiểm tra trực tiếp. Mỗi lần, bạn chọn ba đảo phân biệt \(u,v,w\), yêu cầu ba chú hải ly ở đó gặp nhau, rồi được biết đảo mà chúng chọn. Hãy tìm cấu trúc nối các đảo bằng ít yêu cầu nhất có thể.

Giao diện tương tác

Nộp tệp meetings.cpp, khai báo #include "meetings.h" và cài đặt:

void Solve(int N);

Hàm được gọi đúng một lần cho mỗi test; \(N\) là số đảo. Chương trình có thể gọi hai hàm do thư viện cung cấp:

int Query(int u, int v, int w);
void Bridge(int u, int v);

• Query(u, v, w) trả về đảo nơi ba chú hải ly gặp nhau. Các chỉ số phải thuộc \([0,N-1]\) và đôi một khác nhau, nếu không nhận Wrong Answer [1]. Không được gọi quá \(100\,000\) lần, nếu không nhận Wrong Answer [2].
• Bridge(u, v) báo rằng có cầu nối trực tiếp hai đảo. Phải có \(0\le u<v\le N-1\), nếu không nhận Wrong Answer [3]. Nếu không có cầu đó, nhận Wrong Answer [4]. Nếu báo cùng một cầu nhiều lần, nhận Wrong Answer [5]. Khi Solve kết thúc, phải đã gọi Bridge đúng \(N-1\) lần, nếu không nhận Wrong Answer [6].

Có thể khai báo biến toàn cục và hàm phụ. Không được đọc đầu vào chuẩn, ghi đầu ra chuẩn hoặc giao tiếp với các tệp khác bằng bất kỳ cách nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Thư viện thử nghiệm

Gói thư viện mẫu chính thức chứa grader.cpp, meetings.h và mã nguồn mẫu. Đặt các tệp trong cùng thư mục và biên dịch bằng:

g++ -std=gnu++14 -O2 -o grader grader.cpp meetings.cpp

Trình chấm mẫu chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Trình chấm thực tế khác trình chấm mẫu.

Dữ liệu vào

Đầu vào của trình chấm mẫu có dạng:

N
A_0 B_0
...
A_{N-2} B_{N-2}

Mỗi dòng \(A_i,B_i\) mô tả một cây cầu nối hai đảo đó.

Dữ liệu ra

Nếu chương trình trả lời đúng, trình chấm mẫu ghi số lần gọi Query, chẳng hạn Accepted: 100. Nếu có lỗi, nó ghi loại lỗi, chẳng hạn Wrong Answer [1]. Nếu có nhiều loại lỗi, chỉ một loại được báo.

Ràng buộc

• \(3\le N\le 2000\).
• \(0\le A_i<B_i\le N-1\) với \(0\le i\le N-2\).
• Có thể đi giữa mọi cặp đảo bằng cầu.
• Mỗi đảo nối trực tiếp với không quá \(18\) cây cầu.

Phân nhóm

1. (7 điểm) \(N\le 7\).
2. (10 điểm) \(N\le 50\).
3. (12 điểm) \(N\le 300\).
4. (71 điểm) Không có ràng buộc bổ sung.

Ở các nhóm \(1,2,3\), chỉ nhận toàn bộ điểm của nhóm khi trả lời đúng tất cả các test trong nhóm.

Ở nhóm \(4\), nếu trả lời đúng tất cả các test, gọi \(X\) là số lần gọi Query lớn nhất trong một test của nhóm. Điểm của nhóm là:

• \(49\) điểm nếu \(40\,000<X\le100\,000\).
• \(71\) điểm nếu \(X\le40\,000\).

Ví dụ giao tiếp

5
0 1
0 2
1 3
1 4

Một chuỗi lời gọi tương ứng:

Nguồn

JOI 2018/2019 Spring Training Camp, ngày 1. Đề gốc tiếng Anh, do Japanese Committee for the International Olympiad in Informatics công bố. Bản dịch tiếng Việt theo CC BY-SA 4.0.

Quán cà ri JOI nổi tiếng với những chiếc bánh naan rất dài. Quán có \(L\) hương vị, đánh số từ \(1\) đến \(L\). Món được yêu thích nhất là bánh naan đặc biệt JOI, dài \(L\) cm. Vị trí \(x\) trên bánh là điểm cách đầu bên trái \(x\) cm. Đoạn từ vị trí \(j-1\) đến vị trí \(j\) mang hương vị \(j\) (\(1 \le j \le L\)).

Có \(N\) người đến quán, mỗi người có sở thích riêng. Khi người thứ \(i\) ăn \(1\) cm bánh mang hương vị \(j\), người đó nhận được \(V_{i,j}\) đơn vị hạnh phúc (\(1 \le i \le N\), \(1 \le j \le L\)).

Họ chỉ gọi một chiếc bánh naan đặc biệt JOI và chia bánh như sau:

1. Chọn \(N-1\) số hữu tỉ \(X_1,\ldots,X_{N-1}\) sao cho \(0<X_1<X_2<\cdots<X_{N-1}<L\).
2. Chọn một hoán vị \(P_1,\ldots,P_N\) của các số \(1,\ldots,N\).
3. Cắt bánh tại mỗi vị trí \(X_k\) (\(1 \le k \le N-1\)), thu được \(N\) phần.
4. Với mỗi \(1 \le k \le N\), đưa phần bánh từ vị trí \(X_{k-1}\) đến vị trí \(X_k\) cho người thứ \(P_k\). Quy ước \(X_0=0\) và \(X_N=L\).

Một cách chia được gọi là công bằng nếu mỗi người nhận được ít nhất \(\frac{1}{N}\) lượng hạnh phúc mà người đó sẽ nhận khi ăn cả chiếc bánh.

Cho sở thích của \(N\) người, hãy xác định có thể chia bánh công bằng hay không. Nếu có, hãy tìm một cách chia như vậy.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N L
V_{1,1} V_{1,2} ... V_{1,L}
...
V_{N,1} V_{N,2} ... V_{N,L}

Tất cả dữ liệu vào là số nguyên.

Dữ liệu ra

Nếu không có cách chia công bằng, ghi một dòng chứa -1. Ngược lại, ghi:

A_1 B_1
...
A_{N-1} B_{N-1}
P_1 P_2 ... P_N

Trong đó \(A_k,B_k\) là các số nguyên biểu diễn \(X_k=A_k/B_k\) với \(1 \le k \le N-1\). Nếu có nhiều đáp án đúng, có thể ghi bất kỳ đáp án nào.

Ràng buộc

• \(2 \le N \le 2000\).
• \(1 \le L \le 2000\).
• \(1 \le V_{i,j} \le 100\,000\) với \(1 \le i \le N\), \(1 \le j \le L\).

Nếu xuất ra một cách chia, đáp án phải thỏa mãn:

• \(1 \le B_k \le 10^9\) với \(1 \le k \le N-1\).
• \(0<A_1/B_1<A_2/B_2<\cdots<A_{N-1}/B_{N-1}<L\).
• \(P_1,\ldots,P_N\) là một hoán vị của \(1,\ldots,N\).
• Mỗi người thứ \(i\) nhận được lượng hạnh phúc ít nhất \((V_{i,1}+\cdots+V_{i,L})/N\) với \(1 \le i \le N\).

Không yêu cầu \(A_k\) và \(B_k\) nguyên tố cùng nhau. Với các ràng buộc đầu vào trên, nếu tồn tại cách chia công bằng thì luôn tồn tại một đáp án đúng có mọi mẫu số không vượt quá \(10^9\).

Phân nhóm

1. (5 điểm) \(N=2\).
2. (24 điểm) \(N \le 6\) và \(V_{i,j} \le 10\) với mọi \(1 \le i \le N\), \(1 \le j \le L\).
3. (71 điểm) Không có ràng buộc bổ sung.

Ví dụ

2 5
2 7 1 8 2
3 1 4 1 5

14 5
2 1

7 1
1
2
3
4
5
6
7

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

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

15 28
35 28
50 28
70 28
3 1 5 2 4

Nguồn

JOI 2018/2019 Spring Training Camp, ngày 1. Đề gốc tiếng Anh, do Japanese Committee for the International Olympiad in Informatics công bố. Bản dịch tiếng Việt theo CC BY-SA 4.0.