APIO 2016

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 APIO 2016 - Boat 100 (p) 1.0s 256M
2 APIO 2016 - Fireworks 100 (p) 1.0s 256M
3 APIO 2016 - Gap 100 (p) 1.0s 256M

1. APIO 2016 - Boat

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Dọc bờ bắc sông Hàn có \(N\) trường chèo thuyền, đánh số từ \(1\) đến \(N\) theo thứ tự từ tây sang đông. Mọi thuyền của cùng một trường có cùng màu và không thể phân biệt; thuyền của hai trường khác nhau luôn có màu khác nhau.

Trường \(i\) có thể không gửi thuyền tới lễ hội. Nếu tham gia, trường này được gửi một số nguyên thuyền bất kỳ từ \(a_i\) đến \(b_i\), kể cả hai đầu mút.

Điều kiện quan trọng là: nếu trường \(i\) tham gia, số thuyền trường đó gửi phải lớn hơn số thuyền của mọi trường có chỉ số nhỏ hơn \(i\) đã tham gia.

Hãy đếm số cách các trường có thể gửi thuyền, với điều kiện có ít nhất một trường tham gia. Hai cách khác nhau nếu có một trường gửi số thuyền khác nhau hoặc chỉ tham gia trong một cách.

Dữ liệu vào

  • Dòng đầu chứa số nguyên \(N\).
  • Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(a_i,b_i\).

Dữ liệu ra

In số cách modulo \(1\,000\,000\,007\).

Ràng buộc

  • \(1\le N\le500\).
  • \(1\le a_i\le b_i\le10^9\).

Ví dụ

Ví dụ 1

Input 
2
1 2
2 3
Output 
7

Giải thích

Có bốn cách chỉ một trường tham gia và ba cách cả hai trường tham gia, tổng cộng là bảy cách.

Phân nhóm

Nhóm Điểm Ràng buộc bổ sung
1 9 \(N\le500\) và \(a_i=b_i\) với mọi \(i\)
2 22 \(N\le100\) và \(\sum_{i=1}^{N}(b_i-a_i)\le10^6\)
3 27 \(N\le100\)
4 42 \(N\le500\)

Nguồn

Asia-Pacific Informatics Olympiad 2016, bài Boat.

2. APIO 2016 - Fireworks

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong một màn pháo hoa, mọi khối thuốc nổ nối với bộ kích nổ bằng các dây cháy phải nổ đồng thời. Các dây được nối thành một cây. Tia lửa bắt đầu ở bộ kích nổ, đi dọc dây với vận tốc không đổi; khi đến một nút nối, nó lan ra mọi dây con.

Hình 1 cho thấy cách nối sáu khối thuốc nổ \(E_1,\ldots,E_6\), chiều dài các dây và thời điểm nổ khi tia lửa bắt đầu tại thời điểm \(0\).

{{asset:apio16-fireworks-layout}}

Bạn được phép thay đổi chiều dài các dây, kể cả giảm một dây xuống \(0\) mà vẫn giữ nguyên quan hệ nối của cây. Chi phí thay đổi một dây là trị tuyệt đối của hiệu giữa chiều dài mới và chiều dài ban đầu.

Hình 2 minh họa hai phương án làm tất cả khối thuốc nổ của Hình 1 nổ cùng lúc. Phương án bên trái cho chúng nổ tại thời điểm \(13\) với tổng chi phí \(6\); phương án bên phải cho chúng nổ tại thời điểm \(14\) với tổng chi phí \(5\).

{{asset:apio16-fireworks-adjustments}}

Hãy tìm tổng chi phí nhỏ nhất để mọi khối thuốc nổ phát nổ cùng một thời điểm.

Dữ liệu vào

Dòng đầu chứa hai số nguyên dương \(N,M\), trong đó \(N\) là số nút nối và \(M\) là số khối thuốc nổ. Các nút nối được đánh số từ \(1\) đến \(N\); nút \(1\) đặt bộ kích nổ. Các khối thuốc nổ tương ứng với các đỉnh từ \(N+1\) đến \(N+M\).

Với mỗi đỉnh \(i=2,3,\ldots,N+M\), có một dòng chứa hai số nguyên \(P_i,C_i\). Đỉnh \(i\) được nối với đỉnh cha \(P_i\), và dây đó có chiều dài \(C_i\).

Dữ liệu ra

In tổng chi phí nhỏ nhất.

Ràng buộc

  • \(1\le P_i<i\).
  • \(1\le C_i\le10^9\).
  • Tổng số dây nối với mọi nút nối khác nút đặt bộ kích nổ lớn hơn \(1\).
  • Mỗi đỉnh thuốc nổ là một lá của cây.
  • \(1\le N,M\) và \(N+M\le300\,000\).

Ví dụ

Ví dụ 1

Input 
4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3
Output 
5

Phân nhóm

Nhóm Điểm Ràng buộc bổ sung
1 7 \(N=1\), \(M\le100\)
2 19 \(N+M\le300\) và khoảng cách ban đầu lớn nhất từ bộ kích nổ đến một khối thuốc nổ không quá \(300\)
3 29 \(N+M\le5\,000\)
4 45 \(N+M\le300\,000\)

Nguồn

Asia-Pacific Informatics Olympiad 2016, bài Fireworks.

3. APIO 2016 - Gap

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Có \(N\) số nguyên không âm chưa biết:

\[ A_1<A_2<\cdots<A_N, \]

với \(A_N\le10^{18}\). Hãy tìm khoảng cách lớn nhất giữa hai số liên tiếp:

\[ \max_{1\le i<N}(A_{i+1}-A_i). \]

Các số \(A_i\) không được cung cấp trực tiếp. Chương trình chỉ có thể truy cập chúng qua hàm MinMax.

Yêu cầu cài đặt

Bạn phải cài đặt hàm:

C++
long long findGap(int T, int N);
  • T là số phân nhóm, bằng 1 hoặc 2.
  • N là số lượng số nguyên ẩn.
  • Hàm phải trả về khoảng cách lớn nhất.

Bạn có thể gọi:

C++
void MinMax(long long s, long long t, long long *mn, long long *mx);

Sau lời gọi với \(s\le t\):

  • mn nhận số nhỏ nhất trong tập \(\{A_i\mid s\le A_i\le t\}\);
  • mx nhận số lớn nhất trong tập đó;
  • nếu không có số nào trong đoạn \([s,t]\), cả mn và mx nhận -1.

Nếu gọi với \(s>t\), chương trình bị chấm lỗi. Bài nộp chỉ cần chứa phần cài đặt các hàm yêu cầu, không viết hàm main và không tự cài đặt MinMax. Có thể dùng:

C++
# include "gap.h"

Ví dụ tương tác

Xét \(T=2\), \(N=4\) và dãy ẩn \(2,3,6,8\). Đáp án là \(3\). Một chuỗi lời gọi hợp lệ là:

  • MinMax(1, 2, &mn, &mx), nhận mn = mx = 2;
  • MinMax(3, 7, &mn, &mx), nhận mn = 3, mx = 6;
  • MinMax(8, 9, &mn, &mx), nhận mn = mx = 8.

Grader mẫu trong tệp đính kèm đọc:

Ví dụ 1

Input 
2 4
2 3 6 8

Nó in giá trị trả về của findGap và chi phí truy vấn. Dữ liệu này chỉ dùng để thử nghiệm; grader chính không truyền trực tiếp dãy ẩn cho lời giải.

Chấm điểm

Ngoài việc trả về đáp án đúng, tổng chi phí \(M\) của các lời gọi MinMax phải đủ nhỏ.

  • Nhóm 1, 30 điểm: mỗi lời gọi cộng \(1\) vào \(M\). Nhận đủ điểm của một test nếu
\[ M\le\frac{N+1}{2}. \]
  • Nhóm 2, 70 điểm: nếu đoạn truy vấn chứa \(k\) số ẩn thì lời gọi đó cộng \(k+1\) vào \(M\). Điểm của một test là \(70\) nếu \(M\le3N\); nếu không, điểm test là
\[ \frac{60}{\sqrt{M/N+1}-1}. \]

Điểm của mỗi nhóm là điểm nhỏ nhất trên tất cả test thuộc nhóm đó.

Phân nhóm

Nhóm Điểm Giá trị T
1 30 \(1\)
2 70 \(2\)

Nguồn

Asia-Pacific Informatics Olympiad 2016, bài Gap. Hệ thống sử dụng grader chữ ký C++ tương đương grader chính thức.