BOI 2019 - Ngày 1

Một chip vi điều khiển có sẵn bộ nhớ flash gồm \(B\) bit. Ta cần lưu trữ và cập nhật một biến gồm \(M\) bit trong bộ nhớ này. Bộ nhớ flash có một hạn chế: có thể đổi riêng từng bit từ \(0\) thành \(1\), nhưng chỉ có thể đổi từ \(1\) thành \(0\) bằng cách xóa toàn bộ bộ nhớ. Bộ nhớ chỉ có thể được xóa một số lần hữu hạn trước khi chip bị hao mòn và phải thay thế. Vì vậy, ta muốn ghi được càng nhiều giá trị càng tốt trước khi phải xóa bộ nhớ.

Nhiệm vụ của bạn là thiết kế một cách lưu trữ hiệu quả sao cho luôn có thể khôi phục giá trị hiện tại. Cụ thể, chương trình của bạn phải thực hiện hai thao tác:

• Ghi một giá trị: đầu vào là trạng thái hiện tại của bộ nhớ và giá trị mới cần ghi; bạn phải đưa ra trạng thái mới của bộ nhớ.
• Đọc một giá trị: đầu vào là trạng thái của bộ nhớ sau một số thao tác ghi; bạn phải đưa ra giá trị được ghi trong thao tác ghi cuối cùng.

Hai thao tác đọc và ghi không được trao đổi thông tin bằng bất kỳ cách nào khác ngoài việc đọc trạng thái hiện tại của bộ nhớ từ đầu vào và, đối với thao tác ghi, đổi một số bit (có thể không đổi bit nào) từ \(0\) thành \(1\) trước khi đưa trạng thái mới ra đầu ra.

Yêu cầu nộp bài

Bạn cần nộp mã nguồn của một chương trình thực hiện cả hai vai trò đọc và ghi. Chương trình giao tiếp với hệ thống chấm qua đầu vào chuẩn và đầu ra chuẩn theo giao thức dưới đây; vai trò của mỗi lần chạy được xác định bởi giá trị \(T\) nhận được khi khởi động.

Giao thức tương tác

Đây là bài toán tương tác. Khi chương trình bắt đầu, dòng đầu tiên của đầu vào chứa số nguyên \(T\): \(T=0\) nghĩa là chương trình sẽ ghi các giá trị vào bộ nhớ, còn \(T=1\) nghĩa là chương trình sẽ đọc các giá trị từ bộ nhớ. Dòng thứ hai chứa hai số nguyên \(B\) và \(M\). Những dòng tiếp theo mô tả các thao tác.

Đối với cả hai vai trò, dòng đầu tiên của mỗi thao tác chứa số nguyên \(C\). Nếu \(C=0\), không còn yêu cầu nào và chương trình phải kết thúc. Nếu \(C=1\), chương trình phải tiếp tục xử lý:

• Nếu \(T=0\) và \(C=1\), dòng thứ hai của thao tác chứa hai xâu cách nhau bởi một dấu cách: trạng thái hiện tại của bộ nhớ dưới dạng xâu \(B\) bit và giá trị mới cần ghi dưới dạng xâu \(M\) bit. Nếu có thể ghi giá trị mới bằng cách chỉ đổi một số bit từ \(0\) thành \(1\), chương trình phải in số nguyên 1, rồi in trạng thái mới của bộ nhớ dưới dạng xâu \(B\) bit trên dòng tiếp theo. Nếu không thể ghi giá trị mới, chương trình phải in số nguyên 0.
• Nếu \(T=1\) và \(C=1\), dòng thứ hai của thao tác chứa một xâu duy nhất: trạng thái của bộ nhớ dưới dạng xâu \(B\) bit. Chương trình phải in một xâu \(M\) bit biểu diễn giá trị được ghi vào bộ nhớ gần nhất.

Sau mỗi câu trả lời, bạn phải đẩy hết bộ đệm đầu ra (flush) để bảo đảm hệ thống chấm nhận được câu trả lời. Đầu ra luôn phải kết thúc bằng ký tự xuống dòng. Các lệnh dưới đây minh họa việc trả lời một thao tác ghi thành công với trạng thái mới là s.

C:

fprintf(stdout, "1\n%s\n", s);
fflush(stdout);

C++:

cout << 1 << "\n" << s << endl;

Java:

System.out.println("1");
System.out.println(s);
System.out.flush();

Python:

sys.stdout.write("1\n{0}\n".format(s))
sys.stdout.flush()

Quá trình kiểm thử

Với mỗi test, hệ thống sẽ khởi chạy đồng thời bốn tiến trình của chương trình, gồm hai tiến trình ghi và hai tiến trình đọc. Giới hạn bộ nhớ và thời gian CPU được tính cho tổng cộng cả bốn tiến trình. Mọi hành vi cố ý truyền dữ liệu giữa các tiến trình qua kênh ngoài giao thức đều bị coi là gian lận và sẽ dẫn đến việc bị loại.

Ban đầu, hệ thống tạo một số khối bộ nhớ, mỗi khối gồm \(B\) bit đều bằng \(0\). Sau đó, các thao tác ghi và đọc được thực hiện theo một thứ tự hợp lệ nào đó.

Trong một thao tác ghi, một tiến trình ghi nhận trạng thái hiện tại của một khối cùng giá trị cần ghi vào khối đó. Bạn có thể giả sử các giá trị cần ghi được chọn ngẫu nhiên đều trong khoảng từ \(0\) đến \(2^M-1\), độc lập với mọi yếu tố khác. Nếu chương trình ghi được giá trị, trạng thái của khối được thay bằng trạng thái chương trình trả về. Nếu chương trình không ghi được giá trị, khối đó sẽ không tham gia bất kỳ thao tác ghi nào nữa.

Trong một thao tác đọc, một tiến trình đọc nhận trạng thái của một khối sau một thao tác ghi thành công. Hệ thống kiểm tra xem giá trị chương trình trả về có đúng là giá trị cần ghi trong thao tác ghi đó hay không. Đầu ra của mỗi thao tác ghi thành công được đọc đúng một lần.

Ràng buộc

Mọi test đều thỏa mãn \(N\cdot B\le 120\,000\), trong đó \(N\) là số thao tác ghi tối đa mà chương trình có thể được yêu cầu thực hiện. Các giá trị \(B\) và \(M\) của từng nhóm được liệt kê bên dưới.

Phân nhóm

Trong mỗi nhóm test, điểm của chương trình tỉ lệ với số giá trị trung bình ghi được trong các test thuộc nhóm. Cụ thể, nếu chương trình ghi được trung bình \(V\) giá trị trên mỗi khối, chương trình nhận được \(100\cdot V/P\%\) số điểm của nhóm, với \(P\) được cho dưới đây.

Nếu chương trình trả về giá trị sai trong bất kỳ thao tác đọc nào, điểm của toàn bộ nhóm bằng \(0\). Với bất kỳ lỗi nào khác, số giá trị đọc được trong test xảy ra lỗi được tính là \(0\).

1. Nhóm 1 (5 điểm): \(B=16\), \(M=8\), \(P=4.062445024495069624056\).
2. Nhóm 2 (5 điểm): \(B=32\), \(M=8\), \(P=12.264904841300964834177\).
3. Nhóm 3 (5 điểm): \(B=32\), \(M=16\), \(P=4.129591513707784802006\).
4. Nhóm 4 (5 điểm): \(B=64\), \(M=8\), \(P=30.039277894268828900030\).
5. Nhóm 5 (5 điểm): \(B=64\), \(M=16\), \(P=12.953148094217360432715\).
6. Nhóm 6 (5 điểm): \(B=64\), \(M=32\), \(P=4.073559788233661501537\).
7. Nhóm 7 (5 điểm): \(B=128\), \(M=8\), \(P=69.777892228928747548775\).
8. Nhóm 8 (5 điểm): \(B=128\), \(M=16\), \(P=34.731791275143635240976\).
9. Nhóm 9 (5 điểm): \(B=128\), \(M=32\), \(P=13.950788987705638908663\).
10. Nhóm 10 (5 điểm): \(B=128\), \(M=64\), \(P=4.039918210604800133907\).
11. Nhóm 11 (5 điểm): \(B=256\), \(M=8\), \(P=174.468047086071038511453\).
12. Nhóm 12 (5 điểm): \(B=256\), \(M=16\), \(P=82.222614151404177334554\).
13. Nhóm 13 (5 điểm): \(B=256\), \(M=32\), \(P=37.629382269769206488916\).
14. Nhóm 14 (5 điểm): \(B=256\), \(M=64\), \(P=14.263462282054140577686\).
15. Nhóm 15 (5 điểm): \(B=256\), \(M=128\), \(P=4.015569093893943430859\).
16. Nhóm 16 (5 điểm): \(B=512\), \(M=16\), \(P=204.746242127410346170221\).
17. Nhóm 17 (5 điểm): \(B=512\), \(M=32\), \(P=91.778595148073111539847\).
18. Nhóm 18 (5 điểm): \(B=512\), \(M=64\), \(P=39.230279242145938712621\).
19. Nhóm 19 (5 điểm): \(B=512\), \(M=128\), \(P=15.000000002167672268601\).
20. Nhóm 20 (5 điểm): \(B=512\), \(M=256\), \(P=4.005423277111055468876\).

Ví dụ

Input         Output
0
6 2
1
111111 00
              0
1
000000 11
              1
              110000
0

Input         Output
1
6 2
1
110000
              11
1
110100
              01
0

Nguồn

Baltic Olympiad in Informatics 2019, ngày 1, Tartu, Estonia, 27/4–2/5/2019. Giấy phép CC BY-SA 4.0.

Nautilus là một tàu ngầm bí mật, di chuyển trên đại dương và cố gắng không để bị phát hiện.

Đại dương được mô hình hóa bằng một lưới gồm \(R\times C\) ô, trong đó ký tự # biểu diễn đảo và ký tự . biểu diễn nước. Chẳng hạn:

...##....
..#.##..#
..#....##
.##...#..
....#....

Mỗi phút, Nautilus phát ra một tín hiệu vô tuyến có thể tiết lộ hướng mà tàu ngầm sắp di chuyển. Hướng di chuyển luôn là một trong bốn hướng: Bắc (N), Đông (E), Nam (S), Tây (W), như trong hình dưới đây.

Vytautas đã chế tạo một ra-đa thu được các tín hiệu định kỳ của tàu ngầm. Trong \(M\) phút vừa qua, ra-đa đã thu được \(M\) tín hiệu, được biểu diễn bằng một xâu gồm \(M\) ký tự, chẳng hạn WS?EE??. Một số tín hiệu không giải mã được và được đánh dấu bằng ký tự ?.

Vytautas không biết vị trí ban đầu của tàu ngầm, nhưng muốn dùng bản đồ đại dương để xác định vị trí hiện tại của nó. Biết rằng Nautilus luôn ở trong các ô nước trên bản đồ, hãy giúp Vytautas tính số ô phân biệt mà Nautilus có thể đang ở đó.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(R\), \(C\), \(M\).

\(R\) dòng tiếp theo tạo thành một lưới \(R\times C\) gồm các ký tự # và ., biểu diễn bản đồ đại dương.

Dòng cuối cùng mô tả các tín hiệu Vytautas thu được: một xâu gồm \(M\) ký tự, mỗi ký tự thuộc tập N, E, S, W, ?.

Dữ liệu ra

In một số nguyên duy nhất: số vị trí hiện tại phân biệt có thể có của Nautilus.

Ràng buộc

\(1\le R,C\le 500\); \(1\le M\le 5000\).

Phân nhóm

1. Nhóm 1 (29 điểm): \(1\le R,C,M\le 100\); không có ký tự ?.
2. Nhóm 2 (37 điểm): \(1\le R,C,M\le 100\).
3. Nhóm 3 (34 điểm): \(1\le R,C\le 500\); \(1\le M\le 5000\).

Ví dụ

5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??

22

Nguồn

Baltic Olympiad in Informatics 2019, ngày 1, Tartu, Estonia, 27/4–2/5/2019. Giấy phép CC BY-SA 4.0.

Trong một thung lũng thuộc dãy An-pơ có \(N\) ngôi làng, được đánh số từ \(1\) đến \(N\), nối với nhau bằng đúng \(N-1\) con đường. Tuy vẫn có thể đi từ bất kỳ làng nào đến bất kỳ làng nào khác, hành trình có thể mất khá nhiều thời gian. Điều này đặc biệt phiền phức khi cần mua nhu yếu phẩm, vì chỉ có \(S\) trong số \(N\) ngôi làng có cửa hàng.

Mùa đông năm nay, tuyết rơi dày khiến tình hình càng tệ hơn. Vì vậy, bạn nên rời thung lũng, tức là đến ngôi làng \(E\) duy nhất ở con đèo nối thung lũng với thế giới bên ngoài, hoặc ít nhất mua đủ nhu yếu phẩm cho những tháng tiếp theo. Sáng nay, bạn nghe trên đài rằng tuyết đã khiến một trong \(N-1\) con đường không thể sử dụng được, nhưng lại không nghe rõ đó là con đường nào.

Bạn muốn biết mình và các bạn có thể rời thung lũng hay không; nếu không, mỗi người phải lái xe ít nhất bao xa để đến một ngôi làng có cửa hàng. Vì chưa biết đường nào bị chặn và bạn bè sống ở nhiều ngôi làng khác nhau trong thung lũng, hãy viết chương trình trả lời câu hỏi trên cho \(Q\) cặp gồm một ngôi làng và một con đường bị chặn.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên \(N\), \(S\), \(Q\), \(E\), trong đó \(N\) là số ngôi làng, \(S\) là số cửa hàng (\(1\le S\le N\)), \(Q\) là số truy vấn và \(E\) là ngôi làng cần đến để rời thung lũng (\(1\le E\le N\)).

Mỗi dòng trong \(N-1\) dòng tiếp theo chứa ba số nguyên \(A\), \(B\), \(W\), cho biết có một con đường dài \(W\) nối hai làng \(A\) và \(B\), với \(1\le A,B\le N\) và \(1\le W\le 10^9\).

Tiếp theo là \(S\) dòng, mỗi dòng chứa một số nguyên \(C\), cho biết làng \(C\) có cửa hàng (\(1\le C\le N\)). Các giá trị trên những dòng này đôi một khác nhau, tức là mỗi làng có nhiều nhất một cửa hàng.

Cuối cùng là \(Q\) dòng, mỗi dòng chứa hai số nguyên \(I\) và \(R\). Truy vấn này xét trường hợp con đường thứ \(I\) trong dữ liệu vào không còn sử dụng được (\(1\le I<N\), các đường được đánh số theo thứ tự xuất hiện). Bạn cần xác định những người bạn ở làng \(R\) (\(1\le R\le N\)) có thể rời thung lũng hay không; nếu không, hãy tìm khoảng cách đến ngôi làng có cửa hàng gần nhất mà họ có thể đến.

Các truy vấn được xét độc lập: trong mỗi truy vấn, chỉ con đường được chỉ định trong truy vấn đó bị chặn.

Dữ liệu ra

In \(Q\) dòng, dòng thứ \(i\) chứa câu trả lời cho truy vấn thứ \(i\):

• In escaped nếu có thể rời thung lũng.
• Nếu không thể rời thung lũng, in khoảng cách đến ngôi làng có cửa hàng gần nhất có thể đến được.
• Nếu không thể rời thung lũng và cũng không thể đến bất kỳ cửa hàng nào, in oo.

Ràng buộc

\(1\le N,Q\le 100\,000\). Các ràng buộc của \(S\), \(E\), các con đường, cửa hàng và truy vấn được nêu trong phần dữ liệu vào. Ban đầu có thể đi từ mọi ngôi làng đến mọi ngôi làng khác.

Phân nhóm

1. Nhóm 1 (9 điểm): \(1\le N\le 100\), \(1\le Q\le 10\,000\), và có đường nối hai làng \(A\), \(B\) khi và chỉ khi \(|A-B|=1\).
2. Nhóm 2 (27 điểm): \(1\le N\le 1000\), \(1\le Q\le 1000\).
3. Nhóm 3 (23 điểm): \(1\le N\le 100\,000\), \(1\le Q\le 100\,000\), và \(S=N\).
4. Nhóm 4 (41 điểm): \(1\le N\le 100\,000\), \(1\le Q\le 100\,000\).

Ví dụ

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

escaped
3
oo

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

8
escaped
escaped
escaped
0

Nguồn

Baltic Olympiad in Informatics 2019, ngày 1, Tartu, Estonia, 27/4–2/5/2019. Giấy phép CC BY-SA 4.0.