CEOI 2016 - Ngày 1 - 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	CEOI 2016 - ICC	100 (p)	3.0s	256M
2	CEOI 2016 - Kangaroo	100 (p)	1.0s	256M
3	CEOI 2016 - Trick	100 (p)	5.0s	256M

1. CEOI 2016 - ICC

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

Astro đang theo dõi các thành phố trên hành tinh Mar Sara. Ban đầu có $N$ thành phố, được đánh số từ $1$ đến $N$, và chưa có con đường nào. Người Terran sẽ lần lượt xây dựng các con đường sao cho sau mỗi lần xây, hai thành phố ở hai đầu đường chưa được nối với nhau bằng một đường đi trước đó. Vì vậy, các con đường luôn tạo thành một cây sau khi xây xong.

Sau mỗi lần xây đường, bạn cần xác định hai đầu mút của con đường mới trước khi con đường tiếp theo được xây. Bạn có thể dùng SETI để hỏi về hai tập thành phố rời nhau. Với hai tập $A$ và $B$, SETI cho biết có hay không một con đường trực tiếp nối một thành phố thuộc $A$ với một thành phố thuộc $B$ trong đồ thị hiện tại.

Giao diện hàm

Trong C/C++, hãy cài đặt hàm sau trong chương trình nộp:

C++

void run(int N);

Tệp icc.h khai báo các hàm mà grader cung cấp:

C++

int query(int size_a, int size_b, int a[], int b[]);
void setRoad(int a, int b);

Grader gọi run(N) một lần cho mỗi kiểm thử.
Gọi query(size_a, size_b, a, b) để hỏi về hai tập thành phố. Hai tập phải rời nhau và các chỉ số thành phố nằm trong đoạn $[1,N]$. Hàm trả về $1$ nếu hiện có ít nhất một con đường trực tiếp nối hai tập, ngược lại trả về $0$.
Khi xác định được con đường mới, gọi setRoad(a,b) với hai đầu mút. Nếu câu trả lời sai, kiểm thử hiện tại nhận $0$ điểm và chương trình kết thúc. Nếu đây là con đường thứ $N-1$, kiểm thử kết thúc. Nếu chưa, một con đường mới được xây trước lần gọi tiếp theo.
Nếu run kết thúc trước khi xác định đủ $N-1$ con đường, kiểm thử nhận $0$ điểm.

Hãy thêm #include "icc.h" trong mã nguồn. Không cần đọc dữ liệu vào hoặc in dữ liệu ra bằng luồng chuẩn.

Phân nhóm

Nhóm 1: $N=15$, được gọi query nhiều nhất $1500$ lần, chiếm $7\%$ số điểm.
Nhóm 2: $N=50$, được gọi query nhiều nhất $2500$ lần, chiếm $11\%$ số điểm.
Nhóm 3: $N=100$, được gọi query nhiều nhất $2250$ lần, chiếm $22\%$ số điểm.
Nhóm 4: $N=100$, được gọi query nhiều nhất $2000$ lần, chiếm $21\%$ số điểm.
Nhóm 5: $N=100$, được gọi query nhiều nhất $1775$ lần, chiếm $29\%$ số điểm.
Nhóm 6: $N=100$, được gọi query nhiều nhất $1625$ lần, chiếm $10\%$ số điểm.

Để nhận điểm của một nhóm, bạn phải xác định đúng tất cả các con đường trong mọi kiểm thử của nhóm đó và không vượt quá giới hạn số lần gọi query.

Ví dụ

Ví dụ minh họa một lần chạy với $N=4$. Mỗi dòng query cho biết kết quả grader trả về.

run(4)
query(1, 3, {1}, {2, 3, 4}) -> 0
query(1, 2, {2}, {3, 4})    -> 1
query(1, 1, {2}, {3})       -> 0
setRoad(2, 4)

query(2, 2, {2, 4}, {1, 3}) -> 0
setRoad(1, 3)

query(2, 2, {2, 4}, {1, 3}) -> 1
query(1, 2, {2}, {1, 3})    -> 0
query(1, 1, {4}, {3})       -> 0
setRoad(4, 1)

Ban đầu, con đường mới là $(2,4)$. Sau khi gọi setRoad(2,4), con đường mới tiếp theo là $(1,3). Sau đó, con đường cuối cùng là $(1,4). Truy vấn lặp lại có thể cho kết quả khác vì đồ thị đã được cập nhật.

Nguồn

CEOI 2016, ngày 1, bài 1.

2. CEOI 2016 - Kangaroo

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

Một khu vườn được biểu diễn dưới dạng một hàng ngang gồm $N$ ô đánh số từ 1 đến $N$. Ban đầu, tất cả các ô đều có chứa trái cây. Một con kangaroo chạy tới khu vườn từ ô $cs$. Sau đó nó bắt đầu nhảy đến từng ô trong vườn để ăn hết trái cây ở các ô đó. Nó sẽ luôn kết thúc lộ trình ăn uống của mình ở ô $cf$, sau khi nhảy qua đúng $N$ ô khác nhau, mỗi ô được nhảy vào đúng một lần, bao gồm cả ô $cs$ và ô $cf$. Hiển nhiên, con kangaroo này sẽ nhảy tổng cộng $N−1$ bước.

Vì con kangaroo không muốn bị bắt nên sau mỗi bước nhảy nó đều sẽ đổi hướng nhảy so với lần nhảy trước: Nếu nó đang đứng ở ô $current$ sau khi nhảy đến từ ô $prev$, và từ ô này nó sẽ tiếp tục nhảy đến ô $next$, thì những điều kiện sau bắt buộc phải được thỏa mãn:

Nếu $prev$ < $current$ thì $next$ < $current$;
Nếu $current$ < $prev$ thì $current$ < $next$.
Cho trước $N$ là số lượng ô trong vườn, $cs$ là ô xuất phát của kangaroo và $cf$ là ô cuối cùng mà nó nhảy tới, bạn hãy tính số lượng lộ trình phân biệt mà con kangaroo này có thể nhảy được trong khu vườn.

Input

Gồm một dòng duy nhất chứa ba số nguyên $N$, $cs$ và $cf$.

Output

Ghi ra một số nguyên duy nhất là phần dư sau khi chia số lộ trình phân biệt cho $10^9+7$.

Constraints

$2 \leq N \leq 2000$.
$1 \leq cs \leq N$.
$1 \leq cf \leq N$.
$c_s \neq c_f$.
Các lộ trình được xác định bằng thứ tự các ô mà con kangaroo nhảy đến.
Dữ liệu đảm bảo tồn tại ít nhất một lộ trình thỏa mãn các ràng buộc.
Con kangaroo có thể nhảy theo bất kỳ hướng nào khi nó xuất phát ở ô $cs$.

Scoring

Subtask $1$ ($6\%$ số điểm): $N \leq 8$.
Subtask $2$ ($36\%$ số điểm): $N \leq 40$.
Subtask $3$ ($51\%$ số điểm): $N \leq 200$.

Example

Test 1

Input

4 2 3

Output

Note

Con kangaroo xuất phát ở ô 2 và kết thúc ở ô 3. Hai lộ trình mà nó có thể nhảy qua là $2→1→4→3$ và $2→4→1→3$.

3. CEOI 2016 - Trick

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

Một nhóm du khách đến thăm lâu đài Bran bị Bá tước Dracula bắt giữ. Trong nhóm có một nhà ảo thuật. Ông thỏa thuận với Bá tước rằng nếu biểu diễn thành công một tiết mục, tất cả du khách sẽ được thả.

Tiết mục cần hai trợ lý. Sau khi bắt đầu, nhà ảo thuật không được trao đổi với hai trợ lý; hai trợ lý cũng không được trao đổi với nhau. Bá tước chuẩn bị bộ bài gồm các số từ $0$ đến $2N$, mỗi số xuất hiện đúng một lần, rồi giấu một lá bài. Trong $2N$ lá còn lại, Bá tước đưa $N$ lá cho trợ lý thứ nhất và những lá còn lại cho trợ lý thứ hai.

Mỗi trợ lý chọn hai lá trong tay mình và đưa chúng cho nhà ảo thuật theo một thứ tự xác định. Dựa vào bốn lá nhận được và không có thông tin nào khác, nhà ảo thuật phải đoán chính xác lá bài bị giấu.

Chương trình của bạn sẽ được chạy ba lần cho mỗi tệp kiểm thử: lần thứ nhất đóng vai trợ lý thứ nhất, lần thứ hai đóng vai trợ lý thứ hai, và lần thứ ba đóng vai nhà ảo thuật. Mỗi lần chạy xử lý toàn bộ các lượt trong tệp.

Dữ liệu vào

Dòng đầu chứa số nguyên $T$, là số lượt biểu diễn trong tệp. Dòng thứ hai chứa số nguyên $R \in \{1,2,3\}$, là vai trò của chương trình.

Với mỗi lượt $i$:

Dòng tiếp theo chứa số nguyên $N_i$.
Nếu $R=1$ hoặc $R=2$, dòng kế tiếp chứa $N_i$ số nguyên là các lá bài trong tay trợ lý tương ứng.
Nếu $R=3$, dòng kế tiếp chứa bốn số nguyên: hai lá trợ lý thứ nhất đã đưa ra, theo đúng thứ tự, rồi đến hai lá trợ lý thứ hai đã đưa ra, theo đúng thứ tự.

Dữ liệu ra

Với mỗi lượt, in một dòng:

Nếu $R=1$ hoặc $R=2$, in hai số nguyên phân biệt là hai lá được chọn. Cả hai lá phải thuộc bộ bài mà trợ lý nhận được.
Nếu $R=3$, in một số nguyên là lá bài bị giấu.

Ràng buộc

$1 \le T$.
$6 \le N_i \le 1\,234\,567$.
$N_1+N_2+\cdots+N_T \le 1\,234\,567$.

Phân nhóm

Có $29\%$ số điểm với $N_i=6$ trong mọi lượt.
Có thêm $19\%$ số điểm với $6 \le N_i \le 30$ và tổng các $N_i$ không vượt quá $123\,456$.
Có thêm $30\%$ số điểm với $6 \le N_i \le 500$, tổng các $N_i$ không vượt quá $123\,456$, và có nhiều nhất $10$ lượt có $N_i>50$.
$22\%$ số điểm còn lại không có ràng buộc bổ sung.

Ví dụ

Mỗi khối dưới đây là một lần chạy riêng. Ba lần chạy tương ứng với ba vai trò của chương trình.

:::sample

2
1
6
6 1 2 5 7 10
6
9 8 2 0 4 6

1 2
8 4

:::

:::sample

2
2
6
3 0 4 9 12 8
6
7 1 11 10 3 5

4 3
1 3

:::

:::sample

11
12

:::

Trong ví dụ, trợ lý thứ nhất và thứ hai lần lượt đưa ra hai cặp bài cho từng lượt. Nhà ảo thuật dùng bốn lá đó để đoán các lá bị giấu là $11$ và $12$.

Nguồn

CEOI 2016, ngày 1, bài 3.