IOI 2008 - Ngày 2

Ramesses II vừa trở về sau một trận chiến thắng lợi. Để kỷ niệm chiến thắng, ông quyết định xây dựng một khu vườn tráng lệ. Khu vườn sẽ gồm một hàng cây dài, kéo từ cung điện của ông ở Luxor đến đền Karnak. Hàng cây chỉ gồm cây sen và cây cói giấy, vì hai loài cây này lần lượt tượng trưng cho Thượng Ai Cập và Hạ Ai Cập.

Khu vườn phải có đúng \(N\) cây. Ngoài ra, khu vườn phải cân bằng: trong bất kỳ đoạn liên tiếp nào của hàng cây, số cây sen và số cây cói giấy không được chênh lệch quá \(2\).

Có thể biểu diễn một khu vườn bằng một xâu gồm các chữ cái L (cây sen) và P (cây cói giấy). Chẳng hạn, với \(N=5\), có \(14\) khu vườn cân bằng. Theo thứ tự từ điển, đó là: LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP và PPLPL.

Ta sắp xếp tất cả các khu vườn cân bằng có cùng độ dài theo thứ tự từ điển, với L đứng trước P, rồi đánh số bắt đầu từ \(1\). Ví dụ, với \(N=5\), khu vườn số \(12\) là PLPPL.

Cho số cây \(N\) và một xâu biểu diễn một khu vườn cân bằng, hãy viết chương trình tính số thứ tự được gán cho khu vườn đó, lấy modulo số nguyên \(M\) cho trước. Giá trị \(M\) chỉ nhằm đơn giản hóa việc tính toán, không có ý nghĩa nào khác đối với việc giải bài toán.

Dữ liệu vào

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

• Dòng thứ nhất chứa số nguyên \(N\), là số cây trong khu vườn.
• Dòng thứ hai chứa số nguyên \(M\).
• Dòng thứ ba chứa một xâu gồm \(N\) ký tự L (cây sen) hoặc P (cây cói giấy), biểu diễn một khu vườn cân bằng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên từ \(0\) đến \(M-1\), kể cả hai đầu: số thứ tự của khu vườn được mô tả trong dữ liệu vào, lấy modulo \(M\).

Ràng buộc

• \(1 \le N \le 1\,000\,000\).
• \(7 \le M \le 10\,000\,000\).

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Các ví dụ trong đề không tính điểm. Các tệp ví dụ gốc có nhãn 0 được giữ lại riêng và có trọng số 0.

Tệp ví dụ gốc: lin/lin0a.in, lin/lin0b.in.

Ví dụ

5
7
PLPPL

5

12
10000
LPLLPLPPLPLL

39

Nguồn

IOI 2008, ngày thi thứ hai: Linear Garden, bản tiếng Anh 1.1. Tác giả đề bài: Aleksandar Ilić (Serbia). Tập đề bài và lời giải IOI 2008.

Bạn đang tham gia một cuộc thi đi xuyên Ai Cập từ tây sang đông dọc theo một đoạn thẳng. Ban đầu, bạn ở đầu mút phía tây của đoạn thẳng. Quy tắc của cuộc thi yêu cầu bạn luôn di chuyển dọc theo đoạn thẳng và luôn đi về phía đông.

Trên đoạn thẳng có \(N\) thiết bị dịch chuyển tức thời. Mỗi thiết bị có hai đầu mút. Mỗi khi bạn đi tới một đầu mút của thiết bị, thiết bị lập tức đưa bạn tới đầu mút còn lại. Tùy vào đầu mút mà bạn gặp, lần dịch chuyển này có thể đưa bạn về phía đông hoặc phía tây so với vị trí hiện tại. Sau khi được dịch chuyển, bạn phải tiếp tục đi về phía đông dọc theo đoạn thẳng; bạn không thể tránh bất kỳ đầu mút nào nằm trên đường đi của mình. Không có hai đầu mút của các thiết bị ở cùng một vị trí. Mọi đầu mút đều nằm hẳn bên trong đoạn thẳng, không trùng với điểm bắt đầu hoặc điểm kết thúc.

Mỗi lần được dịch chuyển, bạn nhận được \(1\) điểm. Mục tiêu của cuộc thi là kiếm được nhiều điểm nhất có thể. Để tăng số điểm, bạn được phép thêm tối đa \(M\) thiết bị mới vào đoạn thẳng trước khi bắt đầu hành trình. Bạn cũng được tính điểm khi sử dụng các thiết bị mới.

Bạn có thể đặt các đầu mút của thiết bị mới ở bất kỳ vị trí nào, kể cả vị trí có tọa độ không nguyên, miễn là không trùng với vị trí của một đầu mút khác. Nói cách khác, vị trí của tất cả các đầu mút, thuộc cả thiết bị cũ lẫn thiết bị mới, phải đôi một khác nhau. Các đầu mút mới cũng phải nằm hẳn giữa điểm bắt đầu và điểm kết thúc của đoạn thẳng.

Dữ liệu bảo đảm rằng dù bạn thêm các thiết bị như thế nào theo các quy tắc trên, bạn vẫn luôn có thể đi tới điểm kết thúc của đoạn thẳng.

Cho vị trí các đầu mút của \(N\) thiết bị ban đầu và số thiết bị mới tối đa \(M\) mà bạn được thêm, hãy viết chương trình tính số điểm lớn nhất bạn có thể kiếm được.

Dữ liệu vào

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

• Dòng thứ nhất chứa số nguyên \(N\), là số thiết bị dịch chuyển ban đầu trên đoạn thẳng.
• Dòng thứ hai chứa số nguyên \(M\), là số thiết bị mới tối đa mà bạn được thêm.
• Mỗi dòng trong \(N\) dòng tiếp theo mô tả một thiết bị. Dòng thứ \(i\) trong số này mô tả thiết bị thứ \(i\), chứa hai số nguyên \(W_i\) và \(E_i\), cách nhau bởi một dấu cách. Hai số này lần lượt là khoảng cách từ điểm bắt đầu của đoạn thẳng tới đầu mút phía tây và đầu mút phía đông của thiết bị.

Không có hai đầu mút nào của các thiết bị cho trước có cùng vị trí. Đoạn thẳng mà bạn đi trên đó bắt đầu tại vị trí \(0\) và kết thúc tại vị trí \(2\,000\,001\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: số điểm lớn nhất bạn có thể kiếm được.

Ràng buộc

• \(1 \le N \le 1\,000\,000\): số thiết bị ban đầu trên đoạn thẳng.
• \(1 \le M \le 1\,000\,000\): số thiết bị mới tối đa được thêm.
• \(1 \le W_i < E_i \le 2\,000\,000\) với \(1 \le i \le N\): khoảng cách từ điểm bắt đầu tới đầu mút phía tây và đầu mút phía đông của thiết bị thứ \(i\).

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Các ví dụ trong đề không tính điểm. Các tệp ví dụ gốc có nhãn 0 được giữ lại riêng và có trọng số 0.

Tệp ví dụ gốc: tel/tel0a.in, tel/tel0b.in.

Ví dụ

3
1
10 11
1 4
2 3

6

3
3
5 7
6 10
1999999 2000000

12

Nguồn

IOI 2008, ngày thi thứ hai: Teleporters, bản tiếng Anh 1.2. Tác giả đề bài: Masaki Watanabe (Nhật Bản). Tập đề bài và lời giải IOI 2008.

Bạn được giao nhiệm vụ tìm vị trí lớn nhất trong khả năng chi trả để xây dựng một kim tự tháp mới. Để hỗ trợ việc lựa chọn, bạn được cung cấp bản khảo sát một khu đất, đã được chia thành một lưới gồm \(M \times N\) ô vuông. Đáy kim tự tháp phải là một hình vuông có các cạnh song song với các cạnh của lưới.

Bản khảo sát ghi nhận \(P\) chướng ngại vật có thể chồng lấn lên nhau. Mỗi chướng ngại vật được mô tả bằng một hình chữ nhật trên lưới, có các cạnh song song với các cạnh của lưới. Để xây kim tự tháp, mọi ô nằm dưới đáy của nó phải được dọn sạch tất cả chướng ngại vật. Chi phí loại bỏ chướng ngại vật thứ \(i\) là \(C_i\). Khi loại bỏ một chướng ngại vật, phải loại bỏ toàn bộ nó, không được chỉ loại bỏ một phần. Việc loại bỏ một chướng ngại vật không ảnh hưởng đến bất kỳ chướng ngại vật nào khác chồng lấn với nó.

Cho kích thước \(M,N\) của khu đất, mô tả \(P\) chướng ngại vật cùng chi phí loại bỏ từng chướng ngại vật và ngân sách \(B\), hãy viết chương trình tìm độ dài cạnh lớn nhất có thể của đáy kim tự tháp sao cho tổng chi phí loại bỏ chướng ngại vật không vượt quá \(B\).

Dữ liệu vào

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

• Dòng thứ nhất chứa hai số nguyên lần lượt là \(M\) và \(N\), cách nhau bởi một dấu cách.
• Dòng thứ hai chứa số nguyên \(B\), là tổng chi phí lớn nhất bạn có thể chi trả, tức ngân sách của bạn.
• Dòng thứ ba chứa số nguyên \(P\), là số chướng ngại vật được tìm thấy trong bản khảo sát.
• \(P\) dòng tiếp theo mô tả các chướng ngại vật. Dòng thứ \(i\) trong số này mô tả chướng ngại vật thứ \(i\), chứa năm số nguyên \(X_{i1}\), \(Y_{i1}\), \(X_{i2}\), \(Y_{i2}\), \(C_i\), cách nhau bởi một dấu cách. Các số này lần lượt cho biết tọa độ của ô ở góc dưới bên trái, tọa độ của ô ở góc trên bên phải của chướng ngại vật, và chi phí loại bỏ chướng ngại vật đó.

Ô ở góc dưới bên trái của lưới có tọa độ \((1,1)\); ô ở góc trên bên phải có tọa độ \((M,N)\). Các tọa độ của một chướng ngại vật chỉ các ô ngoài cùng thuộc chướng ngại vật đó, kể cả các ô ở hai góc được cho.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: độ dài cạnh lớn nhất của đáy kim tự tháp mà bạn có thể chuẩn bị. Nếu không thể xây bất kỳ kim tự tháp nào, hãy in \(0\).

Ràng buộc

Các ràng buộc sau áp dụng cho mọi nhóm dữ liệu:

• \(1 \le M,N \le 1\,000\,000\): kích thước của lưới.
• \(1 \le C_i \le 7\,000\): chi phí loại bỏ chướng ngại vật thứ \(i\).
• \(1 \le X_{i1} \le X_{i2} \le M\): hoành độ của các ô ngoài cùng bên trái và bên phải của chướng ngại vật thứ \(i\).
• \(1 \le Y_{i1} \le Y_{i2} \le N\): tung độ của các ô dưới cùng và trên cùng của chướng ngại vật thứ \(i\).

Các ràng buộc theo chỉ số \(i\) áp dụng với mọi \(1 \le i \le P\).

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Các ví dụ trong đề không tính điểm. Các tệp ví dụ gốc có nhãn 0 được giữ lại riêng và có trọng số 0.

Tệp ví dụ gốc: pbs/pbs0a.in, pbs/pbs0b.in.

Ví dụ

6 9
42
5
4 1 6 3 12
3 6 5 6 9
1 3 3 8 24
3 8 6 9 21
5 1 6 2 20

4

13 5
0
8
8 4 10 4 1
4 3 4 4 1
10 2 12 2 2
8 2 8 4 3
2 4 6 4 5
10 3 10 4 8
12 3 12 4 13
2 2 4 2 21

3

Nguồn

IOI 2008, ngày thi thứ hai: Pyramid Base, bản tiếng Anh 1.3. Tác giả đề bài: Richard Peng (Canada). Tập đề bài và lời giải IOI 2008.