CEOI 2024 - Ngày 1

Đề bài

Ondra vừa được thăng chức Đại đô đốc Hải quân Cộng hòa Séc. Tuy nhiên, ngay khi anh bắt đầu nghĩ rằng mình đã có một công việc ổn định, chính phủ công bố cắt giảm ngân sách, trong đó có việc giải thể Hải quân.

Vì vậy, Ondra quyết định chứng minh cho chính phủ thấy Hải quân Séc quan trọng đến mức nào. Nhờ các gián điệp, anh biết về một trận hải chiến sắp diễn ra giữa bốn hạm đội lớn. Nếu có thể giành chiến thắng, chắc chắn anh sẽ tạo ra một màn thể hiện đủ sức thuyết phục.

Đáng tiếc, Hải quân Séc không có tàu chiến cũng chẳng có cảng biển. Nhưng nếu các gián điệp của Ondra chiếm được một số tàu, anh có thể vẫn còn cơ hội. Giá như anh biết được những con tàu nào sẽ sống sót sau trận chiến...

Một trận hải chiến diễn ra như sau. Ban đầu, tàu \(i\) nằm tại ô \((x_i,y_i)\), trong đó cả \(x_i\) và \(y_i\) đều là số chẵn. Mỗi tàu thuộc một trong bốn hạm đội: Bắc, Nam, Đông hoặc Tây. Sau đó, trận chiến diễn ra theo từng bước. Trong mỗi bước:

• Trước tiên, mọi tàu đồng thời di chuyển một ô theo hướng tương ứng với hạm đội của mình.
• Nếu lúc này có ít nhất hai tàu cùng nằm trên một ô, tất cả các tàu đó chìm và biến mất khỏi bản đồ.

Trận chiến kết thúc khi không còn vụ va chạm nào có thể xảy ra. Một tàu sống sót là tàu vẫn còn trên bản đồ sau khi trận chiến kết thúc.

Tàu di chuyển theo hướng của hạm đội, làm thay đổi tọa độ như sau:

• Bắc (N): giảm tọa độ \(y\) đi \(1\).
• Nam (S): tăng tọa độ \(y\) thêm \(1\).
• Đông (E): tăng tọa độ \(x\) thêm \(1\).
• Tây (W): giảm tọa độ \(x\) đi \(1\).

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa ba giá trị \(x_i\), \(y_i\) và \(d_i\), cách nhau bởi dấu cách. Hai số nguyên \(x_i\), \(y_i\) là tọa độ của tàu thứ \(i\). Ký tự \(d_i\) là một trong N, S, E, W, mô tả hướng của hạm đội chứa tàu thứ \(i\).

Không có hai tàu nào có cùng tọa độ ban đầu. Nói cách khác, với hai tàu \(i\) và \(j\) (\(i\ne j\)), ta có \(x_i\ne x_j\) hoặc \(y_i\ne y_j\).

Dữ liệu ra

Với mỗi tàu sống sót, in một dòng chứa số nguyên \(i\) (\(1\le i\le N\)), là chỉ số của tàu đó. Bạn có thể in chỉ số các tàu sống sót theo thứ tự bất kỳ.

Nếu không có tàu nào sống sót, dữ liệu ra phải rỗng.

Giới hạn

• \(2\le N\le 2\cdot 10^5\).
• \(0\le x_i,y_i\le 10^9\) với mọi \(1\le i\le N\); \(x_i\) và \(y_i\) đều là số chẵn.

Chấm điểm

• Subtask 1 (6 điểm): \(N=2\).
• Subtask 2 (12 điểm): \(N\le 100\) và \(x_i,y_i\le 100\) với mọi \(1\le i\le N\).
• Subtask 3 (8 điểm): \(N\le 100\) và \(x_i,y_i\le 10^5\) với mọi \(1\le i\le N\).
• Subtask 4 (11 điểm): \(N\le 200\).
• Subtask 5 (9 điểm): \(N\le 5\,000\).
• Subtask 6 (30 điểm): \(d_i\) là S hoặc E với mọi \(1\le i\le N\).
• Subtask 7 (24 điểm): Không có ràng buộc bổ sung.

Ví dụ

7
0 6 E
0 8 E
2 4 E
4 2 S
6 0 S
6 2 S
6 4 S

7

5
4 0 S
0 2 E
2 2 E
4 4 N
6 6 W

5
2

Đề bài

Trường của Adam đang trải qua một làn sóng dịch COVID mới. Để ngăn dịch tiếp tục lây lan, nhà trường quyết định xét nghiệm tất cả học sinh bằng bộ xét nghiệm kháng nguyên với mẫu nước bọt của các em.

Vì các giáo viên đã quên cách sử dụng những bộ xét nghiệm này từ lâu, Adam tình nguyện đến giúp. Cậu nhận được mẫu nước bọt của \(N\) học sinh; vì lý do riêng tư, cậu chỉ được biết các mã số từ \(0\) đến \(N-1\). Nhiệm vụ của cậu là xác định những mẫu dương tính.

Đáng tiếc, Adam nhận ra quá muộn rằng xét nghiệm lần lượt tất cả học sinh là một công việc vô cùng lâu và nhàm chán. Tuy nhiên, cậu nhận thấy mình có thể thực hiện việc xét nghiệm thông minh hơn. Nếu trộn một tập con các mẫu rồi xét nghiệm hỗn hợp đó, cậu sẽ biết tất cả các mẫu trong hỗn hợp đều âm tính hay có ít nhất một mẫu dương tính. Nhờ vậy, cậu có thể giảm số lần xét nghiệm cần thực hiện.

Mỗi mẫu có đủ nước bọt để Adam xét nghiệm bao nhiêu lần tùy ý. Hơn nữa, các phép xét nghiệm hoàn toàn chính xác, nên những lần xét nghiệm khác nhau trên cùng một mẫu không bao giờ cho kết quả khác nhau.

Trong các điều kiện đó, Adam muốn tối ưu hóa quy trình để sử dụng ít phép xét nghiệm nhất có thể. Tuy nhiên, cậu đang bận thực hiện xét nghiệm, nên việc tối ưu hóa được giao cho bạn.

Từ số liệu thống kê tại địa phương, Adam biết rằng xác suất để một mẫu bất kỳ dương tính là \(P\). Việc một mẫu dương tính hay âm tính không bị ảnh hưởng bởi trạng thái của bất kỳ mẫu nào khác. Có lẽ bạn có thể dùng thông tin này để tối ưu các phép xét nghiệm mà Adam thực hiện.

Giao tiếp

Đây là bài tương tác.

Chương trình của bạn sẽ được chạy trên một số bộ kiểm thử. Trong mỗi bộ kiểm thử, tức là trong một lần thực thi chương trình, bạn phải giải quyết \(T\) kịch bản khác nhau. Giá trị \(N\) và \(P\) giống nhau trong tất cả các kịch bản, nhưng những mẫu dương tính rất có thể sẽ khác nhau giữa các kịch bản.

Bạn có thể tự cài đặt giao thức bắt buộc hoặc sử dụng mã mẫu. Mã mẫu nằm trong tệp đính kèm template.cpp trên CMS.

Giao thức

Trước tiên, chương trình phải đọc một dòng từ đầu vào chuẩn chứa một số nguyên \(N\), một số thực \(P\) và một số nguyên \(T\), cách nhau bởi dấu cách, lần lượt là số học sinh, xác suất một mẫu dương tính và số kịch bản.

Sau đó, chương trình có thể ghi các truy vấn ra đầu ra chuẩn. Mỗi truy vấn là một dòng chứa Q, một dấu cách và một xâu \(s\) độ dài \(N\). Ký tự \(s_i\) là 1 nếu Adam cần thêm mẫu của học sinh thứ \(i\) vào phép xét nghiệm, và là 0 nếu không. Sau khi in dòng này, chương trình phải đẩy dữ liệu đầu ra, rồi đọc một dòng chứa một ký tự: P nếu có ít nhất một mẫu trong nhóm được xét nghiệm là dương tính, và N nếu không có mẫu nào dương tính.

Chương trình cũng có thể đưa ra câu trả lời bằng cách ghi một dòng ra đầu ra chuẩn gồm A, một dấu cách và một xâu \(s\) độ dài \(N\). Ký tự \(s_i\) là 1 nếu mẫu của học sinh thứ \(i\) dương tính, và là 0 nếu mẫu đó âm tính. Sau khi in dòng này, chương trình phải đẩy dữ liệu đầu ra, rồi đọc một dòng chứa một ký tự.

Nếu dòng nhận được chứa C, câu trả lời của bạn là đúng. Khi ấy, chương trình có thể bắt đầu truy vấn cho kịch bản tiếp theo, hoặc kết thúc nếu đây là câu trả lời thứ \(T\).

Nếu dòng nhận được chứa W, câu trả lời của bạn sai. Khi ấy, chương trình phải kết thúc ngay lập tức.

Việc kết thúc sau khi nhận W là cần thiết để CMS cung cấp phản hồi đúng. Nếu chương trình tiếp tục chạy, nó có thể gặp lỗi hoặc nhận một kết quả chấm không thành công khác.

Mã mẫu

Nếu sử dụng phần cài đặt giao thức trong template.cpp, bạn cần cài đặt hàm:

std::vector<bool> find_positive()

Hàm này được gọi đúng một lần cho mỗi kịch bản. Hàm phải trả về một vector Boolean độ dài \(N\), trong đó phần tử thứ \(i\) là true khi và chỉ khi mẫu của học sinh thứ \(i\) dương tính.

Để thực hiện việc này, bạn có thể sử dụng hàm:

bool test_students(std::vector<bool> mask)

Hàm này thực hiện một phép xét nghiệm trên một tập con các mẫu. Đối số duy nhất là một vector Boolean độ dài \(N\), trong đó phần tử thứ \(i\) là true nếu cần thêm mẫu thứ \(i\) vào hỗn hợp. Hàm trả về true khi và chỉ khi có ít nhất một mẫu trong hỗn hợp dương tính.

Bạn cũng có thể sử dụng các biến toàn cục N và P, chứa các giá trị \(N\) và \(P\) trong đề bài. Bạn có thể thực hiện mọi thao tác khởi tạo cần thiết trong hàm main sau lời gọi scanf đầu tiên.

Bộ dữ liệu

Trình chấm của bài không thích nghi, nghĩa là trạng thái dương tính của từng mẫu được xác định trước khi chương trình của bạn chạy. Hơn nữa, mỗi mẫu được xác định là dương tính một cách độc lập với xác suất \(P\), bằng một bộ sinh số ngẫu nhiên công bằng.

Chấm điểm

Có hai subtask.

• Subtask 1 (10 điểm): \(N=1\,000\), \(T=1\) và \(0\le P\le 1\). Lời giải được chấp nhận nếu trả lời đúng và sử dụng không quá \(2\cdot N\) truy vấn trên mọi bộ kiểm thử.
• Subtask 2 (90 điểm): \(N=1\,000\), \(T=300\) và \(0.001\le P\le 0.2\). Subtask này được chấm điểm thành phần theo mô tả dưới đây.

Nếu câu trả lời ở bất kỳ kịch bản nào sai, bạn nhận \(0\) điểm. Nếu tất cả câu trả lời đều đúng, điểm của một bộ kiểm thử được xác định dựa trên số truy vấn trung bình trên mỗi kịch bản; nhìn chung, số truy vấn càng ít thì điểm càng cao.

Gọi \(Q\) là số truy vấn trung bình mà chương trình sử dụng trên tất cả các kịch bản, được làm tròn xuống đến một chữ số sau dấu thập phân. Với mỗi bộ kiểm thử, ban tổ chức đã tính một giá trị \(F\) theo bảng bên dưới. Điểm trên bộ kiểm thử đó được tính như sau:

• Nếu \(Q>10\cdot F\), bạn nhận \(0\) điểm và kết quả là Wrong Answer.
• Nếu \(F<Q\le 10\cdot F\), số điểm là

• Nếu \(Q\le F\), bạn nhận đủ \(90\) điểm.

Lời giải được chấm trên nhiều bộ kiểm thử với các giá trị \(P\) khác nhau. Tổng điểm bạn nhận được là điểm nhỏ nhất trong tất cả các bộ kiểm thử, tức là trên tất cả các xác suất \(P\).

Các bộ kiểm thử như sau:

Hệ thống chấm sẽ cung cấp phản hồi cho từng bộ kiểm thử. Với mỗi bộ kiểm thử mà lời giải nhận được số điểm khác \(0\), phản hồi sẽ bao gồm giá trị \(Q\) của lời giải trên bộ đó.

Ví dụ tương tác

Dưới đây là một ví dụ tương tác với trình chấm. Lưu ý rằng các giá trị \(N\) và \(T\) trong ví dụ không thể xuất hiện trong bất kỳ subtask nào. Đừng quên đẩy dữ liệu đầu ra sau mỗi dòng.

Chương trình đã giải đúng kịch bản đầu tiên nhưng sai ở kịch bản thứ hai, vì câu trả lời đúng là 1100010010. Chương trình không thể biết câu trả lời này vì không thực hiện truy vấn nào. Kể cả khi vẫn còn một kịch bản khác, chương trình cũng phải kết thúc ngay lập tức.

Đề bài

Robert đang tham dự CEOI 2024. Cậu gần như đã hoàn thành lời giải cho bài khó nhất trong ngày, và còn tin chắc lời giải sẽ đạt \(100\) điểm! Chỉ còn một vấn đề nhỏ: cậu đã gõ sai một chỗ. Tệ hơn nữa, con chuột máy tính yêu thích mà cậu dùng từ năm 2008 dường như cuối cùng cũng đã hỏng và hoàn toàn không phản hồi. Vì vậy, cậu phải dùng các phím mũi tên trên bàn phím để di chuyển đến chỗ gõ sai.

Chương trình của Robert có \(N\) dòng với độ dài lần lượt là \(l_1,l_2,\ldots,l_N\). Robert luôn kết thúc chương trình bằng một dòng rỗng, do đó \(l_N=0\).

Con trỏ có thể nằm giữa hai ký tự, ở đầu dòng hoặc ở cuối dòng. Vì vậy, dòng \(i\) có \(l_i+1\) vị trí con trỏ, gọi là các cột, được đánh số từ \(1\) đến \(l_i+1\). Ví dụ, con trỏ ở dòng \(2\), cột \(6\) trông như sau:

![Con trỏ ở vị trí (2, 6)https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_2d60f30a.svg

Robert muốn di chuyển con trỏ từ dòng \(s_l\), cột \(s_c\) đến dòng \(e_l\), cột \(e_c\). Cậu muốn biết số lần nhấn phím ít nhất cần thiết.

Hai phím mũi tên ngang hoạt động khá đơn giản. Nhấn phím trái sẽ đưa con trỏ sang cột trước đó, trừ khi con trỏ đang ở đầu một dòng; khi ấy, con trỏ sẽ chuyển đến cuối dòng trước. Tương tự, nhấn phím phải sẽ đưa con trỏ sang cột tiếp theo, hoặc đến đầu dòng kế tiếp nếu con trỏ đang ở cuối dòng.

Ví dụ, hai lần nhấn phím trái có thể diễn ra như sau:

![Con trỏ di chuyển sau hai lần nhấn phím tráihttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_8cd5e304.svg

Và hai lần nhấn phím phải có thể diễn ra như sau:

![Con trỏ di chuyển sau hai lần nhấn phím phảihttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_176db26f.svg

Nhấn phím trái tại vị trí đầu tiên của tệp hoặc nhấn phím phải tại vị trí cuối cùng của tệp sẽ không có tác dụng.

Hai phím mũi tên dọc phức tạp hơn một chút. Nhấn phím lên sẽ đưa con trỏ đến dòng trước và nhấn phím xuống sẽ đưa con trỏ đến dòng sau mà không thay đổi số cột. Tuy nhiên, nếu cột đó nằm quá cuối dòng mới, con trỏ sẽ chuyển đến cuối dòng ấy.

Ví dụ, các lần nhấn phím lên có thể diễn ra như sau:

![Con trỏ di chuyển sau hai lần nhấn phím lênhttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_87944286.svg

Và các lần nhấn phím xuống có thể diễn ra như sau:

![Con trỏ di chuyển sau hai lần nhấn phím xuốnghttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_707401b0.svg

Nếu nhấn phím lên hoặc xuống khiến con trỏ phải chuyển đến một dòng không tồn tại, con trỏ sẽ không di chuyển.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\), là số dòng trong chương trình của Robert.

Dòng thứ hai chứa hai số nguyên \(s_l\) và \(s_c\), cách nhau bởi dấu cách, là vị trí ban đầu của con trỏ.

Dòng thứ ba chứa hai số nguyên \(e_l\) và \(e_c\), là vị trí đích của con trỏ.

Dòng thứ tư chứa \(N\) số nguyên \(l_1,l_2,\ldots,l_N\), cách nhau bởi dấu cách, là độ dài của từng dòng.

Dữ liệu ra

In một dòng chứa một số nguyên, là số lần nhấn phím ít nhất để di chuyển con trỏ từ \((s_l,s_c)\) đến \((e_l,e_c)\).

Giới hạn

• \(1\le N\le 10^6\).
• \(0\le l_i\le 10^9\) với mọi \(1\le i\le N\).
• \(l_N=0\).
• \(1\le s_l,e_l\le N\).
• \(1\le s_c\le l_{s_l}+1\).
• \(1\le e_c\le l_{e_l}+1\).

Chấm điểm

• Subtask 1 (5 điểm): \(N\le 2\).
• Subtask 2 (14 điểm): \(N\le 1\,000\) và \(l_i\le 5\,000\) với mọi \(1\le i\le N\).
• Subtask 3 (26 điểm): \(N\le 1\,000\).
• Subtask 4 (11 điểm): \(l_i=l_j\) với mọi \(1\le i,j\le N-1\).
• Subtask 5 (44 điểm): Không có ràng buộc bổ sung.

Ví dụ

5
3 1
2 8
7 10 9 9 0

3

5
1 20
3 25
25 10 40 35 0

16