CEOI 2021 - Ngày 1

Đề bài

Zoran là người trông coi vườn thú Zagreb. Hiện anh đang nghiên cứu khoa học về mối quan hệ giữa mức độ hài lòng của khách tham quan và cách các loài động vật được bố trí trong vườn thú.

Hành trình của một khách tham quan qua toàn bộ vườn thú có thể được xem là một dãy gồm \(N\) khu nuôi, mỗi khu chứa một loài động vật nhất định. Ban đầu, khu nuôi thứ \(i\) chứa động vật thuộc loài \(a_i\), và khách tham quan sẽ quan sát các khu nuôi theo thứ tự.

Zoran bắt đầu thử nghiệm những cách thay đổi thứ tự bố trí động vật. Sau đó, anh đặt ra các câu hỏi về mức độ hài lòng của khách trong chuyến tham quan. Hóa ra khách hài lòng nhất khi tổng độ đa dạng của hành trình nhỏ nhất có thể.

Độ đa dạng của một dãy khu nuôi là số loài động vật khác nhau có thể quan sát trong các khu nuôi đó. Tổng độ đa dạng của một dãy khu nuôi là tổng độ đa dạng của tất cả các dãy con liên tiếp của nó.

Ví dụ, độ đa dạng của dãy \((1,1,2)\) là \(2\) vì dãy này có hai loài khác nhau. Tổng độ đa dạng của dãy là \(8\), vì các dãy con liên tiếp \((1)\), \((1)\), \((2)\), \((1,1)\), \((1,2)\) và \((1,1,2)\) lần lượt có độ đa dạng \(1,1,1,1,2,2\).

Zoran biết loài động vật hiện đang ở mỗi khu nuôi. Trước khi sắp xếp lại vườn thú, anh muốn bạn trả lời \(Q\) truy vấn độc lập. Trong truy vấn thứ \(i\), anh muốn biết tổng độ đa dạng nhỏ nhất có thể của dãy con liên tiếp từ khu nuôi \(l_i\) đến khu nuôi \(r_i\), nếu được phép sắp xếp lại các động vật đang sống trong những khu nuôi này.

Dữ liệu vào

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

Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\ldots,a_N\), trong đó \(a_i\) là loài động vật đang ở khu nuôi thứ \(i\).

Mỗi dòng trong \(Q\) dòng tiếp theo chứa hai số nguyên \(l_i\) và \(r_i\) (\(1\le l_i\le r_i\le N\)), mô tả một truy vấn.

Các truy vấn hoàn toàn độc lập với nhau. Nói cách khác, khi trả lời mỗi truy vấn, hãy giả sử khu nuôi thứ \(i\) ban đầu vẫn chứa loài \(a_i\).

Dữ liệu ra

Dòng thứ \(i\) chứa một số nguyên duy nhất là đáp án của truy vấn thứ \(i\).

Chấm điểm

• Subtask 1 (4 điểm): \(1\le N\le11\), \(1\le a_i\le300\,000\), \(Q=1\), \(l_1=1\), \(r_1=N\).
• Subtask 2 (10 điểm): \(1\le N\le300\,000\), \(1\le a_i\le11\), \(Q=1\), \(l_1=1\), \(r_1=N\).
• Subtask 3 (8 điểm): \(1\le N\le300\,000\), \(1\le a_i\le23\), \(Q=1\), \(l_1=1\), \(r_1=N\).
• Subtask 4 (16 điểm): \(1\le N\le300\,000\), \(1\le a_i\le1\,000\), \(Q=1\), \(l_1=1\), \(r_1=N\).
• Subtask 5 (26 điểm): \(1\le N\le300\,000\), \(1\le a_i\le300\,000\), \(Q=1\), \(l_1=1\), \(r_1=N\).
• Subtask 6 (36 điểm): \(1\le N\le300\,000\), \(1\le a_i\le300\,000\), \(1\le Q\le50\,000\).

Ví dụ

3 1
1 2 3
1 3

10

4 2
1 1 1 1
1 2
2 4

3
6

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

16
8
4

Đề bài

Luka tình cờ tìm thấy một bảng hình chữ nhật có chiều cao \(H\) và chiều rộng \(W\), được chia thành \(W\times H\) ô vuông đơn vị. Cậu nhanh chóng nhận ra rằng có đúng \(K\) ô vuông bị khuyết.

Thật trùng hợp, Luka có vô hạn miếng ghép triomino hình chữ L. Liệu có thể lát kín bảng đã cho bằng những miếng ghép này không?

![Một miếng triomino hình chữ Lhttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_396c80e2.png

Bảng được xem là lát đúng nếu mỗi ô vuông còn lại của bảng được phủ bởi một ô của triomino. Các triomino không được phủ lên ô bị khuyết, không được chồng lên nhau và không được nhô ra ngoài bảng. Các triomino có thể được xoay tùy ý theo bội số của \(90\) độ.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(W\), \(H\) và \(K\) (\(0\le K\le W\cdot H\)).

Dòng thứ \(i\) trong \(K\) dòng tiếp theo chứa hai số nguyên \(x_i\) và \(y_i\) (\(1\le x_i\le W\), \(1\le y_i\le H\)), là tọa độ của ô bị khuyết thứ \(i\). Các ô bị khuyết đôi một khác nhau.

Dữ liệu ra

Nếu Luka có thể lát kín bảng, in YES trên một dòng. Ngược lại, in NO trên một dòng.

Chấm điểm

• Subtask 1 (10 điểm): \(2\le W\le13\), \(2\le H\le1\,000\), \(K\le250\).
• Subtask 2 (7 điểm): \(2\le W\le13\), \(2\le H\le10^9\), \(K=0\).
• Subtask 3 (11 điểm): \(2\le W\le3\), \(2\le H\le10^9\), \(K\le250\).
• Subtask 4 (17 điểm): \(4\le W\le6\), \(2\le H\le10^9\), \(K\le250\).
• Subtask 5 (35 điểm): \(7\le W\le13\), \(2\le H\le10^9\), \(K\le250\).
• Subtask 6 (20 điểm): \(2\le W\le13\), \(2\le H\le10^9\), \(K\le250\).

Ví dụ

4 3 3
1 1
1 3
4 3

YES

5 2 4
1 2
2 1
5 1
5 2

NO

2 3 0

YES

Đề bài

“Bắt được tớ, bắt được tớ, tớ sẽ mua báo cho cậu!” là một câu hát trò chơi phổ biến của trẻ em Croatia.

Ankica và Branko đang chơi đuổi bắt trên một đồ thị vô hướng liên thông. Branko di chuyển trên đồ thị, còn Ankica cố bắt cậu. Trò chơi diễn ra theo lượt; mỗi lượt gồm các bước sau:

• Ankica đoán vị trí của Branko, cụ thể là đoán rằng Branko đang ở một đỉnh nào đó. Nếu đoán đúng, Branko bị bắt và trò chơi kết thúc. Nếu đoán sai:
• Branko đi qua một cạnh kề với vị trí hiện tại, tức là chuyển sang một đỉnh kề. Branko không được đứng yên tại vị trí hiện tại.

Cho một đồ thị, hãy xác định Ankica có một chiến lược hữu hạn luôn bắt được Branko hay không, bất kể Branko chơi như thế nào và bắt đầu ở đâu.

Một cách hình thức, chiến lược của Ankica được biểu diễn bằng mảng \(A=(a_1,a_2,\ldots,a_k)\), trong đó \(a_i\) là đỉnh Ankica đoán ở lượt thứ \(i\).

Tương tự, các vị trí của Branko được biểu diễn bằng mảng \(B=(b_1,b_2,\ldots,b_k)\), trong đó \(b_i\) là đỉnh Branko đang đứng trước lượt thứ \(i\). Với mỗi hai phần tử liên tiếp \(b_i\) và \(b_{i+1}\) (\(1\le i<k\)), đồ thị phải có một cạnh nối hai đỉnh đó. Mảng \(A\) không chịu ràng buộc tương tự.

Chiến lược của Ankica được gọi là thành công, tức là bắt được Branko trong không quá \(k\) lượt, nếu với mọi mảng \(B\) hợp lệ có độ dài \(k\), tồn tại một chỉ số \(i\) (\(1\le i\le k\)) sao cho \(a_i=b_i\).

Nếu có chiến lược thành công, hãy tìm một chiến lược làm nhỏ nhất số lượt \(k\).

Bạn vẫn có thể nhận một phần điểm nếu đưa ra chiến lược thành công nhưng không tối ưu, tức là \(k\) chưa nhỏ nhất. Xem mục Chấm điểm để biết chi tiết.

Dữ liệu vào

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

lần lượt là số đỉnh và số cạnh của đồ thị. Các đỉnh được đánh số từ \(1\) đến \(N\).

Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa hai số nguyên \(u_i\) và \(v_i\) (\(1\le u_i,v_i\le N\), \(u_i\ne v_i\)), cho biết có một cạnh vô hướng nối \(u_i\) và \(v_i\).

Không cạnh nào xuất hiện nhiều hơn một lần trong dữ liệu vào và đồ thị luôn liên thông.

Dữ liệu ra

Nếu không tồn tại chiến lược thành công cho Ankica, chỉ in NO trên dòng đầu tiên rồi kết thúc chương trình.

Ngược lại, in YES trên dòng đầu tiên. Dòng thứ hai chứa số lượt \(k\). Dòng thứ ba chứa \(k\) số \(a_1,a_2,\ldots,a_k\) mô tả chiến lược.

Chấm điểm

• Subtask 1 (12 điểm): \(1\le N\le20\).
• Subtask 2 (8 điểm): \(1\le N\le1\,000\), \(M=N-1\), và với mọi \(u=1,\ldots,N-1\), đỉnh \(u\) được nối với đỉnh \(u+1\).
• Subtask 3 (80 điểm): \(1\le N\le1\,000\).

Trên một testcase, nếu chương trình in đúng YES ở dòng đầu tiên nhưng không đưa ra chiến lược thành công, testcase đó nhận \(50\%\) số điểm của subtask chứa nó.

Nếu chương trình in đúng YES ở dòng đầu tiên và đưa ra một chiến lược thành công nhưng không tối ưu, testcase đó nhận \(75\%\) số điểm của subtask chứa nó. Để nhận số điểm này, chiến lược được in phải có không quá \(5N\) lượt. Có thể chứng minh rằng số lượt của chiến lược tối ưu không vượt quá \(5N\).

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

Ví dụ

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

YES
2
1 1

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

NO