IOI 2016 - Ngày 2

Tô màu bằng số là một trò chơi đố nổi tiếng. Trong phiên bản một chiều của trò chơi, có một hàng gồm \(n\) ô, đánh số từ \(0\) đến \(n-1\) từ trái sang phải. Mỗi ô phải được tô đen hoặc trắng. Ký tự X biểu thị ô đen và _ biểu thị ô trắng.

Người chơi được cho một dãy gợi ý \(c=[c_0,\ldots,c_{k-1}]\) gồm \(k\) số nguyên dương. Các ô đen phải tạo thành đúng \(k\) khối liên tiếp, ngăn cách nhau bởi ít nhất một ô trắng. Khối thứ \(i\) từ trái sang, đánh số từ \(0\), phải có đúng \(c_i\) ô đen.

Ví dụ, với \(n=10\) và \(c=[3,4]\), cách tô _XXX__XXXX hợp lệ. Cách tô XXXX_XXX__ không hợp lệ vì hai khối có độ dài sai thứ tự. Cách tô __XXXXXXX_ cũng không hợp lệ vì chỉ có một khối đen thay vì hai khối tách biệt.

Bạn được cho một phần lời giải: ngoài \(n\) và \(c\), màu của một số ô đã được xác định là đen hoặc trắng. Một lời giải đúng phải thỏa mãn các gợi ý và giữ nguyên màu đã biết. Hãy xác định những ô đen trong mọi lời giải đúng, những ô trắng trong mọi lời giải đúng, và những ô có thể nhận cả hai màu ở các lời giải đúng khác nhau.

Dữ liệu luôn có ít nhất một lời giải đúng.

Chi tiết cài đặt

Trong C++, cài đặt hàm khai báo trong paint.h:

std::string solve_puzzle(std::string s, std::vector<int> c);

Trong Java, cài đặt phương thức sau trong lớp paint:

public String solve_puzzle(String s, int[] c)

Trong C, giao diện là:

void solve_puzzle(int n, char* s, int k, int* c, char* result);

• s: xâu độ dài \(n\). Với \(0 \le i < n\), s[i] là X nếu ô \(i\) phải đen, _ nếu phải trắng, và . nếu chưa có thông tin.
• c: mảng độ dài \(k\) chứa các gợi ý theo thứ tự từ trái sang phải.
• Với C++ và Java, trả về xâu độ dài \(n\). Ký tự thứ \(i\) phải là X nếu ô đó đen trong mọi lời giải đúng, _ nếu trắng trong mọi lời giải đúng, hoặc ? nếu có cả lời giải tô đen và lời giải tô trắng ô đó.
• Với C, n là độ dài s, k là số gợi ý. Ghi \(n\) ký tự của đáp án vào mảng result được cấp sẵn thay vì trả về xâu.

Mã ASCII của X, _, ., ? lần lượt là \(88,95,46,63\). Ký tự chưa biết ở đầu vào là ., còn ký tự chưa xác định được ở đầu ra là ?.

Nộp phần cài đặt hàm, không viết hàm main; sử dụng các tệp mẫu của ngôn ngữ tương ứng trong gói đính kèm. Khi nộp bằng C trên LQDOJ, dùng #include "paint.h" thay cho #include "paint_c.h" trong tệp mẫu; header dùng chung cung cấp đúng giao diện C ở trên.

Ràng buộc

• \(1 \le n \le 200\,000\).
• \(1 \le k \le n\) và \(1 \le c_i \le n\) với mọi \(0 \le i < k\).
• s chỉ gồm các ký tự X, _, ..
• Có ít nhất một lời giải đúng phù hợp với s và c.

Phân nhóm

Mỗi subtask được tính trọn số điểm khi tất cả các test của subtask đó đều đúng; nếu không, subtask được \(0\) điểm. Các ràng buộc chung luôn áp dụng.

Ví dụ

Lời gọi thứ nhất:

solve_puzzle("..........", [3, 4])

Có đúng sáu cách tô hợp lệ:

XXX_XXXX__
XXX__XXXX_
XXX___XXXX
_XXX_XXXX_
_XXX__XXXX
__XXX_XXXX

Các ô \(2,6,7\) luôn đen. Mỗi ô còn lại đều có thể đen hoặc trắng tùy lời giải, nên đáp án là ??X???XX??.

Lời gọi thứ hai:

solve_puzzle("........", [3, 4])

Chỉ có một cách tô hợp lệ, nên đáp án là XXX_XXXX.

Lời gọi thứ ba:

solve_puzzle("..._._....", [3])

Không thể đặt khối ba ô đen vào giữa hai ô trắng \(3\) và \(5\), nên ô \(4\) cũng phải trắng. Đáp án là ???___????.

Lời gọi thứ tư:

solve_puzzle(".X........", [3])

Chỉ có hai cách tô hợp lệ là XXX_______ và _XXX______. Do đó đáp án là ?XX?______.

Trình chấm mẫu

Trình chấm mẫu đọc dòng đầu chứa xâu s; dòng tiếp theo chứa \(k\), rồi đến \(k\) số \(c_0,\ldots,c_{k-1}\). Chương trình in xâu kết quả của solve_puzzle trên một dòng.

..........
2 3 4

??X???XX??

........
2 3 4

XXX_XXXX

..._._....
1 3

???___????

.X........
1 3

?XX?______

Nguồn

IOI 2016, ngày thi thứ hai, bài Paint By Numbers. Đề tiếng Việt và gói tệp dành cho thí sinh được đính kèm.

Ilshat là kỹ sư phần mềm nghiên cứu các cấu trúc dữ liệu hiệu quả. Anh thiết kế một cấu trúc dữ liệu lưu một tập các số nguyên không âm \(n\) bit, trong đó \(n=2^b\) với một số nguyên không âm \(b\).

Ban đầu tập rỗng. Chương trình sử dụng cấu trúc dữ liệu phải tuân theo trình tự:

1. Thêm các số nguyên \(n\) bit vào tập bằng add_element(x), mỗi lần một số. Thêm lại một phần tử đã có không làm thay đổi tập.
2. Sau khi thêm phần tử cuối cùng, gọi compile_set() đúng một lần.
3. Sau đó, có thể gọi check_element(x) nhiều lần để kiểm tra phần tử \(x\) có thuộc tập hay không.

Ilshat đã mắc lỗi trong compile_set(): hàm sắp xếp lại các bit của mọi phần tử theo cùng một hoán vị chưa biết. Bạn cần xác định hoán vị đó.

Gọi \(p=[p_0,\ldots,p_{n-1}]\) là một hoán vị của các số từ \(0\) đến \(n-1\). Một phần tử có biểu diễn nhị phân \(a_0,\ldots,a_{n-1}\), với \(a_0\) là bit có trọng số lớn nhất, sẽ bị thay bằng phần tử có các bit

Cùng một hoán vị \(p\) được dùng cho mọi phần tử. Hoán vị có thể bất kỳ, kể cả hoán vị đồng nhất \(p_i=i\) với mọi \(i\). Trình chấm cố định \(p\) trước khi gọi hàm của bạn.

Ví dụ, với \(n=4\), \(p=[2,1,3,0]\), nếu tập chứa 0000, 1100, 0111, thì sau compile_set() tập sẽ chứa 0000, 0101, 1110.

Bạn cần chọn các phần tử để thêm vào tập, gọi compile_set() đúng một lần, kiểm tra một số phần tử trong tập đã biến đổi, rồi dùng thông tin thu được để xác định và trả về \(p\). Có thể gọi add_element nhiều nhất \(w\) lần và check_element nhiều nhất \(r\) lần. Việc thêm một phần tử đã có vẫn được tính là một lần gọi.

Chi tiết cài đặt

Trong C++, cài đặt hàm khai báo trong messy.h:

std::vector<int> restore_permutation(int n, int w, int r);

Trong Java, cài đặt phương thức sau trong lớp messy:

public int[] restore_permutation(int n, int w, int r)

Trong C, giao diện là:

void restore_permutation(int n, int w, int r, int* result);

• n: số bit của mỗi phần tử, đồng thời là độ dài hoán vị.
• w: số lần tối đa được gọi add_element.
• r: số lần tối đa được gọi check_element.
• Với C++ và Java, trả về mảng độ dài \(n\) chứa đúng hoán vị \(p\) theo thứ tự \(p_0,\ldots,p_{n-1}\).
• Với C, ghi \(p_i\) vào result[i] của mảng đã được cấp sẵn, với mọi \(0 \le i < n\).

Nộp phần cài đặt hàm, không viết hàm main; sử dụng các tệp mẫu của ngôn ngữ tương ứng trong gói đính kèm. Khi nộp bằng C trên LQDOJ, dùng #include "messy.h" thay cho #include "messy_c.h" trong tệp mẫu; header dùng chung cung cấp đúng giao diện C ở trên.

Các hàm thư viện

Thư viện C++ cung cấp các hàm sau trong messy.h:

void add_element(std::string x);
bool check_element(std::string x);
void compile_set();

Thư viện C cung cấp:

void add_element(char* x);
int check_element(char* x);
void compile_set();

Trong Java, gọi các phương thức tĩnh của lớp grader:

public static void add_element(String x)
public static boolean check_element(String x)
public static void compile_set()

• add_element(x): thêm phần tử có biểu diễn nhị phân x vào tập. Chỉ được gọi trước compile_set().
• compile_set(): áp dụng phép hoán vị bit cho toàn bộ tập. Phải gọi đúng một lần. Không được thêm phần tử sau lời gọi này, và không được kiểm tra phần tử trước lời gọi này.
• check_element(x): trả về true nếu phần tử được biểu diễn bởi x thuộc tập sau khi biến đổi, và false nếu không. Trong C, các giá trị tương ứng là \(1\) và \(0\).

Mỗi xâu x truyền cho add_element hoặc check_element phải có đúng \(n\) ký tự, chỉ gồm 0 và 1. Ký tự đầu tiên biểu diễn bit có trọng số lớn nhất. Vi phạm giới hạn số lời gọi, thứ tự thao tác hoặc định dạng xâu sẽ bị chấm Wrong Answer.

Ràng buộc

• \(n\) là lũy thừa của \(2\); các giá trị cụ thể của \(n,w,r\) được cho trong bảng subtasks.
• \(p\) là hoán vị của \(0,1,\ldots,n-1\), được cố định trước lời gọi restore_permutation.
• compile_set() phải được gọi đúng một lần, kể cả khi đã suy ra hoán vị.

Phân nhóm

Mỗi subtask được tính trọn số điểm khi tất cả các test của subtask đó đều đúng; nếu không, subtask được \(0\) điểm.

Ví dụ

Trình chấm gọi:

restore_permutation(4, 16, 16)

Chương trình được thêm phần tử nhiều nhất \(16\) lần và kiểm tra nhiều nhất \(16\) lần. Một chuỗi thao tác có thể là:

add_element("0001")
add_element("0011")
add_element("0100")
compile_set()
check_element("0001") -> false
check_element("0010") -> true
check_element("0100") -> true
check_element("1000") -> false
check_element("0011") -> false
check_element("0101") -> false
check_element("1001") -> false
check_element("0110") -> false
check_element("1010") -> true
check_element("1100") -> false

Chỉ có một hoán vị phù hợp với các kết quả kiểm tra này: \(p=[2,1,3,0]\). Vì vậy, restore_permutation phải trả về [2, 1, 3, 0].

Trình chấm mẫu

Trình chấm mẫu đọc dòng đầu chứa \(n,w,r\) và dòng tiếp theo chứa \(n\) số \(p_0,\ldots,p_{n-1}\). Các số này mô tả hoán vị dùng để mô phỏng thư viện; hàm của bạn nhận \(n,w,r\) và sử dụng các lời gọi thư viện để tìm hoán vị.

Nếu hàm trả về mảng độ dài \(n\), trình chấm mẫu C++ in các phần tử của mảng đó trên một dòng. Nếu trả về sai độ dài hoặc vi phạm quy tắc gọi thư viện, trình chấm mẫu in WA. Trình chấm mẫu C++ không tự so sánh từng phần tử của mảng trả về với \(p\); bạn cần kiểm tra kết quả khi thử chương trình.

4 16 16
2 1 3 0

2 1 3 0

Nguồn

IOI 2016, ngày thi thứ hai, bài Unscrambling a Messy Bug. Đề tiếng Việt và gói tệp dành cho thí sinh được đính kèm.

Vệ tinh của chúng ta vừa phát hiện một nền văn minh trên một hành tinh xa xôi. Một bức ảnh có độ phân giải thấp chụp một vùng hình vuông trên hành tinh cho thấy nhiều dấu hiệu của sự sống văn minh. Các chuyên gia đã xác định \(n\) điểm quan tâm, đánh số từ \(0\) đến \(n-1\). Chúng ta muốn chụp các ảnh có độ phân giải cao chứa tất cả các điểm này.

Vùng ảnh được chia thành một lưới \(m \times m\) ô vuông đơn vị. Các hàng được đánh số từ \(0\) đến \(m-1\) từ trên xuống, các cột được đánh số từ \(0\) đến \(m-1\) từ trái sang phải. Ký hiệu \((s,t)\) chỉ ô ở hàng \(s\), cột \(t\). Điểm quan tâm thứ \(i\) nằm trong ô \((r_i,c_i)\). Một ô có thể chứa nhiều điểm quan tâm.

Vệ tinh di chuyển trên đường chéo chính của lưới, nối góc trên bên trái với góc dưới bên phải. Nó có thể chụp ảnh độ phân giải cao của một vùng thỏa mãn cả ba điều kiện:

• Vùng có hình vuông.
• Hai góc đối diện của hình vuông nằm trên đường chéo chính của lưới.
• Mỗi ô của lưới nằm hoàn toàn bên trong hoặc hoàn toàn bên ngoài vùng được chụp.

Vệ tinh được chụp nhiều nhất \(k\) bức ảnh. Sau đó, nó truyền dữ liệu của mọi ô đã chụp về căn cứ, kể cả ô không chứa điểm quan tâm. Dữ liệu của mỗi ô chỉ được truyền một lần, dù ô đó xuất hiện trong nhiều ảnh.

Hãy chọn nhiều nhất \(k\) vùng hình vuông sao cho mọi ô chứa điểm quan tâm đều được chụp ít nhất một lần, đồng thời số ô được chụp ít nhất một lần là nhỏ nhất. Bạn cần tìm số ô nhỏ nhất này.

Chi tiết cài đặt

Trong C++, cài đặt hàm khai báo trong aliens.h:

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c);

Trong Java, cài đặt phương thức sau trong lớp aliens:

public long take_photos(int n, int m, int k, int[] r, int[] c)

Trong C, giao diện là:

long long take_photos(int n, int m, int k, int* r, int* c);

• n: số điểm quan tâm.
• m: số hàng và số cột của lưới.
• k: số ảnh tối đa được chụp.
• r, c: hai mảng độ dài \(n\); điểm thứ \(i\) nằm trong ô (r[i], c[i]).
• Hàm trả về số ô nhỏ nhất được chụp ít nhất một lần, đồng thời phủ tất cả các điểm quan tâm. Giá trị trả về là số nguyên \(64\) bit.

Nộp phần cài đặt hàm, không viết hàm main; sử dụng các tệp mẫu của ngôn ngữ tương ứng trong gói đính kèm. Khi nộp bằng C trên LQDOJ, dùng #include "aliens.h" thay cho #include "aliens_c.h" trong tệp mẫu; header dùng chung cung cấp đúng giao diện C ở trên.

Ràng buộc

• \(1 \le n \le 100\,000\).
• \(1 \le m \le 1\,000\,000\).
• \(1 \le k \le n\).
• \(0 \le r_i,c_i < m\) với mọi \(0 \le i < n\).
• Các cặp \((r_i,c_i)\) không nhất thiết phân biệt.

Phân nhóm

Mỗi subtask được tính trọn số điểm khi tất cả các test của subtask đó đều đúng; nếu không, subtask được \(0\) điểm. Các giới hạn tọa độ và \(1 \le k \le n\) luôn áp dụng.

Ví dụ

Lời gọi thứ nhất:

take_photos(5, 7, 2, [0, 4, 4, 4, 4], [3, 4, 6, 5, 6])

Có \(5\) điểm quan tâm trên lưới \(7 \times 7\), nằm trong bốn ô khác nhau: \((0,3)\), \((4,4)\), \((4,5)\), \((4,6)\). Có thể chụp nhiều nhất \(2\) ảnh.

Một cách phủ tất cả các điểm là chụp vùng \(6 \times 6\) từ ô \((0,0)\) đến \((5,5)\) và vùng \(3 \times 3\) từ ô \((4,4)\) đến \((6,6)\). Hai vùng chồng nhau trên \(4\) ô, nên tổng cộng có \(36+9-4=41\) ô được chụp. Cách này chưa tối ưu.

Phương án tối ưu chụp vùng \(4 \times 4\) từ ô \((0,0)\) đến \((3,3)\) và vùng \(3 \times 3\) từ ô \((4,4)\) đến \((6,6)\). Hai vùng phủ \(16+9=25\) ô, nên hàm trả về \(25\). Chụp ô \((4,6)\) một lần là đủ dù ô đó chứa hai điểm quan tâm.

Lời gọi thứ hai:

take_photos(2, 6, 2, [1, 4], [4, 1])

Hai điểm quan tâm nằm đối xứng tại \((1,4)\) và \((4,1)\). Bất kỳ ảnh hợp lệ nào chứa một điểm cũng chứa điểm kia. Chỉ cần chụp một vùng \(4 \times 4\), gồm \(16\) ô, nên hàm trả về \(16\).

Trình chấm mẫu

Trình chấm mẫu đọc dòng đầu chứa \(n,m,k\). Dòng \(2+i\), với \(0 \le i < n\), chứa hai số \(r_i,c_i\). Chương trình in giá trị trả về của take_photos trên một dòng.

5 7 2
0 3
4 4
4 6
4 5
4 6

25

2 6 2
1 4
4 1

16

Nguồn

IOI 2016, ngày thi thứ hai, bài Aliens. Đề tiếng Việt và gói tệp dành cho thí sinh được đính kèm.