JOI 2009 Representative Selection - Ngày 2

Một ngày nọ, X bắt cóc Y, bịt mắt Y rồi lái xe đưa Y từ nơi bắt cóc về nhà mình. Nhờ nỗ lực của cảnh sát, X đã bị bắt và vụ việc được giải quyết, nhưng động cơ của X vẫn còn là một bí ẩn. Là thám tử đang điều tra động cơ ấy, bạn cần xác định có bao nhiêu lộ trình phù hợp với lời khai của Y.

Khu phố có dạng lưới, gồm \(W+1\) con đường chạy theo hướng bắc–nam và \(H+1\) con đường chạy theo hướng đông–tây. Nơi bắt cóc nằm ở góc tây nam của lưới, còn nhà X nằm ở góc đông bắc.

Y nhớ chính xác số lần rẽ và thứ tự các lần rẽ trái, rẽ phải trên đường đi. X có thể đã đi qua cùng một giao lộ hoặc cùng một đoạn đường nhiều lần, và cũng có thể đã đi ngang qua nhà mình mà chưa dừng lại. Tuy nhiên, X không quay đầu xe lần nào.

Chẳng hạn, với \((W,H)=(4,3)\), nếu X đi theo các mũi tên nét đậm trong hình dưới đây, lời khai của Y sẽ là: rẽ trái, rẽ phải, rẽ phải, rẽ phải, rẽ trái, rẽ trái, rẽ trái.

Trong hình, nhãn ở góc dưới bên trái chỉ nơi bắt cóc; nhãn ở góc trên bên phải chỉ nhà X.

Yêu cầu

Đếm số lộ trình từ nơi bắt cóc đến nhà X có đúng chuỗi rẽ đã cho. In phần dư của số lộ trình khi chia cho \(10\,000\,000\).

Dữ liệu vào

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

• Dòng thứ nhất chứa hai số nguyên \(W,H\). Số đường chạy theo hướng bắc–nam và đông–tây lần lượt là \(W+1\) và \(H+1\).
• Dòng thứ hai chứa số nguyên \(N\), là số lần rẽ trong lời khai của Y.
• Dòng thứ ba chứa một chuỗi độ dài \(N\), chỉ gồm L và R. Ký tự thứ \(i\) bằng L nếu lần rẽ thứ \(i\) là rẽ trái, và bằng R nếu lần rẽ đó là rẽ phải.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là số lộ trình có thể xảy ra, lấy phần dư khi chia cho \(10^7\).

Ràng buộc

• \(1\le W,H\le1000\).
• \(1\le N\le10\,000\).
• Chuỗi lời khai có đúng \(N\) ký tự L hoặc R.
• 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

Tổng điểm là \(100\), gồm \(10\) nhóm, mỗi nhóm \(10\) điểm. Các nhóm lần lượt là 01, 02, 03, 04, (05,11), 06, 07, 08, 09, 10. Nhóm (05,11) gồm hai test 05 và 11; mỗi nhóm khác chứa đúng một test. Phải vượt qua mọi test trong một nhóm để nhận điểm của nhóm đó.

Các test thỏa mãn \(W,H\le40\) chiếm \(40\) điểm.

Ví dụ

4 3
7
LRRRLLL

80

4 4
3
RLR

9

Công ty JOI vừa hoàn thành sản phẩm mới mang tên “Dụng cụ kỳ lạ khó tin” (Incredibly Odd Instrument). Giám đốc đã có thông tin liên lạc của tất cả những người có khả năng mua sản phẩm và muốn gửi thông báo cho họ. Tuy nhiên, gửi trực tiếp cho quá nhiều người có thể khiến công ty bị xem là một doanh nghiệp thiếu uy tín.

Vì vậy, giám đốc muốn chọn ít người nhất để gửi thông báo trực tiếp, rồi để thông tin lan truyền tới những người còn lại. Sản phẩm rất đột phá, nên ngay khi biết về sản phẩm, mỗi người sẽ lập tức chuyển thông tin cho tất cả những người mà mình biết thông tin liên lạc.

Yêu cầu

Tìm số người ít nhất cần được công ty gửi thông báo trực tiếp để cuối cùng tất cả những người có khả năng mua sản phẩm đều biết về sản phẩm.

Dữ liệu vào

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

• Dòng thứ nhất chứa hai số nguyên \(n,m\), trong đó \(n\) là số người có khả năng mua sản phẩm. Những người này được đánh số từ \(1\) đến \(n\).
• Mỗi dòng trong \(m\) dòng tiếp theo chứa hai số nguyên \(a_j,b_j\), cho biết người \(a_j\) biết thông tin liên lạc của người \(b_j\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là số người ít nhất cần nhận thông báo trực tiếp từ công ty.

Ràng buộc

• \(1\le n\le100\,000\).
• \(0\le m\le100\,000\).
• \(1\le a_j,b_j\le n\) và \(a_j\ne b_j\).
• Không có hai dòng mô tả cùng một cặp có thứ tự \((a_j,b_j)\).
• 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

Tổng điểm là \(100\), gồm \(10\) nhóm, mỗi nhóm \(10\) điểm và chứa đúng một test, lần lượt từ 01 đến 10.

Các test thỏa mãn \(n\le1000\) và \(m\le1000\) chiếm \(70\) điểm.

Ví dụ

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

2

Một kỳ thi lập trình quốc tế có \(N\) quốc gia tham gia, được đánh số từ \(1\) đến \(N\). Mỗi quốc gia cử đúng hai thí sinh. Điểm của một quốc gia là tổng điểm của hai thí sinh thuộc quốc gia đó.

Các quốc gia được xếp hạng theo điểm giảm dần. Những quốc gia bằng điểm có cùng thứ hạng. Cụ thể, thứ hạng của một quốc gia bằng \(1\) cộng với số quốc gia có điểm cao hơn quốc gia đó. Ví dụ, nếu bốn quốc gia có điểm lần lượt là \(100,90,90,80\) thì thứ hạng của họ lần lượt là \(1,2,2,4\).

Ông X, một thành viên ban tổ chức, đã vô tình làm mất một phần dữ liệu. Điểm của tất cả thí sinh vẫn còn, nhưng với một số điểm, không còn biết thí sinh đạt điểm đó thuộc quốc gia nào.

Một quốc gia hỏi ông X về thứ hạng của mình. Do không thể xác định chính xác thứ hạng từ dữ liệu còn lại, ông X quyết định trả lời bằng thứ hạng tốt nhất có thể xảy ra.

Yêu cầu

Cho dữ liệu điểm còn lại và quốc gia \(C\), hãy tìm thứ hạng tốt nhất có thể của quốc gia \(C\). Khi khôi phục các quốc gia bị mất trong dữ liệu, phải giữ nguyên mọi thông tin đã biết và bảo đảm mỗi quốc gia có đúng hai thí sinh.

Dữ liệu vào

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

• Dòng thứ nhất chứa hai số nguyên \(N,C\), lần lượt là số quốc gia tham gia và số hiệu quốc gia hỏi về thứ hạng.
• Dòng thứ \(i+1\) (\(1\le i\le2N\)) chứa hai số nguyên \(s_i,a_i\). Thí sinh trong bản ghi này đạt \(s_i\) điểm và thuộc quốc gia \(a_i\). Nếu \(a_i=0\) thì không biết quốc gia của thí sinh đó.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là thứ hạng tốt nhất có thể của quốc gia \(C\), tức giá trị thứ hạng nhỏ nhất phù hợp với dữ liệu còn lại.

Ràng buộc

• \(1\le N\le3000\).
• \(1\le C\le N\).
• \(0\le s_i\le1\,000\,000\).
• \(0\le a_i\le N\).
• Có đúng \(2N\) bản ghi điểm, tương ứng với hai thí sinh của mỗi quốc gia trước khi một phần thông tin quốc gia bị mất.
• 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

Tổng điểm là \(100\), gồm \(25\) nhóm, mỗi nhóm \(4\) điểm và chứa đúng một test, lần lượt từ 01 đến 25. Không có mức điểm theo ràng buộc bổ sung được công bố.

Ví dụ

3 1
7 0
3 1
5 0
10 3
6 0
4 0

2

Quốc gia \(1\) có thể đứng thứ \(2\) hoặc thứ \(3\):

• Nếu điểm \(7\) thuộc quốc gia \(1\), các điểm \(5\) và \(4\) thuộc quốc gia \(2\), còn điểm \(6\) thuộc quốc gia \(3\), thì tổng điểm ba quốc gia lần lượt là \(7+3=10\), \(5+4=9\), \(10+6=16\). Quốc gia \(1\) đứng thứ \(2\).
• Nếu điểm \(7\) thuộc quốc gia \(1\), các điểm \(5\) và \(6\) thuộc quốc gia \(2\), còn điểm \(4\) thuộc quốc gia \(3\), thì tổng điểm ba quốc gia lần lượt là \(7+3=10\), \(5+6=11\), \(10+4=14\). Quốc gia \(1\) đứng thứ \(3\).

Do đó, thứ hạng tốt nhất cần in là \(2\).