JOI 2018 Final Camp - Ngày 2

Một ngày nọ, JOI-kun có được cỗ máy thời gian và quyết định đến Nhật Bản vào thế kỷ thứ IX. Cậu gặp Kukai, một trong những nhà sư nổi tiếng nhất Nhật Bản thời bấy giờ. Kukai muốn phát triển một phương pháp tu hành mới.

Việc tu hành diễn ra như sau:

• Kukai đọc một bài kinh gồm \(N\) câu. Các câu có thứ tự cố định và phải được đọc đúng thứ tự đó.
• Mỗi câu được gán một số nguyên từ \(1\) đến \(N\). Không có hai câu nào được gán cùng một số.
• Mỗi ngày được chia thành \(N\) khoảng thời gian bằng nhau. Câu được gán số \(i\) phải được đọc trong khoảng thời gian thứ \(i\) của ngày. Mỗi câu đủ ngắn để luôn có thể đọc xong trong một khoảng thời gian.

Kukai muốn đọc hết bài kinh nhanh nhất có thể. Số ngày cần thiết phụ thuộc vào cách gán số cho các câu. Hãy đếm số cách gán số khiến Kukai cần đúng \(K\) ngày để đọc hết bài kinh khi lựa chọn cách đọc tối ưu. In kết quả lấy dư cho \(1\,000\,000\,007\).

Dữ liệu vào

Một dòng chứa hai số nguyên \(N,K\), lần lượt là số câu và số ngày cần thiết.

Dữ liệu ra

In số cách gán số thỏa mãn yêu cầu, lấy dư cho \(1\,000\,000\,007\).

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(1 \le K \le N\).

Phân nhóm

1. \(4\) điểm: \(N \le 10\)
2. \(20\) điểm: \(N \le 300\)
3. \(25\) điểm: \(N \le 3\,000\)
4. \(51\) điểm: Không có ràng buộc bổ sung.

Ví dụ

3 2

4

10 5

1310354

Nguồn

JOI 2018 Spring Training Camp, ngày 2 - Asceticism.

Đây là bài chỉ nộp kết quả (output-only). Với mỗi dữ liệu vào được cung cấp, bạn cần nộp tệp kết quả, không phải chương trình sinh kết quả.

Vương quốc IOI có \(N\) thành phố được đánh số từ \(1\) đến \(N\) và \(N-1\) con đường hai chiều được đánh số từ \(1\) đến \(N-1\). Con đường thứ \(i\) nối hai thành phố \(A_i\) và \(B_i\). Có đường đi giữa mọi cặp thành phố.

Khoảng cách giữa hai thành phố là số con đường ít nhất cần đi qua để đi từ thành phố này đến thành phố kia. Tổng khoảng cách của vương quốc là tổng khoảng cách trên tất cả các cặp thành phố khác nhau, mỗi cặp không có thứ tự được tính một lần.

Nhà vua dự định xây thêm \(K\) con đường để giảm tổng khoảng cách, giúp việc đi lại thuận tiện hơn. Là phụ tá của nhà vua, bạn hãy tìm một phương án xây đúng \(K\) con đường. Tổng khoảng cách sau khi xây càng nhỏ thì điểm số càng cao.

Dữ liệu vào

Bài có sáu dữ liệu vào. Mỗi dữ liệu có dạng:

• Dòng đầu chứa ba số nguyên \(N,K,W_0\). Trong đó \(N\) là số thành phố, \(K\) là số con đường cần xây thêm, còn \(W_0\) là tham số dùng để tính điểm.
• Trong \(N-1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\), mô tả con đường có sẵn thứ \(i\).

Dữ liệu ra

Với mỗi dữ liệu vào, nộp một tệp kết quả gồm đúng \(K\) dòng. Dòng thứ \(j\) chứa hai số nguyên \(X_j,Y_j\), với \(1 \le X_j,Y_j \le N\), biểu thị hai thành phố được nối bởi con đường xây thêm thứ \(j\).

Kết quả chỉ hợp lệ nếu tuân theo định dạng trên. Có thể xây thêm đường nối một cặp thành phố vốn đã có đường nối, như trong ví dụ 2.

Ràng buộc

• \(1 \le N \le 1\,000\).
• \(1 \le A_i < B_i \le N\) với \(1 \le i \le N-1\).
• \((A_i,B_i) \ne (A_k,B_k)\) với \(1 \le i < k \le N-1\).
• Có đường đi giữa mọi cặp thành phố.

Chấm điểm

Với mỗi dữ liệu vào, kết quả sai định dạng nhận \(0\) điểm. Nếu kết quả hợp lệ, gọi \(W\) là tổng khoảng cách sau khi xây thêm các con đường theo phương án của bạn, và \(P\) là số điểm tối đa của dữ liệu đó. Đặt

Điểm cho dữ liệu này là

Điểm của bài là tổng điểm của sáu dữ liệu, sau đó làm tròn đến số nguyên gần nhất.

Các tham số của sáu dữ liệu vào như sau:

Ví dụ

4 1 8
1 2
2 3
3 4

1 4

4 1 8
1 2
2 3
3 4

1 2

Nguồn

JOI 2018 Spring Training Camp, ngày 2 - Road Service.

Trong lễ khai mạc IOI 2018, \(N\) thí sinh diễu hành thành một hàng dọc trên một trục số. Tất cả đều hướng về chiều dương. Tại thời điểm \(0\), thí sinh thứ \(i\) tính từ đầu hàng đứng ở tọa độ \(-i\). IOI-chan, người cầm cờ, đứng ở tọa độ \(0\).

Thí sinh thứ \(i\) có một giá trị gọi là độ chậm \(D_i\). Các thí sinh tuân theo quy tắc:

• Nếu khoảng cách từ thí sinh thứ \(i\) đến người ngay phía trước (một thí sinh khác hoặc IOI-chan) lớn hơn hoặc bằng \(D_i+1\), thí sinh thứ \(i\) lập tức di chuyển đến vị trí cách người đó đúng \(1\) đơn vị ở phía sau. Nếu chưa đủ khoảng cách này, thí sinh đứng yên.

IOI-chan di chuyển theo chiều dương với tốc độ \(1\) đơn vị khoảng cách trên mỗi đơn vị thời gian. Mỗi thí sinh di chuyển tức thời ngay khi điều kiện trên được thỏa mãn.

Bạn là phóng viên đưa tin về lễ khai mạc. Lẽ ra phải chụp ảnh, nhưng bạn lại ngủ suốt buổi lễ. Bạn đành chụp ảnh hội trường rồi vẽ thêm hình mọi người lên ảnh. Để không bị phát hiện, đồng thời ước lượng thời gian cần vẽ, bạn muốn trả lời \(Q\) câu hỏi: tại thời điểm \(T_j\), có bao nhiêu người đứng ở tọa độ thuộc đoạn \([L_j,R_j]\), kể cả hai đầu mút? Số người này bao gồm cả IOI-chan.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N,Q\). \(N\) là số thí sinh, không tính IOI-chan.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(D_i\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(T_j,L_j,R_j\) mô tả câu hỏi thứ \(j\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) chứa đáp án của câu hỏi thứ \(j\).

Ràng buộc

• \(1 \le N \le 500\,000\).
• \(1 \le Q \le 500\,000\).
• \(1 \le D_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
• \(1 \le T_j \le 1\,000\,000\,000\) với \(1 \le j \le Q\).
• \(1 \le L_j \le R_j \le 1\,000\,000\,000\) với \(1 \le j \le Q\).

Phân nhóm

1. \(7\) điểm: \(D_i=1\) với mọi \(1 \le i \le N\)
2. \(12\) điểm: \(N \le 1\,000\); \(Q \le 1\,000\); \(T_j \le 1\,000\) và \(1 \le L_j \le R_j \le 1\,000\) với mọi \(1 \le j \le Q\)
3. \(81\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

0
1
1
2
1
2

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

2
0

6 6
11
36
28
80
98
66
36 29 33
190 171 210
18 20 100
1000 900 1100
92 87 99
200 100 300

1
6
0
5
2
7

Nguồn

JOI 2018 Spring Training Camp, ngày 2 - Worst Reporter 3.