JOI 2017 Final Camp - Ngày 3

Có một tuyến xe khách đường dài nối thành phố I với thành phố O. Trên xe có một máy cấp nước cho hành khách và tài xế. Xe rời thành phố I tại thời điểm \(0\) và đến thành phố O tại thời điểm \(X\). Trên đường có \(N\) điểm tiếp nước; xe đến điểm thứ \(i\) tại thời điểm \(S_i\).

Ban đầu máy không có nước. Có thể đổ nước vào máy trước khi khởi hành và khi xe dừng tại một điểm tiếp nước. Nước có giá \(W\) yên mỗi lít tại mọi nơi.

Tại thành phố I có \(M\) hành khách lên xe, được đánh số từ \(1\) đến \(M\). Không ai lên xe ở nơi khác. Hành khách \(j\) cần một lít nước lần đầu tại thời điểm \(D_j\), rồi cứ sau mỗi \(T\) đơn vị thời gian lại cần một lít, tức tại các thời điểm \(D_j+kT\) với \(k=0,1,2,\ldots\). Ta có \(1\le D_j<T\), và \(T\) giống nhau đối với mọi người. Nếu máy hết nước khi một hành khách cần uống, người đó rời xe. Nếu hành khách \(j\) rời xe trước khi tới thành phố O, phải hoàn lại \(C_j\) yên tiền vé.

Tài xế cần một lít nước tại các thời điểm \(kT\) với \(k=0,1,2,\ldots\). Nếu máy hết nước khi tài xế cần uống, xe không thể tiếp tục hành trình.

Không có hai người cần nước cùng lúc. Khi xe đến thành phố O hoặc một điểm tiếp nước, không ai cần nước. Hãy lựa chọn lượng nước đổ vào máy để xe đến được thành phố O và tổng chi phí mua nước cùng tiền hoàn vé là nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa năm số nguyên \(X,N,M,W,T\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(S_i\).
• \(M\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(D_j,C_j\).

Dữ liệu ra

In ra một số nguyên là tổng chi phí nhỏ nhất.

Ràng buộc

• \(1\le X\le 10^{12}\).
• \(1\le N,M\le 200\,000\).
• \(1\le W\le 1\,000\,000\).
• \(1\le T\le X\).
• \(1\le S_i<X\).
• \(1\le D_j<T\).
• \(1\le C_j\le 1\,000\,000\,000\).
• Các giá trị \(D_j\) đôi một khác nhau.
• Khi xe đến thành phố O hoặc một điểm tiếp nước, không ai cần nước.

Phân nhóm

1. \(16\) điểm: \(N\le 8\), \(M\le 8\)
2. \(30\) điểm: \(N\le 100\), \(M\le 100\)
3. \(25\) điểm: \(N\le 2\,000\), \(M\le 2\,000\)
4. \(29\) điểm: Không có

Giới hạn

• Thời gian: 2 giây.
• Bộ nhớ: 256 MB.

Ví dụ

19 1 4 8 7
10
1 20
2 10
4 5
6 5

103

105 3 5 9 10
59
68
71
4 71
6 32
7 29
3 62
2 35

547

1000000000000 1 1 1000000 6
999999259244
1 123456789

333333209997456789

Nguồn

JOI 2016/2017 Spring Training Camp, ngày thi 3, bài Long Distance Coach.

Gần nhà JOI-kun có một dinh thự gồm \(N\) phòng nằm trên một hàng từ đông sang tây. Phòng thứ \(i\) tính từ phía đông được gọi là phòng \(i\). Với mỗi \(1\le i<N\), hành lang nối phòng \(i\) và phòng \(i+1\) có thể đi theo cả hai chiều, nhưng muốn đi vào hành lang từ một trong hai đầu phải có chìa khóa loại \(C_i\).

Phòng \(i\) chứa \(B_i\) chìa khóa có loại \(A_{i,1},A_{i,2},\ldots,A_{i,B_i}\). Khi vào một phòng, JOI-kun nhặt tất cả chìa khóa trong đó. Mỗi chìa khóa được dùng không giới hạn số lần; sở hữu nhiều chìa cùng loại không đem lại lợi ích thêm.

Mỗi truy vấn cho hai phòng \(x,y\): nếu JOI-kun xuất hiện tại phòng \(x\) mà không có chìa khóa nào, liệu cậu có thể đi tới phòng \(y\) hay không?

Dữ liệu vào

• Dòng đầu chứa \(N\).
• Dòng thứ hai chứa \(N-1\) số nguyên \(C_1,C_2,\ldots,C_{N-1}\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(B_i\) rồi đến \(B_i\) số \(A_{i,1},\ldots,A_{i,B_i}\).
• Dòng tiếp theo chứa \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(k\) chứa \(X_k,Y_k\).

Dữ liệu ra

Với mỗi truy vấn, in YES nếu có thể đi từ \(X_k\) tới \(Y_k\), ngược lại in NO.

Ràng buộc

• \(2\le N\le 500\,000\).
• \(1\le Q\le 500\,000\).
• \(1\le B_1+B_2+\cdots+B_N\le 500\,000\).
• \(1\le B_i\le N\).
• \(1\le C_i\le N\).
• \(1\le A_{i,j}\le N\).
• Trong mỗi phòng \(i\), các giá trị \(A_{i,1},\ldots,A_{i,B_i}\) đôi một khác nhau.
• \(1\le X_k,Y_k\le N\) và \(X_k\ne Y_k\).

Phân nhóm

1. \(5\) điểm: \(N,Q,B_1+\cdots+B_N\le 5\,000\)
2. \(5\) điểm: \(N,B_1+\cdots+B_N\le 5\,000\)
3. \(15\) điểm: \(N\le 100\,000\); mọi \(C_i,A_{i,j}\le 20\)
4. \(75\) điểm: Không có

Giới hạn

• Thời gian: 3 giây.
• Bộ nhớ: 256 MB.

Ví dụ

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

YES
NO
NO
YES

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

NO
YES
NO
YES

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

YES
NO
YES

Nguồn

JOI 2016/2017 Spring Training Camp, ngày thi 3, bài Long Mansion.

Đảo JOI là một công viên tự nhiên gồm \(N\) địa điểm, đánh số từ \(0\) đến \(N-1\), và một số con đường hai chiều. Mỗi đường nối hai địa điểm khác nhau, giữa một cặp địa điểm có nhiều nhất một đường, bậc của mỗi địa điểm không quá \(7\), và toàn bộ mạng đường liên thông.

Bạn cần xác định toàn bộ mạng đường bằng cách hỏi IOI-chan liệu hai địa điểm có nối được với nhau khi chỉ được phép đi qua một tập địa điểm cho trước hay không. Bạn được hỏi không quá \(45\,000\) lần.

Chi tiết cài đặt

Chương trình phải khai báo #include "park.h" và cài đặt:

void Detect(int T, int N);

Hàm được gọi đúng một lần. T là số hiệu nhóm, N là số địa điểm.

Để báo một con đường, gọi:

void Answer(int A, int B);

Số lần gọi Answer phải đúng bằng số con đường. Mỗi lần gọi phải thỏa \(0\le A<B\le N-1\) và \((A,B)\) phải là một con đường thật. Vi phạm lần lượt bị chấm Wrong Answer [1], [2]; gọi nhiều hơn một lần với cùng cặp \((A,B)\) bị [3]. Nếu Detect kết thúc mà còn đường chưa báo, nhận [6].

Có thể hỏi:

int Ask(int A, int B, int Place[]);

Mảng Place phải có đúng \(N\) phần tử. Place[i]=1 nghĩa là được phép đi qua địa điểm \(i\), còn Place[i]=0 nghĩa là không. Hàm trả về \(1\) nếu có đường đi từ \(A\) đến \(B\) chỉ qua các địa điểm được phép, ngược lại trả về \(0\).

Mỗi lời gọi phải thỏa \(0\le A<B\le N-1\), mọi Place[i] thuộc \(\{0,1\}\), và Place[A]=Place[B]=1; nếu không nhận Wrong Answer [4]. Hành vi không được đảm bảo nếu độ dài mảng khác \(N\). Gọi quá \(45\,000\) lần nhận [5].

Chương trình có thể cài đặt hàm phụ và dùng biến toàn cục. Chương trình không được đọc/ghi luồng chuẩn hoặc giao tiếp với tệp khác.

Biên dịch và chạy thử

Gói chính thức chứa trình chấm mẫu và mã nguồn mẫu. Nếu bài làm là park.c hoặc park.cpp, có thể biên dịch bằng một trong các lệnh:

gcc -std=c11 -O2 -o grader grader.c park.c -lm
g++ -std=c++14 -O2 -o grader grader.cpp park.cpp

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

Dữ liệu vào của trình chấm mẫu

• Dòng đầu chứa \(T\).
• Dòng thứ hai chứa \(N\).
• Dòng thứ ba chứa số đường \(M\).
• \(M\) dòng tiếp theo chứa \(A_i,B_i\), mô tả một đường hai chiều.

Dữ liệu ra của trình chấm mẫu

Trình chấm mẫu in Accepted. nếu đúng; nếu sai, in một thông báo dạng Wrong Answer [1] rồi kết thúc. Nếu có nhiều lỗi, chỉ một lỗi được báo.

Ràng buộc

• \(1\le T\le 5\).
• \(2\le N\le 1\,400\).
• \(1\le M\le 1\,500\).
• Bậc mỗi địa điểm không quá \(7\).
• Đồ thị liên thông, đơn và vô hướng.

Phân nhóm

1. \(10\) điểm: \(T=1\), \(N\le 250\)
2. \(10\) điểm: \(T=2\), \(M=N-1\); địa điểm \(0,N-1\) có bậc \(1\), mọi địa điểm khác có bậc \(2\)
3. \(27\) điểm: \(T=3\), \(M=N-1\); từ \(0\) tới mỗi \(i>0\) đi qua không quá \(8\) địa điểm trung gian
4. \(30\) điểm: \(T=4\), \(M=N-1\)
5. \(23\) điểm: \(T=5\)

Giới hạn

• Thời gian: 2 giây.
• Bộ nhớ: 256 MB.
• Số lần gọi Ask: không quá \(45\,000\).

Ví dụ giao tiếp

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

Detect(1,6) được gọi. Chuỗi lời gọi minh họa là:

Lời hỏi đầu tiên chỉ cho phép đi qua các địa điểm \(2,3,4,5\), nên có đường đi từ \(3\) tới \(5\) và hàm trả về \(1\). Lời hỏi thứ hai chỉ cho phép đi qua \(0,2,4\), nên không có đường đi từ \(0\) tới \(4\) và hàm trả về \(0\). Chuỗi minh họa không nhất thiết thể hiện một thuật toán có ý nghĩa.

Nguồn

JOI 2016/2017 Spring Training Camp, ngày thi 3, bài Natural Park.