JOI 2011 Representative Selection - Ngày 3

Bạn có được một tài liệu mật của nước IOI, được viết bằng các chữ cái từ A đến Z. Bản gốc của tài liệu được viết bằng ngôn ngữ IOI. Có thể thu được bản gốc bằng cách xóa một số ký tự trong tài liệu mật, có thể không xóa ký tự nào.

Một câu trong ngôn ngữ IOI là một chuỗi có ít nhất một ký tự, thỏa mãn \(M\) quy tắc đôi một khác nhau. Quy tắc thứ \(i\) \((1\le i\le M)\) quy định rằng ký tự \(B_i\) không được xuất hiện ngay sau ký tự \(A_i\).

Yêu cầu

Tính số bản gốc có thể có của tài liệu mật, lấy phần dư khi chia cho \(10\,000\,000\). Nếu những cách xóa khác nhau tạo ra cùng một chuỗi bản gốc thì chỉ tính chuỗi đó một lần.

Dữ liệu vào

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

• Dòng đầu chứa số nguyên \(L\), là độ dài của tài liệu mật.
• Dòng thứ hai chứa chuỗi tài liệu mật gồm \(L\) chữ cái từ A đến Z.
• Dòng thứ ba chứa số nguyên \(M\), là số quy tắc của ngôn ngữ IOI.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i+3\) \((1\le i\le M)\) chứa hai chữ cái \(A_i,B_i\) từ A đến Z, cách nhau bởi một dấu cách, mô tả quy tắc thứ \(i\). Không tồn tại \(j\ne i\) sao cho đồng thời \(A_j=A_i\) và \(B_j=B_i\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số bản gốc có thể có, lấy phần dư khi chia cho \(10\,000\,000\).

Ràng buộc

• \(1\le L\le300\,000\).
• \(0\le M\le26\times26\).

Thông tin kỹ thuật

Giới hạn của kỳ thi gốc: thời gian CPU \(0{,}5\) giây, bộ nhớ \(64\) MB.

Theo thông tin kỹ thuật của kỳ thi gốc, chương trình phải kết thúc bình thường với mã trả về \(0\). Một bộ dữ liệu chỉ được tính điểm khi chương trình đáp ứng giới hạn thời gian, bộ nhớ và cho kết quả đúng. Giới hạn ngăn xếp mặc định là \(8\) MB; cần tránh tràn ngăn xếp khi dùng đệ quy.

Khi cần xử lý số nguyên không vừa kiểu \(32\) bit, hãy dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++, với định dạng %lld cho scanf và printf. Với lượng dữ liệu vào/ra lớn, tài liệu kỹ thuật khuyến nghị dùng scanf/printf thay cho cin/cout để tránh chi phí vào/ra quá lớn.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(20\) bộ dữ liệu, mỗi bộ \(5\) điểm. Các điều kiện về tỷ lệ điểm dưới đây có thể chồng lấp:

• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn \(L\le15\).
• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn \(L\le5\,000\).

Ví dụ

5
JOIOI
1
I O

15

26
ABCDEFGHIJKLMNOPQRSTUVWXYZ
0

7108863

Ủy ban Olympic Tin học Nhật Bản là một tổ chức rất coi trọng việc báo cáo, liên lạc và trao đổi. Ủy ban có \(N\) người; mỗi người có đúng một người được chỉ định làm người nhận báo cáo của mình.

Ủy ban sắp triển khai một dự án gồm \(N\) công việc, được đánh số từ \(1\) đến \(N\). Mỗi người được giao phụ trách một công việc khác nhau. Các công việc được thực hiện lần lượt theo thứ tự từ công việc \(1\) đến công việc \(N\).

Khi hoàn thành công việc, người phụ trách gửi một báo cáo công việc cho người nhận báo cáo của mình. Người nhận được báo cáo tiếp tục chuyển chính báo cáo đó đến người nhận báo cáo của họ. Tuy nhiên, nếu một người đã từng chuyển báo cáo về công việc đó thì người ấy không chuyển lại báo cáo đó nữa. Quá trình này được lặp lại, nhờ đó một số người trong ủy ban nhận được báo cáo. Chỉ sau khi tất cả việc chuyển báo cáo của công việc trước kết thúc, công việc tiếp theo mới được thực hiện.

Yêu cầu

Cho biết người nhận báo cáo của người phụ trách từng công việc. Với mỗi người, hãy tính số loại báo cáo công việc khác nhau mà người đó đã nhận được tại thời điểm bắt đầu thực hiện công việc của mình.

Dữ liệu vào

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

• Dòng đầu chứa số nguyên \(N\), là số người trong ủy ban.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i+1\) \((1\le i\le N)\) chứa số nguyên \(A_i\). Người nhận báo cáo của người phụ trách công việc \(i\) là người phụ trách công việc \(A_i\).

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(i\) \((1\le i\le N)\) chứa một số nguyên là số loại báo cáo công việc khác nhau mà người phụ trách công việc \(i\) đã nhận được khi bắt đầu công việc của mình.

Ràng buộc

• \(2\le N\le100\,000\).
• \(1\le A_i\le N\) và \(A_i\ne i\) với mọi \(1\le i\le N\).

Thông tin kỹ thuật

Giới hạn của kỳ thi gốc: thời gian CPU \(0{,}5\) giây, bộ nhớ \(64\) MB.

Theo thông tin kỹ thuật của kỳ thi gốc, chương trình phải kết thúc bình thường với mã trả về \(0\). Một bộ dữ liệu chỉ được tính điểm khi chương trình đáp ứng giới hạn thời gian, bộ nhớ và cho kết quả đúng. Giới hạn ngăn xếp mặc định là \(8\) MB; cần tránh tràn ngăn xếp khi dùng đệ quy.

Khi cần xử lý số nguyên không vừa kiểu \(32\) bit, hãy dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++, với định dạng %lld cho scanf và printf. Với lượng dữ liệu vào/ra lớn, tài liệu kỹ thuật khuyến nghị dùng scanf/printf thay cho cin/cout để tránh chi phí vào/ra quá lớn.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn \(N\le1\,000\).

Ví dụ

6
3
4
2
6
3
2

0
1
1
3
0
5

Đây là bài chỉ nộp kết quả (output-only). Bạn cần nộp tệp kết quả cho từng tệp dữ liệu vào.

Người ngoài hành tinh đến từ hành tinh IOI dự định xây dựng một sân bay UFO tại công viên JOI ở Nhật Bản. Sự tồn tại của công viên này được giữ bí mật với người dân thông thường. Họ đã khảo sát công viên và lập bản đồ những nơi UFO có thể hạ cánh.

Công viên JOI là một hình chữ nhật rộng \(W\) mét theo hướng đông–tây và dài \(H\) mét theo hướng bắc–nam, được chia thành \(W\times H\) ô vuông cạnh \(1\) mét. Ô ở cột thứ \(x\) tính từ phía tây và hàng thứ \(y\) tính từ phía bắc được ký hiệu là \((x,y)\). Ô ở góc tây bắc là \((1,1)\), còn ô ở góc đông nam là \((W,H)\). Mỗi ô thuộc một trong hai loại: có thể hạ cánh, ký hiệu bằng ., hoặc không thể hạ cánh, ký hiệu bằng w.

UFO do người ngoài hành tinh IOI chế tạo nằm gọn trong một hình chữ nhật rộng \(B\) mét và sâu \(D\) mét. Theo thiết kế, khi UFO hạ cánh, các hướng trên, dưới, trái, phải trong bản thiết kế phải lần lượt tương ứng với các hướng bắc, nam, tây, đông; góc trên bên trái của bản thiết kế phải trùng với góc trên bên trái của một ô trong công viên.

Bản thiết kế UFO là một lưới gồm \(D\) hàng và \(B\) cột, tổng cộng \(B\times D\) ô. Ô ở cột thứ \(i\) từ trái sang và hàng thứ \(j\) từ trên xuống được ký hiệu là \((i,j)\). Ô trên cùng bên trái là \((1,1)\), ô dưới cùng bên phải là \((B,D)\). Ô \((i,j)\) cho biết liệu UFO có chiếm một phần của vùng vuông nằm cách mép phía tây của UFO từ \(i-1\) đến \(i\) mét và cách mép phía bắc từ \(j-1\) đến \(j\) mét hay không. Ô có chứa một phần UFO được ký hiệu bằng O (chữ O hoa); ô không chứa phần nào của UFO được ký hiệu bằng ..

Khi một UFO hạ cánh, mọi ô có ký hiệu O trong bản thiết kế phải nằm trên các ô có thể hạ cánh của công viên. Khi nhiều UFO cùng hạ cánh, không ô nào thuộc một UFO được chung cạnh với bất kỳ ô nào thuộc một UFO khác. Tuy nhiên, các UFO được phép tiếp xúc tại góc của các ô.

Bạn tình cờ được chọn làm đại sứ thiện chí của hành tinh IOI. Hãy lập phương án xây dựng sân bay có thể đón càng nhiều UFO hạ cánh càng tốt.

Yêu cầu

Lập phương án sân bay UFO trong công viên JOI. Phương án cho phép càng nhiều UFO hạ cánh thì điểm càng cao.

Phương án là bản đồ công viên JOI được bổ sung các UFO đã hạ cánh. Trong các ô có thể hạ cánh, dùng O (chữ O hoa) cho ô có chứa UFO và . cho ô không chứa UFO. Các ô không thể hạ cánh vẫn được biểu diễn bằng w.

Dữ liệu vào

Tải bộ dữ liệu vào, gồm năm tệp 01.in, 02.in, 03.in, 04.in, 05.in.

Mỗi tệp dữ liệu vào có định dạng sau:

• Dòng đầu chứa hai số nguyên \(B,D\), cách nhau bởi một dấu cách, lần lượt là chiều rộng và chiều sâu của UFO, tính bằng mét.
• \(D\) dòng tiếp theo mô tả bản thiết kế UFO. Dòng thứ \(j+1\) \((1\le j\le D)\) chứa một chuỗi gồm \(B\) ký tự. Ký tự thứ \(i\) \((1\le i\le B)\) là O hoặc ., biểu diễn ô \((i,j)\) của bản thiết kế.
• Dòng thứ \(D+2\) chứa hai số nguyên \(W,H\), cách nhau bởi một dấu cách, lần lượt là kích thước công viên theo hướng đông–tây và bắc–nam, tính bằng mét.
• \(H\) dòng tiếp theo mô tả bản đồ công viên. Dòng thứ \(y+D+2\) \((1\le y\le H)\) chứa một chuỗi gồm \(W\) ký tự. Ký tự thứ \(x\) \((1\le x\le W)\) là . hoặc w, biểu diễn ô \((x,y)\) của công viên.

Dữ liệu ra

Tệp kết quả gồm \(H\) dòng. Dòng thứ \(y\) \((1\le y\le H)\) chứa một chuỗi gồm \(W\) ký tự, mô tả hàng thứ \(y\) tính từ phía bắc của công viên. Ký tự thứ \(x\) \((1\le x\le W)\) trên dòng này là một trong ba ký tự O, ., w, biểu diễn trạng thái của ô \((x,y)\) trong phương án.

Cách nộp bài

Nộp kết quả tương ứng với từng tệp dữ liệu vào. Mỗi kết quả phải tuân thủ định dạng được quy định trong phần Dữ liệu ra.

Trong kỳ thi gốc, phản hồi khi nộp bài chỉ kiểm tra kết quả có đúng định dạng hay không. Việc phương án có hợp lệ và được bao nhiêu điểm được xác định theo phần Chấm điểm.

Ràng buộc

• \(1\le B\le5\).
• \(1\le D\le5\).
• \(1\le W\le200\).
• \(1\le H\le200\).

Chấm điểm

Bài có \(5\) tệp dữ liệu, mỗi tệp tối đa \(20\) điểm, tổng cộng \(100\) điểm. Mỗi tệp được gán một giá trị \(X\) như trong bảng dưới. Gọi \(Y\) là số UFO hạ cánh lớn nhất trong các phương án mà các thí sinh đã nộp cho tệp đó.

Nếu phương án của bạn không thỏa mãn các điều kiện của bài toán, bạn nhận \(0\) điểm cho tệp đó. Nếu phương án hợp lệ, gọi \(\alpha\) là số UFO có thể hạ cánh trong phương án của bạn. Điểm được tính như sau:

• Nếu \(\alpha\le X\), điểm là \(\frac{4\alpha}{X}\).
• Nếu \(X<\alpha\), điểm là \(4+16\times\left(\frac{\alpha-X}{Y-X}\right)^2\).

Trong cả hai trường hợp, làm tròn điểm đến một chữ số sau dấu phẩy: nếu chữ số thập phân thứ hai từ \(5\) trở lên thì làm tròn lên, nếu không thì làm tròn xuống.

Ví dụ

4 3
O..O
OOOO
.O..
20 10
....................
.w......w.......ww..
....ww......w.w.....
.w.....w............
...w......w.........
w................ww.
....w...............
.w.....w........w.ww
............w.......
....w..............w

..O..O......O..O....
.wOOOO.Ow.O.OOOOww..
...Oww.OOOO.wOw.O..O
.w.....wO..O..O.OOOO
.O.wO.O..OwOOOO..O..
wOOOO.OOOO..O...OwwO
..O.w..O..O..O..OOOO
Ow.O.O.wO.OOOO..wOww
OOOO.OOOO..Ow.......
.O..w.O............w