JOI 2009 Representative Selection - Ngày 3

Bạn nuôi một chú chó tên là JOI. Khi đi dạo, mỗi bước JOI di chuyển về một trong bốn hướng bắc, đông, nam hoặc tây. Bạn gắn cho JOI một thiết bị ghi lại mỗi bước bằng ký tự tương ứng N, E, S hoặc W. Khi JOI dừng lại và kết thúc cuộc đi dạo, thiết bị ghi ký tự Q.

Bạn coi phần được đường đi của JOI bao quanh là lãnh thổ của chú chó. Chính xác hơn, đó là hình có diện tích lớn nhất gồm một hoặc nhiều đa giác không chồng lấn, sao cho mọi cạnh của các đa giác đều nằm trên đường JOI đã đi qua. Diện tích của một hình vuông có cạnh bằng một bước chân được tính là \(1\).

Yêu cầu

Cho bản ghi di chuyển, hãy tính diện tích lãnh thổ của JOI. Nếu đường đi không bao quanh phần nào, kết quả là \(0\).

Dữ liệu vào

Đọc từ đầu vào chuẩn. Mỗi dòng chứa đúng một ký tự trong N, E, S, W, Q. Dòng chứa Q là dòng cuối cùng của dữ liệu vào.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên duy nhất là diện tích lãnh thổ.

Ràng buộc

• JOI thực hiện ít nhất một bước di chuyển.
• Tổng số dòng dữ liệu vào, kể cả dòng Q, không vượt quá \(100\,000\).
• Giới hạn thời gian: \(1\) giây cho mỗi test.
• Giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Bài có \(10\) nhóm chấm, mỗi nhóm \(10\) điểm, tổng cộng \(100\) điểm. Để nhận điểm của một nhóm, chương trình phải trả lời đúng tất cả các test trong nhóm. Các mã dưới đây là số hiệu test trong bộ dữ liệu:

Các test tương ứng với \(30\%\) tổng số điểm có không quá \(1000\) dòng dữ liệu vào.

Ví dụ

S
W
W
N
E
E
E
S
E
N
W
Q

3

E
N
E
N
S
W
S
W
S
W
Q

0

Ông JOI điều hành khách sạn IOI trên cao nguyên IOI, một địa điểm trượt tuyết nổi tiếng. Địa hình phức tạp ở đây rất được những người trượt tuyết giỏi yêu thích, nhưng lại không thân thiện với người mới bắt đầu. Ông JOI muốn tìm tuyến trượt dễ nhất để giới thiệu cao nguyên cho những người mới tập.

Tuyến trượt dễ nhất là tuyến có vận tốc trung bình nhỏ nhất. Vận tốc trung bình của cả tuyến bằng tổng quãng đường chia cho tổng thời gian đi hết tuyến. Điểm bắt đầu phải là một địa điểm có thể đến bằng cáp treo đi thẳng từ khách sạn IOI; điểm kết thúc phải là khách sạn IOI.

Các địa điểm được đánh số từ \(1\) đến \(n\), trong đó khách sạn IOI ở địa điểm \(n\). Địa điểm càng cao thì có số hiệu càng nhỏ; không có hai địa điểm cùng độ cao. Mỗi đoạn đường chỉ đi từ nơi cao xuống nơi thấp, nên không thể đi rồi quay lại cùng một địa điểm.

Yêu cầu

Cho các đoạn đường có thể dùng để trượt tuyết, chiều dài và vận tốc trung bình trên từng đoạn, cùng các địa điểm có thể đến bằng cáp treo trực tiếp từ khách sạn, hãy tìm vận tốc trung bình nhỏ nhất của một tuyến trượt hợp lệ. Làm tròn kết quả đến số nguyên gần nhất, với phần thập phân từ \(0{,}5\) trở lên được làm tròn lên.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(n,m,c\): số địa điểm, số địa điểm có thể đến bằng cáp treo trực tiếp từ khách sạn và số đoạn đường có thể dùng.
• Dòng thứ hai chứa \(m\) số nguyên \(a_1,a_2,\ldots,a_m\), là các địa điểm có thể đến bằng cáp treo trực tiếp từ khách sạn.
• Trong \(c\) dòng tiếp theo, dòng thứ \(j\) chứa bốn số nguyên \(f_j,t_j,d_j,s_j\): điểm đầu, điểm cuối, chiều dài và vận tốc trung bình của đoạn đường thứ \(j\).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là vận tốc trung bình nhỏ nhất sau khi làm tròn.

Ràng buộc

• \(1\le n\le10\,000\), \(1\le m<n\), \(1\le c\le100\,000\).
• \(1\le a_i<n\) với \(1\le i\le m\).
• \(1\le f_j<t_j\le n\), \(1\le d_j\le100\), \(1\le s_j\le100\,000\) với \(1\le j\le c\).
• Luôn tồn tại ít nhất một tuyến bắt đầu tại một địa điểm có cáp treo trực tiếp từ khách sạn và kết thúc tại khách sạn.
• Mọi giá trị sai lệch không quá \(0{,}01\) so với vận tốc trung bình nhỏ nhất đều cho cùng một số nguyên khi làm tròn theo quy tắc trên.
• Giới hạn thời gian: \(1\) giây cho mỗi test.
• Giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Bài có \(20\) nhóm chấm, mỗi nhóm gồm đúng một test: lần lượt là 01, 02, ..., 20. Mỗi nhóm được \(5\) điểm nếu trả lời đúng, tổng cộng \(100\) điểm.

• Các test tương ứng với \(20\%\) tổng số điểm thỏa mãn \(n\le10\) và \(c\le100\).
• Các test tương ứng với \(50\%\) tổng số điểm thỏa mãn \(n\le100\) và \(c\le100\).

Các bảo đảm trên có thể bao hàm nhau, không phải các phân nhóm điểm tách biệt để cộng lại.

Ví dụ

3 1 3
1
1 2 6 1000
2 3 4 2000
1 3 3 3000

1250

4 2 5
1 2
1 3 2 5000
1 3 9 4000
2 3 3 5000
2 4 4 7000
3 4 8 3000

3261

Vào năm \(20XX\), Lễ hội Tin học Quốc tế (International Omatsuri in Informatics) sẽ được tổ chức tại Nhật Bản. Bạn được giao thiết kế biểu trưng cho lễ hội.

Biểu trưng được tạo từ một hình có sẵn, gồm một số ô vuông trong một bảng hình chữ nhật rộng \(W\) ô và cao \(H\) ô. Bạn muốn tô hình này bằng hai màu đỏ và trắng của quốc kỳ Nhật Bản. Mỗi ô thuộc hình phải được tô bằng đúng một màu.

Một nhà thiết kế khuyên bạn chọn cách tô sao cho vùng màu đỏ và vùng màu trắng đều là những hình đối xứng qua một đường thẳng. Hai vùng không bắt buộc có cùng trục đối xứng. Ngoài ra, để cân đối màu sắc, phải có đúng \(K\) ô được tô đỏ.

Yêu cầu

Cho hình ban đầu và số \(K\), hãy tìm một cách tô thỏa mãn các điều kiện trên. Mỗi vùng màu được xét như hợp của toàn bộ các ô vuông được tô màu đó.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(W,H,K\), lần lượt là chiều rộng, chiều cao của bảng và số ô cần tô đỏ.
• Trong \(H\) dòng tiếp theo, mỗi dòng chứa \(W\) số nguyên bằng \(0\) hoặc \(1\). Số thứ \(j\) trên dòng thứ \(i\) của phần này cho biết ô ở hàng \(i\) tính từ trên xuống, cột \(j\) tính từ trái sang: \(1\) nghĩa là ô thuộc hình, \(0\) nghĩa là ô không thuộc hình.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn \(H\) dòng, mỗi dòng gồm \(W\) số nguyên cách nhau bởi dấu cách. Số ở hàng \(i\), cột \(j\) phải là:

• \(1\) nếu ô tương ứng được tô đỏ;
• \(2\) nếu ô tương ứng được tô trắng;
• \(0\) nếu ô tương ứng không thuộc hình ban đầu.

Nếu có nhiều cách tô hợp lệ, có thể xuất bất kỳ cách nào. Bài sử dụng bộ kiểm tra đáp án để xác nhận cách tô; không yêu cầu kết quả trùng từng số với ví dụ.

Ràng buộc

• \(1\le W,H\le40\).
• \(1\le K\le WH-1\).
• Hình ban đầu có ít nhất hai ô; \(K\) nhỏ hơn số ô thuộc hình.
• Luôn tồn tại ít nhất một cách tô hợp lệ.
• Giới hạn thời gian: \(3\) giây cho mỗi test.
• Giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Bài có \(25\) nhóm chấm, mỗi nhóm gồm đúng một test: lần lượt là 01, 02, ..., 25. Mỗi nhóm được \(4\) điểm nếu xuất một cách tô hợp lệ, tổng cộng \(100\) điểm.

Các test tương ứng với \(20\%\) tổng số điểm thỏa mãn \(W,H\le5\).

Ví dụ

4 3 2
0 1 0 0
1 0 1 1
1 0 0 0

0 2 0 0
1 0 2 1
2 0 0 0

Kết quả trên tương ứng với hình dưới đây. Ô màu xám biểu diễn ô được tô đỏ; ô màu trắng biểu diễn ô được tô trắng. Đường nét đứt và đường chấm lần lượt là trục đối xứng của vùng đỏ và vùng trắng.

Cách tô sau không hợp lệ vì vùng đỏ không đối xứng qua một đường thẳng:

Cách tô sau không hợp lệ vì số ô đỏ không bằng \(2\):