CEOI 2024 - Ngày 2

Đề bài

Để sáng tác một bài thi cho CEOI 2024, Ben được hội đồng khoa học tặng một món đồ chơi. Đó là một trò xếp hình có thể hình dung như một lưới \(H\times W\), bên trong có một vật bằng kim loại gồm hai phần: một thanh ngang kích thước \(1\times K\) và một thanh dọc kích thước \(L\times 1\), được gắn lỏng với nhau.

Không thanh nào có thể xoay theo bất kỳ cách nào, nhưng mỗi thanh có thể trượt theo chiều dọc hoặc chiều ngang độc lập với thanh còn lại, miễn là chúng luôn chồng lên nhau tại đúng một ô.

Ngoài ra, lưới còn chứa một số chướng ngại vật. Không thanh nào của vật kim loại có thể đi xuyên qua chướng ngại vật. Các thanh cũng không thể đi ra ngoài lưới, kể cả chỉ một phần. Nhiệm vụ của Ben là di chuyển vật kim loại từ vị trí bắt đầu được chỉ định đến một vị trí có thể khác sao cho cả hai thanh chồng lên ô đích được chỉ định.

Tuy nhiên, Ben đã chơi món đồ này một lúc mà vẫn chưa giải được. Thực tế, cậu bắt đầu nghi rằng ban tổ chức đã trêu mình và đưa cho cậu một trò xếp hình không thể giải. Vì vậy, cậu nhờ bạn xác định liệu trò xếp hình có giải được hay không.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên \(W\), \(H\), \(K\), \(L\), cách nhau bởi dấu cách, lần lượt là chiều rộng và chiều cao của trò xếp hình, chiều rộng của thanh ngang và chiều cao của thanh dọc.

Dòng thứ hai chứa bốn số nguyên \(x_h\), \(y_h\), \(x_v\), \(y_v\). Hai số đầu là tọa độ của ô ngoài cùng bên trái bị thanh ngang chiếm, hai số sau là tọa độ của ô trên cùng bị thanh dọc chiếm.

Các hàng được đánh số từ \(0\) đến \(H-1\) theo thứ tự từ trên xuống dưới; các cột được đánh số từ \(0\) đến \(W-1\) theo thứ tự từ trái sang phải. Tọa độ \(x\) là số cột và tọa độ \(y\) là số hàng.

\(H\) dòng tiếp theo, mỗi dòng gồm \(W\) ký tự, biểu diễn lưới:

• . biểu diễn một ô trống.
• X biểu diễn một chướng ngại vật.
• * biểu diễn ô đích.

Dữ liệu bảo đảm vị trí ban đầu của vật kim loại là hợp lệ: hai thanh chồng lên nhau tại đúng một ô, không thanh nào chồng lên chướng ngại vật hoặc nhô ra ngoài lưới.

Trên lưới có đúng một ô đích, tức là ký tự * xuất hiện đúng một lần. Ô đích có thể nằm dưới vật kim loại ở vị trí ban đầu.

Dữ liệu ra

In một dòng chứa YES nếu có thể di chuyển vật kim loại đến ô đích; ngược lại, in NO.

Giới hạn

• \(2\le W,H\le 1\,500\).
• \(2\le K\le W\) và \(2\le L\le H\).
• \(0\le x_h\le W-K\) và \(0\le y_h\le H-1\).
• \(0\le x_v\le W-1\) và \(0\le y_v\le H-L\).

Chấm điểm

• Subtask 1 (14 điểm): \(W,H\le 50\).
• Subtask 2 (21 điểm): \(W,H\le 90\).
• Subtask 3 (9 điểm): \(W,H\le 300\) và \(K,L\le 10\).
• Subtask 4 (29 điểm): \(W,H\le 360\).
• Subtask 5 (27 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 3 2 2
0 1 0 0
.X.*
....
...X

YES

2 3 2 3
0 1 0 0
.X
.*
.X

NO

Đề bài

Mạng lưới đường bộ cao tốc của Cộng hòa Séc gồm \(N\) thành phố và \(N-1\) con đường có độ dài đã biết, tính bằng kilômét. Giữa mỗi cặp thành phố tồn tại đúng một đường đi. Ngoài ra, mỗi thành phố có đúng một trạm xăng và không có trạm xăng ở nơi nào khác.

Một ngày nọ, một số người quyết định đi du lịch bằng ô tô. Tổng cộng có \(N^2\) chiếc xe di chuyển. Điều kỳ lạ là với mỗi cặp thành phố có thứ tự \((a,b)\), có đúng một chiếc xe đi từ thành phố \(a\) đến thành phố \(b\) theo đường đi duy nhất giữa hai thành phố.

Vì mọi người ở Cộng hòa Séc đều dùng xe Škoda, mỗi xe có bình nhiên liệu cùng dung tích \(K\) lít và tiêu thụ đều đặn một lít xăng trên mỗi kilômét. Trước khi khởi hành, bình nhiên liệu của mỗi xe đều đầy. Người Séc cũng khá dễ đoán: vì lười, họ chỉ đổ xăng khi không còn đủ nhiên liệu để đến thành phố tiếp theo; xe được phép đến một thành phố với bình xăng rỗng. Khi buộc phải dừng ở một trạm xăng, họ luôn đổ đầy bình.

Cơ quan thuế Séc muốn biết trong ngày có bao nhiêu xe đã dừng tại từng trạm xăng. Dựa trên hành vi dễ đoán này, hãy tính các giá trị đó.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách, lần lượt là số thành phố và dung tích bình nhiên liệu của mỗi xe.

Mỗi dòng trong \(N-1\) dòng tiếp theo mô tả một con đường và chứa ba số nguyên \(u_i\), \(v_i\), \(l_i\), cách nhau bởi dấu cách. Hai số \(u_i\), \(v_i\) là chỉ số của hai thành phố được con đường thứ \(i\) nối với nhau, còn \(l_i\) là độ dài con đường tính bằng kilômét.

Các thành phố được đánh số từ \(0\) đến \(N-1\). Dữ liệu bảo đảm giữa mỗi cặp thành phố tồn tại đúng một đường đi.

Dữ liệu ra

In \(N\) dòng. Các dòng lần lượt chứa số xe dừng tại trạm xăng của thành phố \(0\), thành phố \(1\), ..., thành phố \(N-1\).

Giới hạn

• \(2\le N\le 70\,000\).
• \(1\le K\le 10^9\).
• \(0\le l_i\le K\) với mọi \(0\le i\le N-2\).

Chấm điểm

Gọi \(D\) là số con đường lớn nhất cùng nối với một thành phố.

• Subtask 1 (18 điểm): \(N\le 1\,000\) và \(K\le 1\,000\).
• Subtask 2 (8 điểm): \(D\le 2\) và \(l_i=1\) với mọi \(0\le i\le N-2\).
• Subtask 3 (10 điểm): \(D\le 2\).
• Subtask 4 (12 điểm): \(K\le 10\) và \(D\le 10\).
• Subtask 5 (17 điểm): \(K\le 10\).
• Subtask 6 (35 điểm): Không có ràng buộc bổ sung.

Ví dụ

3 1
0 1 1
1 2 1

0
2
0

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

0
3
3
12
8
0

Đề bài

Václav có một vườn hoa xinh đẹp gồm \(M\) bông hoa được trồng trên cùng một đường thẳng. Anh cũng đặt \(N\) vòi phun nước trên đường thẳng này để tưới hoa.

Vị trí các vòi phun lần lượt là \(s_1,\ldots,s_N\). Vị trí các bông hoa lần lượt là \(f_1,\ldots,f_M\). Cả hai dãy đều được cho theo thứ tự không giảm:

• \(s_1\le s_2\le\ldots\le s_N\).
• \(f_1\le f_2\le\ldots\le f_M\).

Václav sắp lên đường tham dự CEOI. Anh muốn bảo đảm tất cả hoa được tưới đầy đủ trong thời gian mình vắng mặt. Để làm việc này, anh xoay riêng từng vòi phun sang trái hoặc sang phải và đặt công suất phun. Vì mọi vòi phun dùng chung một ống nước, chúng đều phun xa một khoảng như nhau.

Nếu công suất phun là \(K\) và vòi phun thứ \(i\) quay sang trái, nó sẽ tưới mọi bông hoa có vị trí trong đoạn từ \(s_i-K\) đến \(s_i\), kể cả hai đầu mút. Tương tự, nếu vòi phun thứ \(j\) quay sang phải, nó sẽ tưới mọi bông hoa có vị trí trong đoạn từ \(s_j\) đến \(s_j+K\), kể cả hai đầu mút. Một vòi phun có thể tưới nhiều bông hoa và một bông hoa có thể được nhiều vòi phun tưới.

Hãy xác định liệu có thể tưới tất cả các bông hoa hay không. Nếu có, hãy tìm công suất phun nhỏ nhất đủ dùng cùng với một cách xoay các vòi phun tương ứng. Nếu có nhiều cấu hình hợp lệ với công suất nhỏ nhất, bạn có thể in ra bất kỳ cấu hình nào.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.

Dòng thứ hai chứa \(N\) số nguyên \(s_1,\ldots,s_N\), cách nhau bởi dấu cách, là vị trí các vòi phun.

Dòng thứ ba chứa \(M\) số nguyên \(f_1,\ldots,f_M\), cách nhau bởi dấu cách, là vị trí các bông hoa.

Dữ liệu ra

Nếu không thể tưới tất cả các bông hoa, in số \(-1\).

Nếu có thể, in hai dòng. Dòng đầu tiên chứa số \(K\), là công suất phun nhỏ nhất cần thiết để tưới tất cả các bông hoa. Dòng thứ hai chứa xâu \(c\) độ dài \(N\), trong đó \(c_i\) là L nếu vòi phun thứ \(i\) cần quay sang trái và là R nếu vòi phun đó cần quay sang phải.

Giới hạn

• \(1\le N,M\le 10^5\).
• \(0\le s_i\le 10^9\) với mọi \(1\le i\le N\).
• \(0\le f_i\le 10^9\) với mọi \(1\le i\le M\).
• \(s_i\le s_j\) với mọi \(i\le j\).
• \(f_i\le f_j\) với mọi \(i\le j\).

Chấm điểm

• Subtask 1 (3 điểm): \(N=1\).
• Subtask 2 (6 điểm): \(N=3x\) với một số nguyên \(x\) nào đó, và \(s_{3i+1}=s_{3i+2}=s_{3i+3}\) với mọi \(0\le i\le x-1\); nói cách khác, các vòi phun luôn được đặt theo từng nhóm ba chiếc.
• Subtask 3 (17 điểm): \(N\le 10\) và \(M\le 1\,000\).
• Subtask 4 (27 điểm): \(K\le 8\); nghĩa là trong mọi bộ kiểm thử đều tồn tại một cách xoay các vòi phun sao cho công suất không quá \(8\) là đủ để tưới tất cả hoa.
• Subtask 5 (47 điểm): Không có ràng buộc bổ sung.

Ví dụ

3 3
10 10 10
5 11 16

6
LLR

1 2
1000
1 2000

-1