JOI 2017 Open Contest - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2017 - Amusement Park	100 (p)	3.0s	256M
2	JOI 2017 - Bulldozer	100 (p)	2.0s	512M
3	JOI 2017 - Golf	100 (p)	5.0s	1G

1. JOI 2017 - Amusement Park

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

JOI-kun và em gái IOI-chan đang chơi tại công viên JOIOI. Công viên có \(N\) trò chơi, đánh số từ \(0\) đến \(N-1\), và \(M\) đường đi hai chiều. Mỗi đường nối hai trò chơi khác nhau; từ mọi trò chơi đều có thể đi đến mọi trò chơi khác.

Mỗi trò chơi có một bảng tin, trên đó JOI-kun được ghi đúng một số \(0\) hoặc \(1\). Nội dung đã ghi không bị khách khác thay đổi. Hai người sẽ chơi riêng rồi gặp lại. Không có thiết bị liên lạc, JOI-kun muốn truyền cho IOI-chan số nguyên \(X\) biểu diễn thời gian gặp mặt:

JOI-kun ghi \(0\) hoặc \(1\) lên bảng tin của mọi trò chơi.
IOI-chan bắt đầu tại một trò chơi, đọc bảng tin ở đó, rồi có thể đi qua các đường và đọc bảng tin tại mỗi nơi cô đến.

Hãy viết hai chương trình để IOI-chan xác định đúng \(X\) với ít lần di chuyển. Hai chương trình nhận cùng một đồ thị, gồm cùng số hiệu đỉnh và cùng thứ tự các cạnh.

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

Bạn cần cài đặt hai hàm sau trong cùng bài nộp:

C++

void Joi(int N, int M, int A[], int B[], long long X, int T);
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T);

Mỗi hàm được gọi đúng một lần cho mỗi bộ kiểm thử.

Trong cả hai hàm, \(N,M\) là số trò chơi và số đường; cạnh thứ \(i\) nối \(A[i]\) với \(B[i]\) (\(0\le i<M\)); \(T\) là số hiệu nhóm. Với Joi, \(X\) là số cần truyền. Với Ioi, \(P\) là trò chơi ban đầu và \(V\) là giá trị trên bảng tin tại \(P\).

Trong Joi, gọi:

C++

void MessageBoard(int attr, int msg);

để ghi msg lên bảng tại attr.

Phải có \(0\le attr<N\); nếu không, nhận Wrong Answer[1].
Không được gọi hai lần với cùng attr; nếu vi phạm, nhận Wrong Answer[2].
msg phải bằng \(0\) hoặc \(1\); nếu không, nhận Wrong Answer[3].
Phải gọi MessageBoard đúng \(N\) lần; nếu không, nhận Wrong Answer[4].
Một lời gọi không hợp lệ khiến tiến trình Joi dừng ngay.

Trong Ioi, gọi:

C++

int Move(int dest);

để di chuyển tới dest; hàm trả về giá trị trên bảng tin tại đó.

Phải có \(0\le dest<N\); nếu không, nhận Wrong Answer[6].
dest phải kề vị trí hiện tại; nếu không, nhận Wrong Answer[7].
Không được gọi Move quá \(20\,000\) lần; nếu vi phạm, nhận Wrong Answer[8].
Ioi phải trả về đúng \(X\); nếu không, nhận Wrong Answer[5].

Bạn có thể khai báo hàm phụ và biến toàn cục, nhưng mọi hàm/biến nội bộ nên được khai báo static để tránh xung đột tên. Khi chấm chính thức, Joi và Ioi chạy trong hai tiến trình riêng biệt, vì vậy không thể chia sẻ biến toàn cục. Không được đọc/ghi luồng chuẩn hoặc dùng tệp hay phương thức khác để liên lạc.

Định dạng bộ chấm mẫu

Bộ chấm mẫu đọc:

Dòng đầu chứa \(N,M,X,P,T\).
\(M\) dòng tiếp theo, dòng thứ \(i+1\) chứa \(A[i],B[i]\).

Nếu đúng, bộ chấm mẫu in Accepted : #move=12345, trong đó số cuối là số lần gọi Move. Nếu sai, nó in Wrong Answer [k]. Nếu có nhiều lỗi, chỉ một lỗi được báo. Bộ chấm mẫu chạy trong một tiến trình và khác bộ chấm chính thức; chương trình không được dựa vào sự khác biệt này.

Ràng buộc

\(60\le N\le 10\,000\).
\(1\le M\le 20\,000\).
\(0\le A[i],B[i]<N\) và \(A[i]\ne B[i]\).
Không có hai cạnh trùng nhau, kể cả khi đảo thứ tự hai đầu mút.
Đồ thị liên thông.
\(0\le X\le 2^{60}-1\).
\(0\le P<N\).

Phân nhóm

Nhóm 1 (8 điểm): \(T=1\), \(N\le 300\).
Nhóm 2 (10 điểm): \(T=2\).
Nhóm 3 (10 điểm): \(T=3\), \(M=N-1\), \(A[i]=i\), \(B[i]=i+1\) với \(0\le i\le N-2\), và gọi Move không quá \(250\) lần.
Nhóm 4 (55 điểm): \(T=4\), \(N\ge 240\). Gọi \(C\) là số lần gọi Move lớn nhất trên mọi bộ kiểm thử của nhóm. Điểm nhóm là

\[ \begin{cases} 0, & C>960,\\ \left\lfloor 55-13\log_2\left(\dfrac{C}{120}\right)\right\rfloor, & 120<C\le 960,\\ 55, & C\le 120. \end{cases} \]

Khi \(C>960\), hệ thống chính thức có thể hiển thị Correct : 0 point hoặc Incorrect.

Nhóm 5 (17 điểm): \(T=5\) và gọi Move không quá \(120\) lần.

Ví dụ giao tiếp

PDF chỉ hiển thị phần đầu của ví dụ vì dữ liệu đầy đủ khá dài. Tệp sample-01.txt đầy đủ nằm trong tệp đính kèm chính thức.

60 59 123 5 1
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
...

Lời gọi	Giải thích
Trong ví dụ, `Joi` nhận \(X=123\)	và ghi lần lượt một số bit, trong đó các bảng \(0,1,2,3,4,5\) nhận \(0,1,1,0,0,1\).
`Ioi` bắt đầu tại \(P=5\) với \(V=1\); một phần chuỗi gọi là `Move(4)`, `Move(3)`, `Move(2)`, `Move(3)`,	nhận lại \(0,0,1,0\), rồi trả về \(123\).

Nguồn

JOI 2016/2017 Open Contest.

2. JOI 2017 - Bulldozer

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

Vương quốc JOI nổi tiếng về vàng. Lãnh thổ được biểu diễn trên mặt phẳng tọa độ, với \(N\) địa điểm. Địa điểm thứ \(i\) nằm tại \((X_i,Y_i)\) và chứa vàng hoặc đá, nhưng không chứa cả hai.

Nếu địa điểm chứa vàng, khai thác một lần thu được vàng trị giá \(V_i\). Nếu chứa đá, khai thác một lần phải trả chi phí \(C_i\) để xử lý đá.

Để khai thác, trước hết chọn hai đường thẳng song song, rồi khai thác một lần toàn bộ vàng và đá trong miền nằm giữa hai đường, kể cả trên hai đường biên. Lợi nhuận bằng tổng giá trị vàng trừ tổng chi phí xử lý đá trong miền. Có thể chọn một miền không chứa địa điểm nào.

Hãy tính lợi nhuận lớn nhất.

Dữ liệu vào

Dòng đầu chứa \(N\).
\(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(X_i,Y_i,W_i\). Nếu \(W_i\ge1\), địa điểm chứa vàng trị giá \(V_i=W_i\); nếu \(W_i\le-1\), địa điểm chứa đá với chi phí \(C_i=-W_i\).

Dữ liệu ra

In lợi nhuận lớn nhất.

Ràng buộc

\(1\le N\le 2\,000\).
\(-1\,000\,000\,000\le X_i,Y_i\le1\,000\,000\,000\).
\(1\le |W_i|\le1\,000\,000\,000\).
Không có hai địa điểm trùng nhau.

Phân nhóm

\(5\) điểm: \(N\le100\) và \(Y_i=0\) với mọi \(i\)
\(20\) điểm: \(N\le100\); không có ba điểm phân biệt thẳng hàng; hai đường thẳng khác nhau cùng đi qua hai điểm của dữ liệu không song song
\(35\) điểm: Không có ba điểm phân biệt thẳng hàng; hai đường thẳng khác nhau cùng đi qua hai điểm của dữ liệu không song song
\(20\) điểm: Không có ba điểm phân biệt thẳng hàng
\(20\) điểm: Không có ràng buộc bổ sung

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Có thể chọn miền chứa các địa điểm \(2,3,4,5\), thu lợi nhuận lớn nhất là \(19\).

Ví dụ 2

Input

Output

Giải thích

Các điểm \(1,2,3\) thẳng hàng; các điểm \(4,5,6\) cũng thẳng hàng.

Ví dụ 3

Input

Output

Giải thích

Không có ba điểm phân biệt thẳng hàng, nhưng đường qua điểm \(1,2\) song song với đường qua điểm \(3,4\).

Ví dụ 4

Input

2
0 0 -1
1 0 -1

Output

Giải thích

Có thể chọn miền không chứa vàng hoặc đá nào.

Ví dụ 5

Input

Output

Nguồn

JOI 2016/2017 Open Contest.

3. JOI 2017 - Golf

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

JOI-kun luyện tập trên một sân golf đặc biệt, được biểu diễn bằng mặt phẳng tọa độ. Có \(N\) chướng ngại vật. Chướng ngại vật thứ \(i\) là hình chữ nhật kín

\[ A_i\le x\le B_i,\qquad C_i\le y\le D_i. \]

Hai chướng ngại vật, kể cả biên, không giao nhau. Điểm bắt đầu là \((S,T)\) và điểm kết thúc là \((U,V)\); hai điểm khác nhau và không nằm trên chướng ngại vật hay biên của chúng.

Mỗi cú đánh có thể đưa bóng đi một khoảng tùy ý theo một trong bốn hướng song song với trục tọa độ. Quỹ đạo bóng không được chạm phần trong của chướng ngại vật, nhưng có thể đi trên biên hoặc dừng trên biên. Từ đó, bóng có thể đổi hướng bằng một cú đánh về phía không bị chướng ngại vật chắn.

Hãy tính số cú đánh ít nhất để đưa bóng từ điểm đầu đến điểm cuối.

Dữ liệu vào

Dòng đầu chứa \(S,T,U,V\).
Dòng thứ hai chứa \(N\).
\(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(A_i,B_i,C_i,D_i\).

Dữ liệu ra

In số cú đánh ít nhất.

Ràng buộc

\(1\le S,T,U,V\le1\,000\,000\,000\).
\(1\le N\le100\,000\).
\(1\le A_i<B_i\le1\,000\,000\,000\).
\(1\le C_i<D_i\le1\,000\,000\,000\).
\((S,T)\ne(U,V)\).
Hai chướng ngại vật, kể cả biên, không giao nhau.
Điểm đầu và điểm cuối không nằm trên chướng ngại vật hay biên của chúng.

Phân nhóm

\(10\) điểm: \(S,T,U,V\le1\,000\), \(N\le1\,000\), \(B_i,D_i\le1\,000\) với mọi \(i\)
\(20\) điểm: \(N\le1\,000\)
\(70\) điểm: Không có ràng buộc bổ sung

Ví dụ

Ví dụ 1

Input

3 5 8 6
1
5 6 2 8

Output

Giải thích

Có thể đi theo \((3,5)\to(3,2)\to(8,2)\to(8,6)\) bằng ba cú đánh, và không thể dùng ít hơn.

Ví dụ 2

Input

Output

Giải thích

Có thể đưa bóng từ điểm đầu đến điểm cuối bằng một cú đánh.

Ví dụ 3

Input

20 68 85 74
5
30 70 14 100
5 24 15 67
75 86 75 79
75 90 19 62
93 98 26 58

Output

Nguồn

JOI 2016/2017 Open Contest.