IOI 2008 - Ngày 1

Bạn cần in \(N\) từ bằng một chiếc máy in chữ rời. Đây là loại máy in cổ, trong đó người dùng xếp các miếng kim loại nhỏ, mỗi miếng mang một chữ cái, để tạo thành từ. Sau đó, một tờ giấy được ép lên các miếng kim loại để in từ đó. Chiếc máy của bạn cho phép thực hiện ba thao tác:

• Thêm một chữ cái vào cuối từ hiện đang có trong máy.
• Xóa chữ cái cuối cùng của từ hiện đang có trong máy. Chỉ được thực hiện thao tác này khi trong máy có ít nhất một chữ cái.
• In từ hiện đang có trong máy.

Ban đầu máy trống, không chứa miếng kim loại mang chữ cái nào. Khi in xong, bạn được phép để lại một số chữ cái trong máy. Bạn cũng có thể in các từ theo thứ tự tùy ý.

Mỗi thao tác đều tốn thời gian, nên bạn muốn thực hiện ít thao tác nhất có thể. Hãy tìm số thao tác ít nhất để in tất cả \(N\) từ đã cho, đồng thời đưa ra một dãy thao tác đạt được số lượng đó.

Dữ liệu vào

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

• Dòng đầu tiên chứa số nguyên \(N\), là số từ cần in.
• Mỗi dòng trong \(N\) dòng tiếp theo chứa một từ. Mỗi từ chỉ gồm các chữ cái tiếng Anh viết thường từ a đến z và có độ dài từ \(1\) đến \(20\), kể cả hai đầu mút. Các từ đôi một khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn:

• Dòng đầu tiên chứa số nguyên \(M\), là số thao tác ít nhất cần thực hiện để in \(N\) từ.
• Mỗi dòng trong \(M\) dòng tiếp theo chứa đúng một ký tự mô tả một thao tác, theo thứ tự thực hiện:
  • Thêm một chữ cái: ghi chính chữ cái đó ở dạng viết thường.
  • Xóa chữ cái cuối cùng: ghi ký tự - (dấu trừ, mã ASCII \(45\)).
  • In từ hiện tại: ghi ký tự P (chữ P viết hoa).

Ràng buộc

• \(1 \le N \le 25\,000\).
• Độ dài mỗi từ nằm trong đoạn \([1,20]\).
• Các từ đôi một khác nhau và chỉ chứa chữ cái tiếng Anh viết thường.

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: typ/typ0.in.

Ví dụ

3
print
the
poem

20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P

Nguồn

IOI 2008.

Bạn đang tham quan một công viên có \(N\) hòn đảo. Từ mỗi đảo \(i\), người ta đã xây đúng một cây cầu tới một đảo khác; độ dài của cây cầu đó được ký hiệu là \(L_i\). Như vậy, công viên có tổng cộng \(N\) cây cầu. Mặc dù mỗi cây cầu được xây từ một đảo tới một đảo khác, hiện nay tất cả các cây cầu đều có thể đi theo cả hai chiều. Ngoài ra, giữa mỗi cặp đảo có đúng một tuyến phà đi lại theo cả hai chiều.

Bạn thích đi bộ hơn đi phà, nên muốn tối đa hóa tổng độ dài các cây cầu đã đi qua, đồng thời tuân thủ những quy tắc sau:

• Bạn có thể bắt đầu chuyến tham quan tại một đảo tùy ý.
• Bạn không được ghé thăm bất kỳ đảo nào quá một lần.
• Tại một thời điểm bất kỳ, bạn có thể di chuyển từ đảo hiện tại \(S\) tới một đảo \(D\) chưa từng ghé thăm, bằng một trong hai cách:
  • Đi bộ: chỉ thực hiện được khi có một cây cầu nối hai đảo. Độ dài cây cầu được cộng vào tổng quãng đường đã đi bộ.
  • Đi phà: chỉ được chọn cách này nếu không thể đi từ \(S\) tới \(D\) bằng bất kỳ cách kết hợp nào giữa các cây cầu và những tuyến phà đã sử dụng trước đó. Khi kiểm tra khả năng đi tới \(D\), phải xét mọi đường đi, kể cả những đường đi qua các đảo mà bạn đã ghé thăm.

Bạn không bắt buộc phải ghé thăm tất cả các đảo, và cũng có thể không đi qua được tất cả các cây cầu.

Cho thông tin về \(N\) cây cầu và độ dài của chúng, hãy tính tổng quãng đường đi bộ lớn nhất có thể đạt được khi tuân thủ các quy tắc trên.

Dữ liệu vào

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

• Dòng đầu tiên chứa số nguyên \(N\), là số đảo trong công viên. Các đảo được đánh số từ \(1\) đến \(N\).
• Mỗi dòng trong \(N\) dòng tiếp theo mô tả một cây cầu. Dòng thứ \(i\) trong số này mô tả cây cầu được xây từ đảo \(i\), gồm hai số nguyên cách nhau bởi một dấu cách: số thứ nhất là số hiệu đảo ở đầu cầu còn lại, số thứ hai là độ dài \(L_i\) của cây cầu.

Hai đầu của mỗi cây cầu luôn nằm trên hai đảo khác nhau. Có thể có hai cây cầu khác nhau nối cùng một cặp đảo.

Dữ liệu ra

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

Kết quả của một số bộ kiểm thử không biểu diễn được bằng số nguyên \(32\) bit. Để xử lý đầy đủ các trường hợp, có thể cần dùng int64 trong Pascal hoặc long long trong C/C++. Các giá trị đọc từ đầu vào đều nằm trong phạm vi số nguyên \(32\) bit.

Ràng buộc

• \(2 \le N \le 1\,000\,000\).
• \(1 \le L_i \le 100\,000\,000\) với mọi \(1 \le i \le N\).
• Đảo ở đầu cầu còn lại có số hiệu trong đoạn \([1,N]\) và khác \(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 đó.

Mỗi nhóm có trọng số 1. Có 19 nhóm tính điểm; điểm cuối cùng bằng \(100 \times W / 19\), với \(W\) là tổng trọng số các nhóm đạt. Mỗi nhóm đạt đóng góp chính xác \(100/19\) điểm; không làm tròn riêng từng 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: isl/isl0.in.

Ví dụ

7
3 8
7 2
4 2
1 4
1 9
3 4
2 3

24

Nguồn

IOI 2008.

Scheherazade kể rằng ở một nơi xa xôi giữa sa mạc có một hồ nước. Ban đầu, hồ có \(F\) con cá. Người ta chọn ra \(K\) loại đá quý trong số những loại quý giá nhất trên Trái Đất và cho mỗi con cá nuốt đúng một viên đá quý. Vì \(K\) có thể nhỏ hơn \(F\), hai hoặc nhiều con cá có thể nuốt đá quý cùng loại.

Theo thời gian, một số con cá đã ăn những con cá khác. Một con cá có thể ăn một con khác khi và chỉ khi chiều dài của nó ít nhất gấp đôi chiều dài con kia: cá \(A\) có thể ăn cá \(B\) khi và chỉ khi \(L_A \ge 2L_B\). Không có quy định về thời điểm cá quyết định ăn. Một con cá có thể lần lượt ăn nhiều con cá nhỏ hơn, trong khi một số con có thể không ăn con nào dù có khả năng ăn. Khi một con cá ăn một con nhỏ hơn, chiều dài của nó không thay đổi, nhưng tất cả đá quý trong bụng con cá nhỏ hơn được chuyển nguyên vẹn vào bụng nó.

Scheherazade nói rằng nếu tìm được hồ, bạn sẽ được bắt đúng một con cá và giữ lại tất cả đá quý trong bụng nó. Bạn muốn thử vận may, nhưng trước khi lên đường, bạn muốn biết có bao nhiêu tổ hợp đá quý khác nhau có thể thu được khi bắt một con cá.

Cho chiều dài mỗi con cá và loại đá quý mà nó nuốt ban đầu, hãy tính số tổ hợp đá quý khác nhau có thể xuất hiện trong bụng một con cá bất kỳ, lấy phần dư khi chia cho số nguyên \(M\) đã cho. Một tổ hợp chỉ được xác định bởi số lượng đá quý thuộc từng loại trong \(K\) loại. Thứ tự các viên đá không có ý nghĩa, và hai viên đá cùng loại không thể phân biệt với nhau.

Dữ liệu vào

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

• Dòng thứ nhất chứa số nguyên \(F\), là số cá ban đầu trong hồ.
• Dòng thứ hai chứa số nguyên \(K\), là số loại đá quý. Các loại đá quý được đánh số từ \(1\) đến \(K\).
• Dòng thứ ba chứa số nguyên \(M\).
• Mỗi dòng trong \(F\) dòng tiếp theo mô tả một con cá bằng hai số nguyên cách nhau bởi một dấu cách: chiều dài của con cá, tiếp theo là loại đá quý mà nó nuốt ban đầu.

Dữ liệu bảo đảm ban đầu có ít nhất một viên đá quý thuộc mỗi loại trong \(K\) loại.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên trong đoạn \([0,M-1]\): phần dư khi chia số tổ hợp đá quý khác nhau có thể thu được cho \(M\).

Giá trị \(M\) chỉ được dùng để đơn giản hóa việc tính toán bằng cách lấy phần dư; nó không ảnh hưởng đến những tổ hợp nào có thể thu được.

Ràng buộc

• \(1 \le F \le 500\,000\).
• \(1 \le K \le F\).
• \(2 \le M \le 30\,000\).
• \(1 \le L_X \le 1\,000\,000\,000\) với mỗi con cá \(X\).
• Loại đá quý ban đầu của mỗi con cá thuộc đoạn \([1,K]\), và mỗi loại xuất hiện ít nhất một lần.

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: fsh/fsh0.in.

Ví dụ

5
3
7
2 2
5 1
8 3
4 1
2 3

4

Nguồn

IOI 2008.