IOI 2009 - Ngày 2

Một bãi đỗ xe có \(N\) chỗ đỗ, được đánh số từ \(1\) đến \(N\). Mỗi sáng, khi mở cửa, bãi chưa có xe nào và hoạt động trong ngày theo quy tắc sau. Mỗi khi một xe đến, nhân viên kiểm tra xem còn chỗ trống hay không. Nếu không còn, xe phải chờ ở lối vào cho đến khi có một chỗ được giải phóng. Nếu có chỗ trống, hoặc ngay khi có một chỗ trở nên trống, xe được đưa vào chỗ đó. Nếu có nhiều chỗ trống, xe được đưa vào chỗ có số hiệu nhỏ nhất. Nếu có thêm xe đến trong khi đã có xe đang chờ, các xe xếp thành một hàng ở lối vào theo thứ tự đến. Khi có chỗ trống, xe ở đầu hàng, tức là xe đến sớm nhất trong số các xe đang chờ, được đưa vào chỗ đó.

Phí đỗ xe, tính bằng đô la, bằng khối lượng của xe tính bằng kilôgam nhân với đơn giá của chỗ đỗ mà xe sử dụng. Phí không phụ thuộc vào thời gian xe ở trong bãi.

Người quản lý biết hôm nay sẽ có \(M\) xe đến và biết thứ tự các xe đến và rời bãi. Hãy giúp người đó tính tổng doanh thu trong ngày, tính bằng đô la.

Cho đơn giá của các chỗ đỗ, khối lượng các xe và thứ tự các xe đến và rời bãi, hãy viết chương trình xác định tổng doanh thu của bãi đỗ xe.

Dữ liệu vào

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

• Dòng đầu chứa hai số nguyên \(N\) và \(M\), cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo mô tả đơn giá của các chỗ đỗ. Dòng thứ \(s\) trong số này chứa một số nguyên \(R_s\), là đơn giá của chỗ đỗ số \(s\), tính bằng đô la trên kilôgam.
• \(M\) dòng tiếp theo mô tả khối lượng của các xe. Các xe được đánh số từ \(1\) đến \(M\) theo thứ tự tùy ý. Dòng thứ \(k\) trong số này chứa một số nguyên \(W_k\), là khối lượng của xe số \(k\), tính bằng kilôgam.
• \(2M\) dòng tiếp theo mô tả các lần đến và rời bãi của tất cả các xe theo thứ tự thời gian. Mỗi dòng chứa một số nguyên: số dương \(i\) cho biết xe số \(i\) đến bãi; số âm \(-i\) cho biết xe số \(i\) rời bãi. Không xe nào rời bãi trước khi đến. Mỗi xe từ \(1\) đến \(M\) xuất hiện đúng hai lần trong dãy này, một lần đến và một lần rời bãi. Hơn nữa, không xe nào rời bãi trước khi đã được đỗ vào một chỗ, tức là không xe nào bỏ đi khi vẫn đang chờ trong hàng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: tổng số đô la mà người quản lý bãi đỗ xe thu được trong ngày hôm nay.

Ràng buộc

• \(1 \le N \le 100\): số chỗ đỗ xe.
• \(1 \le M \le 2\,000\): số xe.
• \(1 \le R_s \le 100\) với \(1 \le s \le N\): đơn giá của chỗ đỗ số \(s\), tính bằng đô la trên kilôgam.
• \(1 \le W_k \le 10\,000\) với \(1 \le k \le M\): khối lượng xe số \(k\), tính bằng kilôgam.

Phân nhóm

Một số bộ dữ liệu có tổng cộng \(40\) điểm bảo đảm rằng mỗi khi một xe đến, luôn có ít nhất một chỗ đỗ còn trống. Trong các bộ dữ liệu này, không xe nào phải chờ chỗ đỗ.

Ví dụ

3 4
2
3
5
200
100
300
800
3
2
-3
1
4
-4
-2
-1

5300

2 4
5
2
100
500
1000
2000
3
1
2
4
-1
-3
-2
-4

16200

Nguồn

IOI 2009, ngày thi thứ hai: Garage, bản tiếng Anh 1.2. Tác giả đề bài: Carl Hultquist. Tập đề bài và lời giải IOI 2009.

Chú gấu Mecho vừa tìm thấy một kho báu nhỏ: hũ mật bí mật của bầy ong, chứa đầy mật! Mecho đang vui vẻ thưởng thức thì bất ngờ bị một con ong phát hiện và báo động. Mecho biết rằng ngay lúc này, những đàn ong sẽ xuất hiện từ các tổ và bắt đầu lan khắp nơi để tìm bắt mình. Mecho phải rời hũ mật và nhanh chóng về nhà, nhưng mật quá ngọt nên chú không muốn rời đi quá sớm. Hãy giúp Mecho xác định thời điểm muộn nhất mà chú có thể rời đi.

Khu rừng của Mecho được biểu diễn bằng một lưới vuông gồm \(N \times N\) ô đơn vị, có các cạnh song song với các hướng bắc - nam và đông - tây. Mỗi ô chứa một cái cây, một bãi cỏ, một tổ ong hoặc nhà của Mecho. Hai ô được xem là kề nhau nếu một ô nằm ngay phía bắc, nam, đông hoặc tây của ô kia; các ô chỉ tiếp xúc theo đường chéo không kề nhau. Mecho khá vụng về nên mỗi bước phải đi sang một ô kề. Mecho chỉ có thể đi trên cỏ, không thể đi xuyên qua cây hoặc tổ ong, và có thể đi tối đa \(S\) bước mỗi phút.

Tại thời điểm báo động vang lên, Mecho đang ở ô cỏ chứa hũ mật, còn ong đang ở tất cả các ô chứa tổ ong; trong rừng có thể có nhiều tổ. Trong mỗi phút kể từ thời điểm này, các sự kiện diễn ra theo đúng thứ tự sau:

1. Nếu Mecho vẫn đang ăn mật, chú quyết định tiếp tục ăn hay rời đi. Nếu tiếp tục ăn, chú không di chuyển trong cả phút đó. Nếu rời đi, chú lập tức di chuyển tối đa \(S\) bước trong rừng theo quy tắc trên. Mecho không thể mang mật theo, nên một khi đã di chuyển, chú không thể ăn mật nữa.
2. Sau khi Mecho đã ăn hoặc di chuyển xong trong cả phút đó, ong lan thêm một ô trên lưới và chỉ lan vào các ô cỏ. Cụ thể, ong lan vào mọi ô cỏ kề với bất kỳ ô nào đã có ong. Khi một ô đã có ong, ô đó sẽ luôn có ong về sau; nghĩa là vùng có ong lớn dần chứ không chuyển từ nơi này sang nơi khác.

Nói cách khác, khi báo động vang lên, ong chỉ chiếm các ô có tổ. Cuối phút thứ nhất, ong chiếm tất cả các ô cỏ kề với tổ ong, đồng thời vẫn ở trong các tổ. Cuối phút thứ hai, ong chiếm thêm mọi ô cỏ kề với các ô cỏ kề tổ ong, và cứ thế tiếp tục. Sau đủ thời gian, ong sẽ đồng thời chiếm tất cả các ô cỏ trong rừng mà chúng có thể tới được.

Cả Mecho lẫn ong đều không thể ra ngoài khu rừng. Theo các quy tắc trên, thời gian Mecho ăn mật luôn là một số nguyên phút. Mecho bị bắt nếu tại bất kỳ thời điểm nào chú ở trong một ô có ong.

Cho bản đồ khu rừng, hãy viết chương trình xác định số phút lớn nhất mà Mecho có thể tiếp tục ăn mật tại vị trí ban đầu nhưng vẫn về tới nhà trước khi bị ong bắt.

Dữ liệu vào

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

• Dòng đầu chứa hai số nguyên \(N\) và \(S\), cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo mô tả bản đồ khu rừng. Mỗi dòng chứa \(N\) ký tự, mỗi ký tự biểu diễn một ô đơn vị của lưới.

Các ký tự có ý nghĩa như sau:

Bản đồ được bảo đảm có đúng một ký tự M, đúng một ký tự D và ít nhất một ký tự H. Ngoài ra, tồn tại một dãy các ô G liên tiếp kề nhau nối Mecho với nhà, và một dãy các ô G liên tiếp kề nhau nối ít nhất một tổ ong với hũ mật, tức vị trí ban đầu của Mecho. Các dãy này có thể có độ dài bằng \(0\) nếu nhà của Mecho hoặc một tổ ong nằm kề vị trí ban đầu của chú. Ong không thể đi xuyên qua hoặc bay qua nhà của Mecho; đối với chúng, nhà cũng giống như một cái cây.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: số phút lớn nhất mà Mecho có thể tiếp tục ăn mật tại vị trí ban đầu mà vẫn về nhà an toàn.

Nếu Mecho không thể về tới nhà trước khi bị ong bắt, kể cả khi rời đi ngay lập tức, hãy in \(-1\).

Ràng buộc

• \(1 \le N \le 800\): độ dài cạnh của bản đồ.
• \(1 \le S \le 1\,000\): số bước tối đa Mecho có thể đi trong mỗi phút.

Phân nhóm

Một số bộ dữ liệu có tổng cộng \(40\) điểm thỏa mãn \(N \le 60\).

Ví dụ

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT

1

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
TGHHGGT

2

Nguồn

IOI 2009, ngày thi thứ hai: Mecho, bản tiếng Anh 1.1. Tác giả đề bài: Carl Hultquist. Tập đề bài và lời giải IOI 2009.

Cơ quan Phát triển Khu vực của Liên Hợp Quốc (UNRDA) có một cơ cấu tổ chức được xác định rất rõ ràng. Cơ quan có tổng cộng \(N\) nhân viên, mỗi người đến từ một trong \(R\) khu vực địa lý khác nhau trên thế giới. Các nhân viên được đánh số từ \(1\) đến \(N\) theo thứ tự thâm niên, trong đó nhân viên số \(1\), Chủ tịch, có thâm niên cao nhất. Các khu vực được đánh số từ \(1\) đến \(R\) theo thứ tự tùy ý. Mỗi nhân viên, trừ Chủ tịch, có đúng một cấp trên trực tiếp. Cấp trên trực tiếp luôn có thâm niên cao hơn những nhân viên dưới quyền trực tiếp của mình.

Ta nói nhân viên \(A\) là người quản lý của nhân viên \(B\) khi và chỉ khi \(A\) là cấp trên trực tiếp của \(B\), hoặc \(A\) là người quản lý của cấp trên trực tiếp của \(B\). Chẳng hạn, Chủ tịch là người quản lý của mọi nhân viên khác. Rõ ràng không thể có hai nhân viên là người quản lý của nhau.

Gần đây, Cục Điều tra Liên Hợp Quốc (UNBI) nhận được một số khiếu nại rằng cơ cấu tổ chức của UNRDA thiếu cân bằng và ưu ái một số khu vực hơn những khu vực khác. Để điều tra, UNBI muốn xây dựng một hệ thống máy tính nhận thông tin về cơ cấu cấp trên của UNRDA, rồi trả lời các truy vấn sau: với hai khu vực khác nhau \(r_1\) và \(r_2\), có bao nhiêu cặp nhân viên \((e_1,e_2)\) sao cho \(e_1\) đến từ khu vực \(r_1\), \(e_2\) đến từ khu vực \(r_2\), và \(e_1\) là người quản lý của \(e_2\)? Mỗi truy vấn có hai tham số \(r_1,r_2\) và kết quả là một số nguyên: số cặp nhân viên khác nhau thỏa mãn các điều kiện trên.

Cho khu vực quê quán của từng nhân viên và thông tin về cấp trên trực tiếp, hãy viết chương trình tương tác để trả lời các truy vấn như trên.

Dữ liệu vào

Trước tiên, đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(N\), \(R\), \(Q\), theo thứ tự này, cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo mô tả các nhân viên theo thứ tự thâm niên. Dòng thứ \(k\) trong số này mô tả nhân viên số \(k\). Dòng đầu tiên, mô tả Chủ tịch, chỉ chứa một số nguyên \(H_1\), là khu vực quê quán của Chủ tịch. Mỗi dòng còn lại chứa hai số nguyên cách nhau bởi một dấu cách: \(S_k\), số hiệu cấp trên trực tiếp của nhân viên \(k\), và \(H_k\), khu vực quê quán của nhân viên \(k\).

Tương tác

Sau khi đọc dữ liệu ban đầu, chương trình phải luân phiên đọc truy vấn từ đầu vào chuẩn và ghi câu trả lời ra đầu ra chuẩn. Phải trả lời lần lượt từng truy vấn trong số \(Q\) truy vấn: chương trình phải gửi câu trả lời cho truy vấn đã nhận trước khi có thể nhận truy vấn tiếp theo.

Mỗi truy vấn được đưa trên một dòng của đầu vào chuẩn, gồm hai số nguyên khác nhau \(r_1\) và \(r_2\), cách nhau bởi một dấu cách.

Dữ liệu ra

Với mỗi truy vấn, ghi ra đầu ra chuẩn một dòng chứa một số nguyên: số cặp nhân viên \((e_1,e_2)\) của UNRDA sao cho khu vực quê quán của \(e_1\) là \(r_1\), khu vực quê quán của \(e_2\) là \(r_2\), và \(e_1\) là người quản lý của \(e_2\).

Dữ liệu bảo đảm rằng đáp án đúng cho mọi truy vấn được đưa trên đầu vào chuẩn luôn nhỏ hơn \(1\,000\,000\,000\).

Chú ý: Để tương tác đúng với chương trình chấm, bạn phải đẩy hết dữ liệu trong bộ đệm đầu ra chuẩn (flush) sau mỗi câu trả lời. Trong C hoặc C++ dùng scanf/printf, thực hiện fflush(stdout);; trong C++ dùng cin/cout, thực hiện cout << flush;; trong Pascal, thực hiện flush(output);.

Bạn cũng phải tránh làm chương trình bị chặn khi đọc đầu vào chuẩn. Khi dùng scanf, không kết thúc chuỗi định dạng bằng dấu cách hoặc ký tự xuống dòng: có thể dùng "%d", nhưng không dùng "%d " hay "%d\n". Chẳng hạn, lời gọi scanf("%d\n", &x) có thể khiến chương trình bị chặn. Các quy tắc này được trình bày trong tài liệu thông tin kỹ thuật của kỳ thi.

Ràng buộc

• \(1 \le N \le 200\,000\): số nhân viên.
• \(1 \le R \le 25\,000\): số khu vực.
• \(1 \le Q \le 200\,000\): số truy vấn chương trình phải trả lời.
• \(1 \le H_k \le R\) với \(1 \le k \le N\): khu vực quê quán của nhân viên \(k\).
• \(1 \le S_k < k\) với \(2 \le k \le N\): cấp trên trực tiếp của nhân viên \(k\).
• \(1 \le r_1,r_2 \le R\) và \(r_1 \ne r_2\): hai khu vực được hỏi trong một truy vấn.

Phân nhóm

Một số bộ dữ liệu có tổng cộng \(30\) điểm thỏa mãn \(R \le 500\).

Một số bộ dữ liệu có tổng cộng \(55\) điểm thỏa mãn điều kiện không khu vực nào có quá \(500\) nhân viên.

Các bộ dữ liệu thỏa mãn cả hai điều kiện trên có tổng cộng \(15\) điểm.

Các bộ dữ liệu thỏa mãn ít nhất một trong hai điều kiện trên có tổng cộng \(70\) điểm.

Ví dụ

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

1
3
2
1

Nguồn

IOI 2009, ngày thi thứ hai: Regions, bản tiếng Anh 1.2. Tác giả đề bài: Long Fan và Richard Peng. Tập đề bài, thông tin kỹ thuật và lời giải IOI 2009.

Một người bán hàng lưu động nhận thấy việc lập lịch trình tối ưu cho các chuyến đi trên đất liền là một bài toán tính toán quá khó, nên quyết định chuyển việc kinh doanh sang thế giới một chiều của sông Danube. Ông có một chiếc thuyền rất nhanh, có thể đi từ bất kỳ điểm nào đến bất kỳ điểm nào khác trên sông mà không mất thời gian, nhưng tiếc là thuyền tiêu tốn rất nhiều nhiên liệu. Mỗi mét đi ngược dòng, tức hướng về đầu nguồn, tốn \(U\) đô la; mỗi mét đi xuôi dòng, tức ra xa đầu nguồn, tốn \(D\) đô la.

Có \(N\) hội chợ dọc theo sông mà người bán hàng muốn tham dự. Mỗi hội chợ chỉ diễn ra trong một ngày. Với mỗi hội chợ \(X\), ông biết ngày tổ chức \(T_X\), tính bằng số ngày kể từ khi mua thuyền; vị trí \(L_X\), tính bằng khoảng cách theo mét từ đầu nguồn xuôi theo dòng sông tới hội chợ; và số tiền \(M_X\) đô la mà ông sẽ thu được nếu tham dự. Hành trình của ông phải bắt đầu và kết thúc tại ngôi nhà bên sông của mình, ở vị trí \(S\), cũng được đo bằng số mét từ đầu nguồn theo chiều xuôi dòng.

Hãy giúp người bán hàng chọn những hội chợ cần tham dự, hoặc không tham dự hội chợ nào, và thứ tự tham dự để lợi nhuận khi kết thúc hành trình là lớn nhất. Tổng lợi nhuận bằng tổng số đô la thu được từ các hội chợ đã tham dự, trừ tổng số đô la chi cho việc đi lại ngược và xuôi dòng.

Lưu ý rằng nếu hội chợ \(A\) diễn ra trước hội chợ \(B\), người bán hàng chỉ có thể tham dự cả hai theo thứ tự \(A\) rồi \(B\), không thể tham dự \(B\) rồi mới đến \(A\). Tuy nhiên, nếu hai hội chợ diễn ra cùng ngày, ông có thể tham dự cả hai theo thứ tự bất kỳ. Không có giới hạn về số hội chợ có thể tham dự trong một ngày, nhưng không thể tham dự lại cùng một hội chợ để nhận tiền lần thứ hai. Ông có thể đi qua những hội chợ đã tham dự, nhưng không nhận thêm tiền.

Cho ngày tổ chức, vị trí và số tiền thu được của tất cả các hội chợ, cùng vị trí nhà và chi phí đi lại, hãy viết chương trình xác định lợi nhuận lớn nhất có thể đạt được khi kết thúc hành trình.

Dữ liệu vào

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

• Dòng đầu chứa bốn số nguyên \(N\), \(U\), \(D\), \(S\), theo đúng thứ tự này, cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo mô tả \(N\) hội chợ theo thứ tự tùy ý. Dòng thứ \(k\) trong số này mô tả hội chợ thứ \(k\), gồm ba số nguyên cách nhau bởi một dấu cách: ngày tổ chức \(T_k\), vị trí \(L_k\) và số tiền người bán hàng thu được khi tham dự \(M_k\).

Tất cả các vị trí trong dữ liệu vào đều khác nhau. Nghĩa là không có hai hội chợ nào diễn ra tại cùng một vị trí, và không có hội chợ nào diễn ra tại nhà của người bán hàng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: lợi nhuận lớn nhất mà người bán hàng có thể đạt được khi kết thúc hành trình.

Ràng buộc

• \(1 \le N \le 500\,000\): số hội chợ.
• \(1 \le D \le U \le 10\): chi phí đi một mét ngược dòng (\(U\)) hoặc xuôi dòng (\(D\)).
• \(1 \le S \le 500\,001\): vị trí nhà của người bán hàng.
• \(1 \le T_k \le 500\,000\) với \(1 \le k \le N\): ngày tổ chức hội chợ thứ \(k\).
• \(1 \le L_k \le 500\,001\) với \(1 \le k \le N\): vị trí hội chợ thứ \(k\).
• \(1 \le M_k \le 4\,000\) với \(1 \le k \le N\): số đô la thu được khi tham dự hội chợ thứ \(k\).

Phân nhóm

Một số bộ dữ liệu có tổng cộng \(60\) điểm thỏa mãn điều kiện không có hai hội chợ nào diễn ra cùng ngày.

Một số bộ dữ liệu có tổng cộng \(40\) điểm thỏa mãn điều kiện không có số nào trong dữ liệu vào vượt quá \(5\,000\).

Các bộ dữ liệu thỏa mãn cả hai điều kiện trên có tổng cộng \(15\) điểm.

Các bộ dữ liệu thỏa mãn ít nhất một trong hai điều kiện trên có tổng cộng \(85\) điểm.

Ví dụ

4 5 3 100
2 80 100
20 125 130
10 75 150
5 120 110

50

Nguồn

IOI 2009, ngày thi thứ hai: Salesman, bản tiếng Anh 1.2. Tác giả đề bài: Velin Tzanov. Tập đề bài và lời giải IOI 2009.