JOI 2013/2014 - Vòng sơ khảo

Có năm học sinh tham gia một lớp học ở trường trung học JOI: Taro, Jiro, Saburo, Shiro và Hanako.

Cả năm học sinh đều dự thi cuối kỳ của lớp học này. Với học sinh đạt từ \(40\) điểm trở lên trong kỳ thi, điểm tổng kết chính là điểm thi cuối kỳ. Tất cả học sinh có điểm thi dưới \(40\) đều tham gia học phụ đạo và được tính điểm tổng kết là \(40\).

Cho điểm thi cuối kỳ của năm học sinh, hãy viết chương trình tính trung bình cộng điểm tổng kết của cả năm bạn.

Dữ liệu vào

Dữ liệu vào gồm \(5\) dòng, mỗi dòng chứa một số nguyên:

• Dòng thứ nhất là điểm thi cuối kỳ của Taro.
• Dòng thứ hai là điểm thi cuối kỳ của Jiro.
• Dòng thứ ba là điểm thi cuối kỳ của Saburo.
• Dòng thứ tư là điểm thi cuối kỳ của Shiro.
• Dòng thứ năm là điểm thi cuối kỳ của Hanako.

Dữ liệu ra

In ra một dòng chứa một số nguyên là trung bình cộng điểm tổng kết của năm học sinh.

Ràng buộc

• Điểm thi cuối kỳ của mỗi học sinh là số nguyên từ \(0\) đến \(100\), kể cả hai đầu mút.
• Tất cả điểm thi cuối kỳ đều là bội của \(5\).
• Trung bình cộng điểm tổng kết của năm học sinh luôn là số nguyên.

Ví dụ

10
65
100
30
95

68

40
95
0
95
50

64

Một đại hội thể thao mang tầm thế giới sẽ được tổ chức tại Tokyo vào năm 20XX. Thi lập trình được yêu thích như một môn thể thao trên toàn thế giới và có khả năng được đưa vào đại hội. Sau khi tìm hiểu về hội đồng xét chọn các môn thi, ta biết được những thông tin sau.

Một danh sách gồm \(N\) môn thi ứng viên đã được lập cho hội đồng, sắp xếp theo thứ tự từ thú vị nhất đến ít thú vị nhất. Môn ở vị trí thứ \(i\) từ trên xuống là môn thú vị thứ \(i\) và được gọi là môn thi \(i\). Danh sách còn ghi chi phí \(A_i\) cần thiết để tổ chức môn thi \(i\).

Hội đồng gồm \(M\) thành viên, được đánh số từ \(1\) đến \(M\). Thành viên \(j\) có ngưỡng chi phí riêng là \(B_j\) và bỏ một phiếu cho môn thú vị nhất trong số các môn có chi phí tổ chức không vượt quá \(B_j\).

Với ngưỡng chi phí của mỗi thành viên, luôn có ít nhất một môn thi có chi phí tổ chức không vượt quá ngưỡng đó. Vì vậy, tất cả thành viên đều bỏ đúng một phiếu. Có duy nhất một môn thi nhận được nhiều phiếu nhất.

Cho danh sách các môn thi và thông tin về các thành viên hội đồng, hãy viết chương trình tìm số hiệu của môn thi nhận được nhiều phiếu nhất.

Dữ liệu vào

Dữ liệu vào gồm \(1 + N + M\) dòng:

• Dòng đầu tiên chứa hai số nguyên \(N, M\), lần lượt là số môn thi và số thành viên hội đồng.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1 \le i \le N\)) chứa số nguyên \(A_i\), là chi phí cần thiết để tổ chức môn thi \(i\).
• Dòng thứ \(j\) trong \(M\) dòng tiếp theo (\(1 \le j \le M\)) chứa số nguyên \(B_j\), là ngưỡng chi phí của thành viên \(j\).

Dữ liệu ra

In ra một dòng chứa số hiệu của môn thi nhận được nhiều phiếu nhất.

Ràng buộc

• \(1 \le N \le 1000\).
• \(1 \le M \le 1000\).
• \(1 \le A_i \le 1000\) với mọi \(1 \le i \le N\).
• \(1 \le B_j \le 1000\) với mọi \(1 \le j \le M\).
• Mỗi thành viên đều có thể bỏ đúng một phiếu theo quy tắc đã nêu.
• Có duy nhất một môn thi nhận được nhiều phiếu nhất.

Ví dụ

4 3
5
3
1
4
4
3
2

2

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

1

JOI được giao lập kế hoạch cho một chuyến tham quan thành phố Siêu Đô ở đất nước IOI.

Siêu Đô được chia thành một lưới ô vuông bởi \(W\) con đường thẳng chạy theo hướng bắc–nam và \(H\) con đường thẳng chạy 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ứ \(i\) tính từ phía tây và con đường đông–tây thứ \(j\) tính từ phía nam được ký hiệu là \((i, j)\).

Ngoài ra, từ mỗi giao điểm còn có một đoạn đường đến giao điểm liền kề về phía đông bắc, trừ các giao điểm nằm trên con đường cực bắc hoặc cực đông. Tương tự, có một đoạn đường đến giao điểm liền kề về phía tây nam, trừ các giao điểm nằm trên con đường cực nam hoặc cực tây.

Cụ thể, từ giao điểm \((i, j)\), có thể đi qua một đoạn đường để đến mỗi giao điểm trong số \((i - 1, j)\), \((i + 1, j)\), \((i, j - 1)\), \((i, j + 1)\) nếu giao điểm đó tồn tại. Ngoài ra, cũng có thể đi qua một đoạn đường để đến \((i - 1, j - 1)\) hoặc \((i + 1, j + 1)\) nếu giao điểm đó tồn tại.

JOI đã quyết định thứ tự ghé thăm \(N\) điểm tham quan. Điểm tham quan thứ \(i\) cần ghé thăm (\(1 \le i \le N\)) nằm tại giao điểm \((X_i, Y_i)\). Để rút ngắn thời gian của chuyến tham quan, JOI muốn giảm số đoạn đường phải đi qua.

Hãy viết chương trình tìm tổng số đoạn đường ít nhất phải đi qua để ghé thăm các điểm tham quan theo đúng thứ tự đã định.

Chuyến tham quan bắt đầu tại giao điểm \((X_1, Y_1)\). Trong chuyến đi, JOI không được ra ngoài Siêu Đô. JOI có thể đi qua giao điểm có một điểm tham quan mà không ghé thăm điểm tham quan đó.

Làm rõ về tổng số đoạn đường: Có thể đi qua cùng một đoạn đường hai lần trở lên trong chuyến tham quan. Khi tính tổng số đoạn đường, đoạn đường đó được tính lặp lại đúng bằng số lần đi qua.

Dữ liệu vào

Dữ liệu vào gồm \(1 + N\) dòng:

• Dòng đầu tiên chứa ba số nguyên \(W, H, N\), cách nhau bởi dấu cách.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(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 điểm tham quan thứ \(i\) cần ghé thăm nằm tại giao điểm \((X_i, Y_i)\).

Dữ liệu ra

In ra một dòng chứa tổng số đoạn đường ít nhất phải đi qua để ghé thăm các điểm tham quan theo đúng thứ tự.

Ràng buộc

• \(2 \le W \le 10000\).
• \(2 \le H \le 10000\).
• \(1 \le N \le 1000\).
• \(1 \le X_i \le W\) và \(1 \le Y_i \le H\) với mọi \(1 \le i \le N\).

Ví dụ

4 3 3
1 1
3 3
4 1

5

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

7

Câu lạc bộ lập trình của trường trung học IOI có ba thành viên là J, O và I. Câu lạc bộ đang lập lịch sinh hoạt cho \(N\) ngày.

Trong mỗi ngày, mỗi thành viên có hai lựa chọn: tham gia hoặc không tham gia. Vì vậy, xét riêng việc tham gia của ba thành viên, có tất cả \(8\) khả năng cho một ngày.

Phòng câu lạc bộ chỉ có một chiếc chìa khóa, ban đầu do J giữ. Vào mỗi ngày sinh hoạt, một trong những thành viên tham gia ngày đó phải mang theo chìa khóa. Sau buổi sinh hoạt, một trong những thành viên đã tham gia sẽ mang chìa khóa về.

Để bảo đảm buổi sinh hoạt diễn ra vào tất cả các ngày đã định, câu lạc bộ chỉ định trước một người phụ trách cho mỗi ngày. Người phụ trách bắt buộc phải tham gia buổi sinh hoạt của ngày đó.

Cho số ngày cần lập lịch và người phụ trách của từng ngày, hãy viết chương trình đếm số lịch tham gia cho phép câu lạc bộ sinh hoạt vào tất cả các ngày, rồi in ra phần dư của số đó khi chia cho \(10007\).

Thành viên mang chìa khóa về sau mỗi buổi có thể là bất kỳ thành viên nào tham gia buổi đó. Vào ngày cuối cùng, ai mang chìa khóa về cũng được. Một lịch được xác định bởi những thành viên tham gia từng ngày.

Dữ liệu vào

Dữ liệu vào gồm \(2\) dòng:

• Dòng đầu tiên chứa số nguyên \(N\), là số ngày cần lập lịch.
• Dòng thứ hai chứa một chuỗi gồm \(N\) ký tự. Ký tự thứ \(i\) (\(1 \le i \le N\)) cho biết người phụ trách ngày thứ \(i\): J, O, I lần lượt tương ứng với J, O, I.

Dữ liệu ra

In ra một dòng chứa phần dư của số lịch hợp lệ khi chia cho \(10007\).

Ràng buộc

• \(2 \le N \le 1000\).
• Chuỗi có đúng \(N\) ký tự, mỗi ký tự là J, O hoặc I.

Ví dụ

2
OI

7

20
JIOIJOIJOJOIIIOJIOII

4976

Đất nước IOI gồm \(N\) thị trấn, được đánh số từ \(1\) đến \(N\), nối với nhau bằng các con đường. Có \(K\) con đường, mỗi con đường nối hai thị trấn khác nhau. Xe có thể đi theo cả hai chiều trên mỗi con đường, nhưng không thể đi từ thị trấn này sang thị trấn khác mà không đi theo các con đường.

JOI sống ở thị trấn \(1\) và quyết định đi taxi đến nhà bà ở thị trấn \(N\). Đất nước IOI có \(N\) hãng taxi, được đánh số từ \(1\) đến \(N\). Các hãng taxi có những quy định hơi đặc biệt sau:

• Chỉ có thể lên taxi của hãng \(i\) tại thị trấn \(i\).
• Cước phí cho một chuyến taxi của hãng \(i\) là \(C_i\), không phụ thuộc vào quãng đường đã đi.
• Sau khi đón khách, taxi của hãng \(i\) chỉ có thể đi liên tiếp qua nhiều nhất \(R_i\) con đường.

Ví dụ, nếu \(R_1 = 2\), khi lên taxi của hãng \(1\) tại thị trấn \(1\), JOI chỉ có thể đi qua tối đa \(2\) con đường bằng chiếc taxi đó. Để đi qua từ \(3\) con đường trở lên, JOI phải đổi taxi tại một thị trấn trên đường đi.

JOI chỉ được lên hoặc xuống taxi tại các thị trấn, và không được sử dụng phương tiện di chuyển nào khác. Hãy viết chương trình tìm tổng cước phí nhỏ nhất để JOI đi đến thị trấn \(N\).

Dữ liệu vào

Dữ liệu vào gồm \(1 + N + K\) dòng:

• Dòng đầu tiên chứa hai số nguyên \(N, K\), cách nhau bởi dấu cách, lần lượt là số thị trấn và số con đường của đất nước IOI.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1 \le i \le N\)) chứa hai số nguyên \(C_i, R_i\), cách nhau bởi dấu cách. Taxi của hãng \(i\) có cước phí \(C_i\) và được đi qua nhiều nhất \(R_i\) con đường sau khi đón khách.
• Dòng thứ \(j\) trong \(K\) dòng tiếp theo (\(1 \le j \le K\)) chứa hai số nguyên khác nhau \(A_j, B_j\), cách nhau bởi dấu cách, cho biết có một con đường nối thị trấn \(A_j\) và thị trấn \(B_j\).

Dữ liệu ra

In ra một dòng chứa một số nguyên là tổng cước phí nhỏ nhất để JOI đi từ thị trấn \(1\) đến thị trấn \(N\).

Ràng buộc

• \(2 \le N \le 5000\).
• \(N - 1 \le K \le 10000\).
• \(1 \le C_i \le 10000\) và \(1 \le R_i \le N\) với mọi \(1 \le i \le N\).
• \(1 \le A_j < B_j \le N\) với mọi \(1 \le j \le K\).
• Không có cặp \((A_j, B_j)\) nào xuất hiện từ hai lần trở lên.
• Bảo đảm 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 và đổi taxi.

Ví dụ

6 6
400 2
200 1
600 3
1000 1
300 5
700 4
1 2
2 3
3 6
4 6
1 5
2 4

700

(5)---(1)---(2)---(4)
             |     |
            (3)---(6)

JOI quyết định ăn tiểu long bao cho bữa trưa tại một nhà hàng Trung Hoa. Tiểu long bao là món ăn có nhân và nước súp nóng được bọc trong một lớp vỏ bột mì, nổi tiếng vì nước súp có thể bắn ra xung quanh khi ăn.

Phần ăn JOI gọi gồm \(N\) chiếc tiểu long bao có nhân hoặc nước súp khác nhau. Các chiếc bánh được xếp cách đều nhau trên một hàng, đánh số theo thứ tự từ \(1\) đến \(N\). Khoảng cách giữa chiếc bánh thứ \(i\) và chiếc bánh thứ \(j\) là \(|i - j|\).

JOI sẽ ăn các chiếc bánh theo một thứ tự nào đó. Ban đầu, độ ngon của tất cả các chiếc bánh đều bằng \(0\). Khi JOI ăn chiếc bánh thứ \(i\), nước súp của nó bắn ra xung quanh và rơi lên những chiếc bánh chưa được ăn nằm cách bánh \(i\) không quá \(D_i\). Độ ngon của mỗi chiếc bánh bị nước súp bắn trúng tăng thêm \(A_i\).

Cụ thể, khi chiếc bánh thứ \(i\) được ăn, nếu chiếc bánh thứ \(j\) vẫn chưa được ăn và thỏa mãn \(1 \le j \le N\), \(i - D_i \le j \le i + D_i\), thì độ ngon của chiếc bánh thứ \(j\) tăng thêm \(A_i\).

JOI muốn chọn thứ tự ăn sao cho tổng độ ngon của các chiếc bánh tại thời điểm ăn chúng là lớn nhất. Hãy viết chương trình tìm tổng độ ngon lớn nhất khi JOI ăn hết các chiếc bánh theo thứ tự tốt nhất.

Dữ liệu vào

Dữ liệu vào gồm \(3\) dòng:

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(D_1, D_2, \ldots, D_N\), cách nhau bởi dấu cách.
• Dòng thứ ba chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\), cách nhau bởi dấu cách.

Dữ liệu ra

In ra một dòng chứa tổng độ ngon lớn nhất của các chiếc bánh mà JOI ăn.

Ràng buộc

• \(1 \le N \le 100\).
• \(0 \le D_i \le 7\) với mọi \(1 \le i \le N\).
• \(0 \le A_i \le 1000\) với mọi \(1 \le i \le N\).

Ví dụ

5
1 0 1 1 2
0 2 6 3 4

20

10
5 2 7 2 6 5 3 5 3 6
8 7 8 4 0 6 0 10 10 0

237