JOI 2010/2011 - Vòng chung kết

Sau một hành trình dài, con tàu di dân xuyên không gian và thời gian chở bạn cuối cùng đã tìm thấy một hành tinh có vẻ thích hợp để sinh sống. Hành tinh được đặt tên là JOI; đúng như tên gọi, đây là một hành tinh khắc nghiệt với ba loại địa hình đan xen: rừng rậm (Jungle), biển (Ocean) và băng (Ice). Sau một cuộc khảo sát sơ bộ, bản đồ khu vực dự định định cư đã được lập.

Khu vực dự định định cư có dạng hình chữ nhật, dài \(M\) km theo hướng bắc–nam và \(N\) km theo hướng đông–tây, được chia thành các ô vuông có cạnh \(1\) km. Có tất cả \(MN\) ô. Ô ở hàng thứ \(p\) tính từ phía bắc và cột thứ \(q\) tính từ phía tây được ký hiệu là \((p,q)\). Ô ở góc tây bắc là \((1,1)\), còn ô ở góc đông nam là \((M,N)\). Mỗi ô có đúng một trong ba loại địa hình: rừng rậm, biển hoặc băng, lần lượt được biểu diễn bằng các chữ cái J, O, I.

Để lập kế hoạch định cư chi tiết, bạn cần khảo sát \(K\) vùng hình chữ nhật, đếm số ô rừng rậm, biển và băng trong mỗi vùng.

Yêu cầu

Cho thông tin về khu vực dự định định cư và các vùng cần khảo sát, hãy viết chương trình tính số ô thuộc từng loại địa hình trong mỗi vùng.

Dữ liệu vào

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

• Dòng đầu tiên chứa hai số nguyên \(M,N\), cách nhau bởi dấu cách, cho biết kích thước khu vực theo hướng bắc–nam và đông–tây, tính bằng km.
• Dòng thứ hai chứa số nguyên \(K\), là số vùng cần khảo sát.
• \(M\) dòng tiếp theo mô tả khu vực. Dòng \(i+2\) (\(1\le i\le M\)) chứa một chuỗi gồm \(N\) ký tự J, O, I, biểu diễn địa hình của \(N\) ô ở hàng thứ \(i\) tính từ phía bắc.
• \(K\) dòng tiếp theo mô tả các vùng cần khảo sát. Dòng \(j+M+2\) (\(1\le j\le K\)) chứa bốn số nguyên dương \(a_j,b_j,c_j,d_j\), cách nhau bởi dấu cách. Ô \((a_j,b_j)\) là góc tây bắc và ô \((c_j,d_j)\) là góc đông nam của vùng thứ \(j\). Các ô trên biên cũng thuộc vùng khảo sát.

Dữ liệu ra

Ghi ra đầu ra chuẩn \(K\) dòng. Dòng thứ \(j\) chứa ba số nguyên, cách nhau bởi dấu cách, lần lượt là số ô rừng rậm (J), biển (O) và băng (I) trong vùng khảo sát thứ \(j\).

Ràng buộc

• \(1\le M\le1000\).
• \(1\le N\le1000\).
• \(1\le K\le100000\).
• \(1\le a_j\le c_j\le M\) và \(1\le b_j\le d_j\le N\) với mọi \(1\le j\le K\).
• Giới hạn thời gian: \(0.5\) giây. Giới hạn bộ nhớ: \(64\) MB.

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 điều kiện điểm thành phần dưới đây có thể chồng lấp:

• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(M\le50\) và \(K\le100\).
• Các bộ dữ liệu chiếm \(50\%\) tổng số điểm thỏa mãn \(M\le50\).

Ví dụ

4 7
4
JIOJOIJ
IOJOIJO
JOIJOOI
OOJJIJO
3 5 4 7
2 2 3 6
2 2 2 2
1 1 4 7

1 3 2
3 5 2
0 1 0
10 11 7

Trong thị trấn của bạn có một hiệu sách cũ lâu đời mang tên JOI mà bạn thường xuyên ghé thăm. Mỗi cuốn sách có một giá cơ bản xác định, và hiệu sách JOI sẽ mua lại cuốn sách với giá đó.

Hiệu sách phân loại sách thành \(10\) thể loại, chẳng hạn như tiểu thuyết, truyện tranh và tạp chí. Các thể loại được đánh số từ \(1\) đến \(10\). Hiệu sách có dịch vụ mua lại với giá cao hơn nếu bạn bán cùng lúc nhiều cuốn sách thuộc cùng một thể loại. Cụ thể, nếu bán cùng lúc \(T\) cuốn sách thuộc một thể loại, giá mua lại của mỗi cuốn trong số đó sẽ cao hơn giá cơ bản của nó \(T-1\) yên. Ví dụ, nếu bán cùng lúc ba cuốn sách cùng thể loại có giá cơ bản lần lượt là \(100\), \(120\), \(150\) yên, giá mua lại tương ứng sẽ là \(102\), \(122\), \(152\) yên.

Vì lý do cá nhân, bạn đột ngột phải chuyển nhà. Bạn có \(N\) cuốn sách, nhưng khó có thể mang tất cả đến nơi ở mới, nên quyết định bán đúng \(K\) cuốn trong số đó cho hiệu sách JOI.

Yêu cầu

Cho giá cơ bản và số hiệu thể loại của từng cuốn sách, hãy viết chương trình tính tổng số tiền lớn nhất có thể nhận được khi bán sách.

Dữ liệu vào

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

• Dòng đầu tiên chứa hai số nguyên \(N,K\), cách nhau bởi dấu cách, cho biết bạn có \(N\) cuốn sách và sẽ bán \(K\) cuốn.
• \(N\) dòng tiếp theo mô tả các cuốn sách. Dòng \(i+1\) (\(1\le i\le N\)) chứa hai số nguyên \(C_i,G_i\), cách nhau bởi dấu cách, lần lượt là giá cơ bản và số hiệu thể loại của cuốn sách thứ \(i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: tổng số tiền lớn nhất có thể nhận được khi bán sách.

Ràng buộc

• \(2\le N\le2000\).
• \(1\le K<N\).
• \(1\le C_i\le100000=10^5\) với mọi \(1\le i\le N\).
• \(1\le G_i\le10\) với mọi \(1\le i\le N\).
• Giới hạn thời gian: \(1\) giây. Giới hạn bộ nhớ: \(64\) MB.

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 điều kiện điểm thành phần dưới đây có chồng lấp:

• Các bộ dữ liệu chiếm \(20\%\) tổng số điểm thỏa mãn \(N\le20\).
• Các bộ dữ liệu chiếm \(20\%\) tổng số điểm thỏa mãn \(G_i\in\{1,2\}\) với mọi \(1\le i\le N\).
• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm đồng thời thỏa mãn \(N\le20\) và \(G_i\in\{1,2\}\) với mọi \(1\le i\le N\).
• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn ít nhất một trong hai điều kiện: \(N\le20\); hoặc \(G_i\in\{1,2\}\) với mọi \(1\le i\le N\).

Ví dụ

7 4
14 1
13 2
12 3
14 2
8 2
16 3
11 2

60

Vương quốc JOI có \(N\) thị trấn, được nối với nhau bằng \(M\) con đường hai chiều. Có trung tâm mua sắm tại \(K\) thị trấn; người dân đi theo các con đường đến một trong những thị trấn đó để mua sắm.

Tùy vào vị trí ngôi nhà, người dân có thể phải đi một quãng đường rất dài để mua sắm, gây nhiều bất tiện. Để nắm rõ tình hình, nhà vua muốn biết khoảng cách ngắn nhất từ nhà đến một thị trấn có trung tâm mua sắm có thể lớn đến mức nào. Nhà có thể được xây ở giữa một con đường (xem giải thích ví dụ 1), khiến việc khảo sát trở nên rất khó khăn. Vì vậy, nhà vua nhờ bạn, một lập trình viên tài giỏi, viết chương trình thực hiện cuộc khảo sát này.

Yêu cầu

Cho thông tin về các con đường và các thị trấn có trung tâm mua sắm, hãy tìm giá trị lớn nhất của khoảng cách ngắn nhất từ một điểm trên đường đến một thị trấn có trung tâm mua sắm. Xét tất cả các điểm trên đường, kể cả hai đầu mút. Có thể bỏ qua khoảng cách di chuyển bên trong mỗi thị trấn.

Dữ liệu vào

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

• Dòng đầu tiên chứa ba số nguyên \(N,M,K\), cách nhau bởi dấu cách, lần lượt là số thị trấn, số con đường và số thị trấn có trung tâm mua sắm. Các thị trấn được đánh số \(1,2,\ldots,N\).
• \(M\) dòng tiếp theo mô tả các con đường. Dòng \(i+1\) (\(1\le i\le M\)) chứa ba số nguyên \(a_i,b_i,l_i\), cách nhau bởi dấu cách, cho biết con đường thứ \(i\) nối thị trấn \(a_i\) với thị trấn \(b_i\) và có chiều dài \(l_i\). Hai đầu của một con đường không cùng thuộc một thị trấn. Giữa hai thị trấn bất kỳ có nhiều nhất một con đường nối trực tiếp. Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác bằng cách đi qua một số con đường.
• \(K\) dòng tiếp theo mô tả vị trí các trung tâm mua sắm. Dòng \(i+M+1\) (\(1\le i\le K\)) chứa một số nguyên \(s_i\), cho biết thị trấn \(s_i\) có trung tâm mua sắm. Các giá trị \(s_1,\ldots,s_K\) đôi một khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên: giá trị lớn nhất của khoảng cách ngắn nhất đến một thị trấn có trung tâm mua sắm, sau khi làm tròn đến số nguyên gần nhất. Nếu phần thập phân bằng \(0.5\), làm tròn lên.

Ràng buộc

• \(2\le N\le3000\).
• \(1\le M\le100000=10^5\).
• \(1\le K\le N\).
• \(1\le a_i,b_i\le N\) và \(a_i\ne b_i\) với mọi \(1\le i\le M\).
• \(1\le l_i\le1000\) với mọi \(1\le i\le M\).
• \(1\le s_i\le N\) với mọi \(1\le i\le K\).
• Giới hạn thời gian: \(0.5\) giây. Giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) nhóm dữ liệu, mỗi nhóm \(10\) điểm. Mỗi nhóm gồm nhiều bộ dữ liệu; chỉ nhận được điểm của nhóm nếu trả lời đúng tất cả các bộ dữ liệu trong nhóm đó.

• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn \(K=1\).

Ví dụ

3 3 1
1 2 1
2 3 1
3 1 1
1

2

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

3

Cuối năm ngoái, ông già Noel quên tặng quà Giáng sinh cho các em nhỏ ở làng JOI. Để xin lỗi, ông quyết định mang bánh sô-cô-la đến cho các em. Ngày giao bánh đã là ngày mai, nên ông cần sớm lập kế hoạch di chuyển.

Làng JOI được chia thành một lưới ô vuông bởi \(W\) con đường thẳng theo hướng bắc–nam và \(H\) con đường thẳng theo hướng đông–tây. Các con đường bắc–nam được đánh số \(1,2,\ldots,W\) từ tây sang đông; các con đường đông–tây được đánh số \(1,2,\ldots,H\) từ nam lên bắc. Giao điểm của con đường bắc–nam thứ \(x\) tính từ phía tây và con đường đông–tây thứ \(y\) tính từ phía nam được ký hiệu là \((x,y)\).

Trong làng có \(N\) ngôi nhà, mỗi ngôi nhà nằm tại một giao điểm. Ông già Noel chỉ được di chuyển dọc theo các con đường. Thời gian đi giữa hai giao điểm kề nhau là \(1\).

Mọi ngôi nhà trong làng đều có trẻ em, nên ông già Noel phải giao đúng một chiếc bánh sô-cô-la đến mỗi nhà. Mang những chiếc bánh quý giá bay trên trời cùng tuần lộc có phần nguy hiểm, nên ông và tuần lộc sẽ hạ cánh tại một giao điểm trong làng, rồi ông đi bộ từ đó để giao bánh. Ông không đi bộ mang theo từ hai chiếc bánh trở lên cùng lúc. Vì vậy, sau mỗi lần giao bánh cho một nhà, ông quay về giao điểm đã hạ cánh.

Ông già Noel muốn chọn kế hoạch có tổng thời gian từ lúc hạ cánh đến khi giao xong bánh cho tất cả các nhà là nhỏ nhất. Lưu ý rằng thời gian quay về giao điểm hạ cánh sau khi giao bánh cho ngôi nhà cuối cùng không được tính vào tổng thời gian. Chỉ tính thời gian di chuyển, bỏ qua mọi thời gian khác.

Yêu cầu

Cho vị trí các ngôi nhà, hãy viết chương trình tìm tổng thời gian nhỏ nhất nếu chọn giao điểm hạ cánh tối ưu, đồng thời tìm vị trí giao điểm cần hạ cánh để đạt được tổng thời gian đó.

Dữ liệu vào

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

• Dòng đầu tiên chứa hai số nguyên \(W,H\), cách nhau bởi dấu cách, là số con đường theo từng hướng.
• Dòng thứ hai chứa số nguyên \(N\), là số ngôi nhà.
• \(N\) dòng tiếp theo mô tả vị trí các ngôi nhà. Dòng \(i+2\) (\(1\le i\le N\)) chứa hai số nguyên \(X_i,Y_i\), cách nhau bởi dấu cách, cho biết ngôi nhà thứ \(i\) nằm tại giao điểm \((X_i,Y_i)\). Các giao điểm này đôi một khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn:

• Dòng đầu tiên chứa một số nguyên là tổng thời gian nhỏ nhất.
• Dòng thứ hai chứa hai số nguyên \(x,y\) theo thứ tự đó, cách nhau bởi dấu cách, là tọa độ giao điểm hạ cánh để đạt được tổng thời gian nhỏ nhất. Nếu có nhiều giao điểm phù hợp, chọn giao điểm ở xa nhất về phía tây, tức có \(x\) nhỏ nhất. Nếu vẫn còn nhiều lựa chọn, chọn giao điểm ở xa nhất về phía nam trong số đó, tức có \(y\) nhỏ nhất.

Ràng buộc

• \(1\le W\le1000000000=10^9\).
• \(1\le H\le1000000000=10^9\).
• \(1\le N\le100000=10^5\).
• \(1\le X_i\le W\) và \(1\le Y_i\le H\) với mọi \(1\le i\le N\).
• Các cặp \((X_i,Y_i)\) đôi một khác nhau.
• Giới hạn thời gian: \(1\) giây. Giới hạn bộ nhớ: \(64\) MB.

Lưu ý

Các số nguyên cần xử lý trong bài này có thể vượt quá phạm vi biểu diễn của kiểu số nguyên \(32\) bit.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(20\) nhóm dữ liệu, mỗi nhóm \(5\) điểm. Mỗi nhóm gồm nhiều bộ dữ liệu; chỉ nhận được điểm của nhóm nếu trả lời đúng tất cả các bộ dữ liệu trong nhóm đó. Các điều kiện điểm thành phần dưới đây có thể chồng lấp:

• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn \(N\le1000\).
• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn \(W\le50\), \(H\le50\) và \(N\le1000\).

Ví dụ

5 4
3
1 1
3 4
5 3

10
3 3

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

21
2 3

Bạn đã từng nghe đến công ty Just Odd Inventions chưa? Công việc của công ty này là tạo ra “những phát minh kỳ quặc” (just odd inventions). Ta gọi tắt công ty là JOI.

Công ty JOI đang nghiên cứu cách nhốt nhiều vi sinh vật còn sống trong cùng một đĩa Petri. Có \(N\) vi sinh vật cần nghiên cứu, được đánh số \(1,2,\ldots,N\). Khi bị nhốt vào đĩa Petri, mỗi vi sinh vật lập tức giải phóng một chất độc hại gọi là foo (fatally odd object). Lượng foo mà mỗi vi sinh vật giải phóng đã được biết trước. Toàn bộ lượng foo do các vi sinh vật trong đĩa giải phóng được chia đều để các vi sinh vật đó hấp thụ. Khả năng chịu đựng foo của mỗi vi sinh vật cũng đã được biết trước; nếu hấp thụ một lượng lớn hơn ngưỡng này, vi sinh vật sẽ chết.

Vi sinh vật \(i\) giải phóng \(a_i\) miligam foo và chịu được tối đa \(b_i\) miligam foo. Nói cách khác, nếu nhốt các vi sinh vật \(i_1,i_2,\ldots,i_k\) vào đĩa Petri, mỗi vi sinh vật trong đĩa sẽ hấp thụ lượng foo, tính bằng miligam, bằng

Vi sinh vật \(i\) trong đĩa sẽ chết nếu lượng hấp thụ này lớn hơn \(b_i\).

Theo yêu cầu của công ty JOI, bạn phải nhốt càng nhiều vi sinh vật còn sống vào cùng một đĩa Petri càng tốt. Tuy nhiên, xác vi sinh vật sẽ ảnh hưởng xấu đến môi trường trong đĩa, nên không được để bất kỳ vi sinh vật nào trong đĩa chết do hấp thụ foo.

Việc công ty JOI kiếm lợi nhuận bằng cách tạo ra “những phát minh kỳ quặc” như thế nào vẫn là một bí ẩn; ngay cả trong công ty cũng không ai ngoài giám đốc biết được điều đó.

Yêu cầu

Cho số lượng vi sinh vật cần nghiên cứu, lượng foo giải phóng và ngưỡng chịu đựng foo của từng vi sinh vật, hãy viết chương trình tìm số vi sinh vật lớn nhất có thể nhốt vào cùng một đĩa Petri mà không vi sinh vật nào chết.

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ố vi sinh vật cần nghiên cứu.
• \(N\) dòng tiếp theo mô tả các vi sinh vật. Dòng \(i+1\) (\(1\le i\le N\)) chứa hai số nguyên dương \(a_i,b_i\), cách nhau bởi dấu cách, lần lượt là lượng foo mà vi sinh vật \(i\) giải phóng và ngưỡng chịu đựng foo của nó, tính bằng miligam.

Dữ liệu ra

Ghi ra đầu ra chuẩn trên một dòng số vi sinh vật lớn nhất có thể nhốt vào cùng một đĩa Petri mà không vi sinh vật nào chết.

Ràng buộc

• \(1\le N\le300000=3\times10^5\).
• \(1\le a_i\le100000=10^5\) với mọi \(1\le i\le N\).
• \(1\le b_i\le100000=10^5\) với mọi \(1\le i\le N\).
• Giới hạn thời gian: \(1.5\) giây. Giới hạn bộ nhớ: \(256\) MB.

Lưu ý

Các số nguyên cần xử lý trong bài này có thể vượt quá phạm vi biểu diễn của kiểu số nguyên \(32\) bit.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) nhóm dữ liệu, mỗi nhóm \(10\) điểm. Mỗi nhóm gồm nhiều bộ dữ liệu; chỉ nhận được điểm của nhóm nếu trả lời đúng tất cả các bộ dữ liệu trong nhóm đó.

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

Ví dụ

6
12 8
5 9
2 4
10 12
6 7
13 9

3