CEOI 2021 - Ngày 2

Đề bài

Sau khi Ankica bắt được Branko, cậu từ chối mua báo cho cô và đòi chơi một trò khác vì cho rằng trò trước không công bằng. Ankica ngây thơ đề xuất một trò chơi khác với những viên đá, nhưng Branko vẫn nghi ngờ và quyết định thay đổi hoàn toàn luật chơi.

Trò chơi có \(N\) đống đá, đống thứ \(i\) ban đầu có \(a_i\) viên. Hai người lần lượt lấy một số viên đá khỏi một đống. Người lấy viên đá cuối cùng thắng.

Điểm đặc biệt là ở mỗi lượt, đối thủ sẽ chỉ định đống mà người chơi phải lấy đá.

Đánh số các lượt bằng các số nguyên tăng dần từ \(1\). Trò chơi diễn ra như sau:

• Ở lượt lẻ, Branko chỉ một đống đá chưa rỗng. Sau đó Ankica lấy ít nhất một và nhiều nhất là toàn bộ số đá khỏi đống ấy.
• Ở lượt chẵn, Ankica chỉ một đống đá chưa rỗng. Sau đó Branko lấy ít nhất một và nhiều nhất là toàn bộ số đá khỏi đống ấy.

Branko tìm được một số viên đá, chia chúng thành các đống và trò chơi bắt đầu. Là một game thủ chuyên nghiệp, Ankica nhanh chóng nhận ra cấu hình ban đầu là thế thắng cho cô: cô có thể thắng bất kể Branko chơi thế nào.

Bạn có thể thắng trò chơi nếu ở vào vị trí của Ankica không?

Tương tác

Đây là bài tương tác. Chương trình của bạn phải giao tiếp với chương trình của ban tổ chức đóng vai Branko. Chương trình của bạn đóng vai Ankica và phải bảo đảm cô thắng.

Trước tiên, chương trình đọc trạng thái ban đầu của trò chơi từ đầu vào chuẩn. Trạng thái ban đầu gồm hai dòng: dòng đầu chứa số nguyên \(N\); dòng thứ hai chứa \(N\) số nguyên dương \(a_1,a_2,\ldots,a_N\).

Sau đó trò chơi bắt đầu. Vì chương trình đóng vai Ankica, cách xử lý phụ thuộc vào lượt hiện tại là lẻ hay chẵn.

Trong một lượt lẻ:

1. Trước tiên, chương trình đọc một số nguyên \(k\). Nếu lúc này mọi đống đều rỗng, \(k=-1\); hãy kết thúc chương trình vì trò chơi đã kết thúc và bạn đã thua. Nếu không, \(1\le k\le N\) cho biết Ankica phải lấy đá từ đống thứ \(k\). Đống thứ \(k\) được bảo đảm chưa rỗng. Gọi số đá hiện có trong đống này là \(s_k\).
2. Sau đó, chương trình in một số nguyên \(x\) (\(1\le x\le s_k\)), là số viên đá Ankica muốn lấy khỏi đống thứ \(k\), rồi xả bộ đệm đầu ra.

Trong một lượt chẵn:

1. Trước tiên, chương trình in một số nguyên \(l\) rồi xả bộ đệm đầu ra. Nếu lúc này mọi đống đều rỗng, phải in \(l=-1\) và kết thúc chương trình vì trò chơi đã kết thúc và bạn đã thắng. Nếu không, \(1\le l\le N\) cho biết Ankica buộc Branko lấy đá từ đống thứ \(l\). Đống thứ \(l\) phải chưa rỗng. Gọi số đá hiện có trong đống này là \(s_l\).
2. Sau đó, chương trình đọc một số nguyên \(y\) (\(1\le y\le s_l\)), là số viên đá Branko đã lấy khỏi đống thứ \(l\).

Trạng thái ban đầu được bảo đảm là thế thắng cho Ankica, bất kể Branko chơi thế nào.

Bạn có thể tải từ hệ thống chấm một chương trình mẫu giao tiếp đúng với chương trình của ban tổ chức, bao gồm thao tác xả bộ đệm đầu ra, và giải được ví dụ tương tác thứ nhất.

Chấm điểm

Đặt \(M=\max(a_1,a_2,\ldots,a_N)\).

• Subtask 1 (12 điểm): \(1\le N,M\le7\).
• Subtask 2 (13 điểm): \(1\le N\le12\), \(1\le M\le500\).
• Subtask 3 (15 điểm): \(1\le N,M\le500\) và \(a_i=a_j\) với mọi \(1\le i,j\le N\).
• Subtask 4 (60 điểm): \(1\le N,M\le500\).

Ví dụ tương tác

Ví dụ 1

Ví dụ 2

Đề bài

Chú rùa Wilco muốn mua kẹo. Để làm vậy, cậu sẽ đến phố mua sắm Nakamise ở Tokyo.

Chú thỏ Tom là một người bạn lo rằng Wilco ăn quá nhiều đường. Để giảm số kẹo Wilco có thể mua, Tom sẽ mua bớt một số viên kẹo trước cậu.

Con phố có \(N\) địa điểm. Mỗi địa điểm là một cửa hàng hoặc một sân chơi trẻ em. Khoảng cách giữa hai địa điểm kề nhau là như nhau; có thể hình dung các địa điểm là \(N\) điểm cách đều trên một đường thẳng.

Mỗi cửa hàng có một số viên kẹo, có thể bằng không. Wilco đi từ địa điểm đầu tiên đến địa điểm cuối cùng và ghé qua tất cả các địa điểm theo thứ tự. Mỗi khi đến một cửa hàng, cậu mua toàn bộ số kẹo còn lại và bỏ vào túi.

Tom di chuyển nhanh gấp đôi Wilco. Khác với Wilco, Tom có thể di chuyển theo cả hai hướng. Để tránh bị nghi ngờ, Tom chỉ mang nhiều nhất một viên kẹo tại một thời điểm. Sau khi mua một viên kẹo, Tom phải mang nó cho đến khi trao cho trẻ em tại một sân chơi. Tom không được bỏ kẹo ở nơi nào khác, nhưng có thể bỏ kẹo tại sân chơi sau khi Wilco đã đến địa điểm cuối cùng. Mục tiêu của Tom là giảm nhỏ nhất số kẹo Wilco sẽ mua.

Cả hai bắt đầu ở địa điểm đầu tiên tại thời điểm \(0\). Việc mua và bỏ kẹo không mất thời gian. Nếu cả hai cùng ở một cửa hàng tại một thời điểm, Tom có thể mua kẹo trước Wilco, nhưng Tom vẫn chỉ được mua nhiều nhất một viên. Vì vậy, nếu địa điểm đầu tiên là cửa hàng, Tom có thể mua một viên trước Wilco ngay tại thời điểm \(0\).

Giả sử Tom di chuyển và mua kẹo một cách tối ưu, tổng cộng Wilco sẽ mua bao nhiêu viên kẹo?

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\).

Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\ldots,a_N\), mô tả \(N\) địa điểm trên phố. Nếu \(a_i=-1\), địa điểm thứ \(i\) là sân chơi. Nếu không, địa điểm đó là cửa hàng và \(a_i\) là số kẹo trong cửa hàng. Một cửa hàng có thể không có viên kẹo nào, tức là \(a_i\) có thể bằng \(0\).

Có ít nhất một địa điểm là sân chơi.

Dữ liệu ra

In số viên kẹo Wilco sẽ mua.

Chấm điểm

• Subtask 1 (8 điểm): \(1\le N\le20\), \(|a_i|\le1\).
• Subtask 2 (10 điểm): \(1\le N\le300\), \(|a_i|\le1\).
• Subtask 3 (30 điểm): \(1\le N\le300\), \(-1\le a_i\le10\,000\).
• Subtask 4 (25 điểm): \(1\le N\le5\,000\), \(-1\le a_i\le10\,000\).
• Subtask 5 (27 điểm): \(1\le N\le500\,000\), \(-1\le a_i\le10\,000\).

Ví dụ

5
-1 1 1 1 1

2

8
-1 1 0 0 -1 0 0 3

1

8
2 -1 2 -1 2 -1 2 -1

1

Đề bài

Trên ngọn núi Velebit xinh đẹp có \(N\) trạm trú ẩn. Có đúng \(N-1\) cặp trạm được nối bằng đường mòn sao cho có thể đi giữa mọi cặp trạm bằng các đường mòn này.

Nàng tiên Vila rất thích đi bộ đường dài. Cô mất đúng một ngày để đi qua một đường mòn nối hai trạm. Nhờ phép thuật, Vila có thể xuất hiện tại một trạm bất kỳ vào đầu ngày, rồi dành \(K-1\) ngày tiếp theo để đi bộ sao cho không đến cùng một trạm quá một lần. Như vậy, trong chuyến đi, Vila ghé đúng \(K\) trạm.

Vila khát nước khi đi bộ nên muốn một số trạm có giếng nước. Trong mọi chuyến đi có thể thực hiện, cô muốn ghé đúng một trạm có giếng.

Nhiệm vụ của bạn là xác định có thể chọn một tập con các trạm để đặt giếng thỏa mãn mong muốn đặc biệt của Vila hay không. Ngoài ra, hãy tính số tập con như vậy theo modulo \(10^9+7\).

Nói cách khác, cho một cây có \(N\) đỉnh và số nguyên dương \(K\), hãy xác định có tồn tại một tập con các đỉnh sao cho mọi đường đi chứa đúng \(K\) đỉnh đều chứa đúng một đỉnh thuộc tập con hay không, đồng thời đếm số tập con như vậy theo modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(2\le K\le N\)).

\(N-1\) dòng tiếp theo mô tả các đường mòn. Dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\) (\(1\le a_i,b_i\le N\)), cho biết có một đường mòn nối hai trạm \(a_i\) và \(b_i\).

Các đường mòn được bảo đảm tạo thành một cây.

Dữ liệu ra

Dòng đầu tiên in YES nếu tồn tại một tập con các trạm thỏa mãn điều kiện của Vila; ngược lại, in NO.

Dòng thứ hai in số tập con thỏa mãn điều kiện theo modulo \(10^9+7\).

Chấm điểm

• Subtask 1 (30 điểm): \(2\le K\le N\le200\).
• Subtask 2 (20 điểm): \(2\le K\le N\le10\,000\).
• Subtask 3 (20 điểm): \(2\le K\le N\le500\,000\).
• Subtask 4 (30 điểm): \(2\le K\le N\le1\,500\,000\).

Nếu chương trình in đúng dòng đầu tiên nhưng dòng thứ hai không đúng, testcase đó nhận \(60\%\) số điểm của subtask chứa nó.

Điểm của mỗi subtask bằng điểm nhỏ nhất trong các testcase thuộc subtask đó.

Ví dụ

4 2
3 4
3 1
2 3

YES
2

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

NO
0

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

YES
10