JOI 2011/2012 - Vòng sơ khảo

Quán mì Ý JOI có một thực đơn ăn trưa rất được yêu thích, gồm mì Ý được giới thiệu trong ngày và nước ép trái cây tươi. Khi gọi một suất ăn này, khách chọn một trong ba loại mì Ý và một trong hai loại nước ép của ngày hôm đó. Giá của suất ăn bằng tổng giá của mì Ý và nước ép đã chọn, trừ đi \(50\) yên.

Yêu cầu

Cho giá của các loại mì Ý và nước ép trong một ngày, hãy tính giá thấp nhất của một suất ăn trong ngày đó.

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:

• Dòng thứ nhất chứa giá của loại mì Ý thứ nhất.
• Dòng thứ hai chứa giá của loại mì Ý thứ hai.
• Dòng thứ ba chứa giá của loại mì Ý thứ ba.
• Dòng thứ tư chứa giá của loại nước ép thứ nhất.
• Dòng thứ năm chứa giá của loại nước ép thứ hai.

Các mức giá đều được tính bằng yên.

Dữ liệu ra

In ra một dòng chứa giá thấp nhất của một suất ăn trong ngày đó, tính bằng yên.

Ràng buộc

• Giá của mỗi loại mì Ý và mỗi loại nước ép là một số nguyên từ \(100\) đến \(2000\) yên, kể cả hai đầu mút.

Ví dụ

800
700
900
198
330

848

1999
1999
100
189
100

150

Ở đất nước JOI, bóng đá rất được yêu thích và giải đấu JOI được tổ chức hằng tuần.

Giải đấu có \(N\) đội bóng, được đánh số từ \(1\) đến \(N\). Mỗi cặp đội thi đấu với nhau đúng một trận, nên tổng số trận đấu là \(N(N-1)/2\). Kết quả mỗi trận được xác định bằng số bàn thắng của hai đội. Đội thắng nhận \(3\) điểm xếp hạng, đội thua nhận \(0\) điểm; nếu hòa, mỗi đội nhận \(1\) điểm.

Thứ hạng được xác định theo tổng điểm xếp hạng của mỗi đội, không xét hiệu số bàn thắng bại. Các đội bằng điểm cùng nhận thứ hạng cao nhất trong các vị trí mà chúng chiếm. Nói cách khác, thứ hạng của một đội bằng \(1\) cộng với số đội có tổng điểm lớn hơn đội đó.

Yêu cầu

Cho kết quả của tất cả các trận đấu, hãy xác định thứ hạng của từng đội.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\), là số đội bóng.

Trong \(N(N-1)/2\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên \(A_i\), \(B_i\), \(C_i\), \(D_i\), cách nhau bởi dấu cách. Dòng này mô tả trận đấu giữa đội \(A_i\) và đội \(B_i\), trong đó đội \(A_i\) ghi \(C_i\) bàn và đội \(B_i\) ghi \(D_i\) bàn.

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(i\) chứa một số nguyên là thứ hạng của đội \(i\), với \(1 \le i \le N\).

Ràng buộc

• \(2 \le N \le 100\).
• \(1 \le A_i,B_i \le N\) và \(A_i \ne B_i\), với \(1 \le i \le N(N-1)/2\).
• \(0 \le C_i,D_i \le 100\), với \(1 \le i \le N(N-1)/2\).
• Không có hai dòng mô tả trận đấu giữa cùng một cặp đội.
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Ví dụ

4
1 2 0 1
1 3 2 1
1 4 2 2
2 3 1 1
2 4 3 0
3 4 1 3

2
1
4
2

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

2
4
1
4
3

Chủ tịch K là khách quen của tiệm pizza JOI ở trung tâm thành phố JOI. Vì một số lý do, ông quyết định bắt đầu tiết kiệm từ tháng này. Ông muốn gọi chiếc pizza có số calo trên mỗi đô la lớn nhất trong số những chiếc pizza có thể gọi tại tiệm. Ta gọi một chiếc pizza như vậy là “pizza tốt nhất”. Có thể có nhiều loại pizza tốt nhất.

Tiệm có \(N\) loại nguyên liệu phủ. Khách có thể tùy ý chọn một số loại để đặt lên đế bánh, nhưng không được chọn cùng một loại từ hai lần trở lên. Khách cũng có thể gọi pizza chỉ có đế bánh, không có nguyên liệu phủ nào.

Đế bánh có giá \(A\) đô la và mỗi loại nguyên liệu phủ đều có giá \(B\) đô la. Giá một chiếc pizza bằng tổng giá đế bánh và các nguyên liệu phủ đã chọn. Vì vậy, pizza có \(k\) loại nguyên liệu phủ, với \(0 \le k \le N\), có giá \(A + kB\) đô la. Tổng số calo của pizza bằng số calo của đế bánh cộng với số calo của các nguyên liệu phủ đã chọn.

Yêu cầu

Cho giá đế bánh, giá nguyên liệu phủ và số calo của đế bánh cùng từng loại nguyên liệu phủ, hãy tính số calo trên mỗi đô la của pizza tốt nhất.

Dữ liệu vào

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

• Dòng đầu tiên chứa số nguyên \(N\), là số loại nguyên liệu phủ.
• Dòng thứ hai chứa hai số nguyên \(A\), \(B\), cách nhau bởi dấu cách, lần lượt là giá đế bánh và giá mỗi loại nguyên liệu phủ.
• Dòng thứ ba chứa số nguyên \(C\), là số calo của đế bánh.
• Dòng thứ \(3+i\) chứa số nguyên \(D_i\), là số calo của loại nguyên liệu phủ thứ \(i\), với \(1 \le i \le N\).

Dữ liệu ra

In ra một dòng chứa số calo trên mỗi đô la của pizza tốt nhất. Bỏ phần thập phân và in kết quả dưới dạng số nguyên.

Ràng buộc

• \(1 \le N \le 100\).
• \(1 \le A,B \le 1000\).
• \(1 \le C \le 10000\).
• \(1 \le D_i \le 10000\), với \(1 \le i \le N\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Ví dụ

3
12 2
200
50
300
100

37

4
20 3
900
300
100
400
1300

100

Bạn rất thích mì Ý và ngày nào cũng tự nấu mì Ý cho bữa tối. Bạn biết làm ba loại mì Ý: sốt cà chua, sốt kem và sốt húng quế.

Bạn quyết định lên thực đơn bữa tối cho \(N\) ngày. Mỗi ngày, bạn chọn một trong ba loại mì Ý. Tuy nhiên, ăn cùng một loại liên tục sẽ gây chán, nên không được chọn cùng một loại mì Ý trong ba ngày liên tiếp trở lên. Ngoài ra, loại mì Ý của \(K\) ngày trong số \(N\) ngày đã được quyết định trước.

Yêu cầu

Cho \(N\) và thông tin về \(K\) ngày đã quyết định, hãy đếm số thực đơn thỏa mãn các điều kiện trên và lấy phần dư khi chia cho \(10000\).

Dữ liệu vào

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

Dòng đầu tiên chứa hai số nguyên \(N\), \(K\), cách nhau bởi dấu cách.

Dòng thứ \(1+i\), với \(1 \le i \le K\), chứa hai số nguyên \(A_i\), \(B_i\), cách nhau bởi dấu cách. Điều này có nghĩa là loại mì Ý của ngày thứ \(A_i\) đã được quyết định:

• \(B_i=1\): sốt cà chua.
• \(B_i=2\): sốt kem.
• \(B_i=3\): sốt húng quế.

Dữ liệu ra

In ra một dòng chứa phần dư khi chia số thực đơn hợp lệ cho \(10000\).

Ràng buộc

• \(3 \le N \le 100\).
• \(1 \le K \le N\).
• \(1 \le A_i \le N\) và \(1 \le B_i \le 3\), với \(1 \le i \le K\).
• Các giá trị \(A_1,A_2,\ldots,A_K\) đôi một khác nhau.
• Dữ liệu bảo đảm có ít nhất một thực đơn hợp lệ.
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Ví dụ

5 3
3 1
1 1
4 2

6

20 5
10 2
4 3
12 1
13 2
9 1

2640

Các tòa nhà của công ty JOI có hình dạng được ghép từ những hình lục giác đều có cạnh dài \(1\) mét. Giáng sinh đang đến gần, nên công ty quyết định trang trí các bức tường của tòa nhà bằng đèn. Tuy nhiên, trang trí những phần không thể nhìn thấy từ bên ngoài là lãng phí. Vì vậy, chỉ trang trí các mặt tường có thể đi tới từ bên ngoài mà không đi xuyên qua tòa nhà.

Hình minh họa trong phần giải thích Ví dụ 1 cho thấy một cách bố trí các tòa nhà nhìn từ trên cao. Những con số trong mỗi ô lục giác biểu thị tọa độ. Ô màu xám là nơi có tòa nhà, còn ô màu trắng là nơi không có tòa nhà.

Yêu cầu

Cho bản đồ biểu diễn vị trí các tòa nhà, hãy tính tổng chiều dài các mặt tường cần trang trí bằng đèn. Có thể đi lại tự do ở bên ngoài bản đồ, nhưng không thể đi qua giữa hai tòa nhà kề nhau.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(W\), \(H\), cách nhau bởi dấu cách.

Tiếp theo là \(H\) dòng mô tả vị trí các tòa nhà. Dòng thứ \(i+1\), với \(1 \le i \le H\), chứa \(W\) số nguyên cách nhau bởi dấu cách. Số thứ \(j\), với \(1 \le j \le W\), bằng \(1\) nếu ô lục giác ở tọa độ \((j,i)\) có tòa nhà và bằng \(0\) nếu không có.

Tọa độ trên bản đồ tuân theo các quy tắc sau:

• Ô lục giác ở phía tây nhất của hàng phía bắc nhất có tọa độ \((1,1)\).
• Ô lục giác kề phía đông của ô \((x,y)\) có tọa độ \((x+1,y)\).
• Khi \(y\) lẻ, ô lục giác kề phía tây nam của ô \((x,y)\) có tọa độ \((x,y+1)\).
• Khi \(y\) chẵn, ô lục giác kề phía đông nam của ô \((x,y)\) có tọa độ \((x,y+1)\).

Dữ liệu ra

In ra một dòng chứa tổng chiều dài các mặt tường cần trang trí bằng đèn, tính bằng mét.

Ràng buộc

• \(1 \le W,H \le 100\).
• Mỗi ô trên bản đồ có giá trị \(0\) hoặc \(1\).
• Có ít nhất một ô chứa tòa nhà.
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Ví dụ

8 4
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 0
1 0 1 0 1 1 1 1
0 1 1 0 1 0 1 0

64

8 5
0 1 1 1 0 1 1 1
0 1 0 0 1 1 0 0
1 0 0 1 1 1 1 1
0 1 0 1 1 0 1 0
0 1 1 0 1 1 0 0

56

Một số nguyên dương được gọi là số zigzag nếu khi viết số đó trong hệ thập phân, không có chữ số \(0\) ở đầu, rồi đọc các chữ số theo thứ tự từ trái sang phải, các bước tăng và giảm luân phiên nhau. Các bước tăng và giảm đều là nghiêm ngặt.

Ví dụ, \(2947\) là số zigzag vì dãy chữ số \(2 \to 9 \to 4 \to 7\) lần lượt tăng, giảm, rồi tăng. Số \(71946\) cũng là số zigzag vì các bước lần lượt là giảm, tăng, giảm, rồi tăng. Ngược lại, \(123\), \(71446\), \(71442\) và \(88\) không phải số zigzag. Mọi số nguyên dương có một chữ số đều được coi là số zigzag.

Yêu cầu

Đếm số zigzag là bội của \(M\) trong đoạn từ \(A\) đến \(B\), kể cả hai đầu mút, rồi lấy phần dư khi chia số lượng đó cho \(10000\).

Dữ liệu vào

Dữ liệu vào gồm \(3\) dòng, mỗi dòng chứa một số nguyên dương. Ba dòng lần lượt chứa \(A\), \(B\) và \(M\).

Lưu ý rằng \(A\) và \(B\) có thể không nằm trong phạm vi biểu diễn của các kiểu dữ liệu số nguyên thông thường.

Dữ liệu ra

In ra một dòng chứa phần dư khi chia số lượng các số zigzag là bội của \(M\) trong đoạn \([A,B]\) cho \(10000\).

Ràng buộc

• \(1 \le A \le B \le 10^{500}\).
• \(1 \le M \le 500\).
• \(A\), \(B\) và \(M\) đều là số nguyên dương.

Ví dụ

100
200
5

13

6
1234567
3

246