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

Taro có thói quen ghé thăm \(3\) cửa hàng mỗi ngày. Cậu xuất phát từ nhà, đi qua \(3\) cửa hàng theo một thứ tự cố định rồi trở về nhà. Thỉnh thoảng, cậu dùng đồng hồ bấm giờ để đo số giây cần thiết để di chuyển trên từng chặng và ghi lại kết quả.

Yêu cầu

Cho kết quả đo của một ngày, hãy viết chương trình tính tổng thời gian di chuyển trong ngày đó theo phút và giây.

Dữ liệu vào

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

• Dòng \(1\) là thời gian đi từ nhà đến cửa hàng thứ nhất, tính bằng giây.
• Dòng \(2\) là thời gian đi từ cửa hàng thứ nhất đến cửa hàng thứ hai, tính bằng giây.
• Dòng \(3\) là thời gian đi từ cửa hàng thứ hai đến cửa hàng thứ ba, tính bằng giây.
• Dòng \(4\) là thời gian đi từ cửa hàng thứ ba về nhà, tính bằng giây.

Dữ liệu ra

In ra \(2\) dòng. Nếu tổng thời gian là \(x\) phút \(y\) giây, với \(1 \le x \le 59\) và \(0 \le y \le 59\), in \(x\) trên dòng thứ nhất và \(y\) trên dòng thứ hai.

Ràng buộc

• Mỗi thời gian trong đầu vào là một số nguyên dương.
• Tổng thời gian di chuyển ít nhất là \(1\) phút \(0\) giây và nhiều nhất là \(59\) phút \(59\) giây.

Ví dụ

31
34
7
151

3
43

316
430
643
1253

44
2

5
10
15
30

1
0

Bạn có \(N\) chiếc nhẫn. Trên mỗi chiếc nhẫn có khắc một xâu gồm \(10\) chữ cái in hoa trong bảng chữ cái tiếng Anh. Các chữ được khắc vòng quanh chiếc nhẫn, nên đầu và cuối xâu nối liền với nhau. Không xét việc đọc xâu theo chiều ngược lại.

Yêu cầu

Cho một xâu cần tìm, hãy viết chương trình đếm số chiếc nhẫn có chứa xâu đó.

Dữ liệu vào

Dữ liệu gồm \(2+N\) dòng:

• Dòng \(1\) chứa xâu cần tìm, gồm từ \(1\) đến \(10\) chữ cái in hoa trong bảng chữ cái tiếng Anh.
• Dòng \(2\) chứa số nguyên \(N\), là số chiếc nhẫn.
• Dòng \(2+i\) (\(1 \le i \le N\)) chứa xâu gồm \(10\) chữ cái được khắc trên chiếc nhẫn thứ \(i\).

Dữ liệu ra

In ra một dòng chứa một số nguyên là số chiếc nhẫn có chứa xâu cần tìm.

Ràng buộc

• \(1 \le N \le 100\).
• Xâu cần tìm có độ dài từ \(1\) đến \(10\).
• Xâu trên mỗi chiếc nhẫn có đúng \(10\) chữ cái.
• Tất cả các xâu chỉ gồm chữ cái in hoa trong bảng chữ cái tiếng Anh.

Ví dụ

ABCD
3
ABCDXXXXXX
YYYYABCDXX
DCBAZZZZZZ

2

XYZ
1
ZAAAAAAAXY

1

PQR
3
PQRAAAAPQR
BBPQRBBBBB
CCCCCCCCCC

2

Trường trung học JOI quyết định dùng những viên gạch hình vuông kích thước \(1 \times 1\) để tạo một bức tranh tường hình vuông kích thước \(N \times N\) và trưng bày trong lễ hội văn hóa. Có \(3\) màu gạch: đỏ, xanh lam và vàng.

Bức tranh được thiết kế như sau. Trước hết, lát vòng ngoài cùng bằng gạch đỏ, vòng ngay bên trong bằng gạch xanh lam, rồi vòng tiếp theo bằng gạch vàng. Tiếp tục lặp lại cho đến khi lát kín hình vuông \(N \times N\). Như vậy, màu các vòng từ ngoài vào trong lần lượt là đỏ, xanh lam, vàng, đỏ, xanh lam, vàng, \(\ldots\)

Một ngày khi lễ hội văn hóa đang đến gần, người ta phát hiện có \(K\) viên gạch của bức tranh bị bong ra. Vì vậy, họ quyết định mua gạch mới để lát lại những vị trí đó.

Chẳng hạn, khi \(N=11\), bức tranh kích thước \(11 \times 11\) có thiết kế như hình dưới đây.

Khi \(N=16\), bức tranh kích thước \(16 \times 16\) có thiết kế như hình dưới đây.

Yêu cầu

Cho độ dài cạnh \(N\) của bức tranh, số viên gạch bị bong \(K\) và vị trí của \(K\) viên gạch đó, hãy viết chương trình xác định màu của từng viên gạch bị bong.

Dữ liệu vào

Dữ liệu gồm \(2+K\) dòng:

• Dòng \(1\) chứa số nguyên \(N\), là độ dài cạnh của bức tranh.
• Dòng \(2\) chứa số nguyên \(K\), là số viên gạch bị bong.
• Dòng \(2+i\) (\(1 \le i \le K\)) chứa hai số nguyên \(a_i\) và \(b_i\), cách nhau bởi một dấu cách. Viên gạch bị bong thứ \(i\) nằm ở cột thứ \(a_i\) tính từ trái sang và hàng thứ \(b_i\) tính từ trên xuống.

Dữ liệu ra

In ra \(K\) dòng, mỗi dòng chứa một số nguyên. Trên dòng thứ \(i\) (\(1 \le i \le K\)), in 1 nếu viên gạch bị bong thứ \(i\) có màu đỏ, 2 nếu có màu xanh lam và 3 nếu có màu vàng.

Ràng buộc

• \(1 \le N \le 1\,000\,000\,000 = 10^9\).
• \(1 \le K \le 1000\).
• \(1 \le a_i \le N\) và \(1 \le b_i \le N\) với mọi \(1 \le i \le K\).
• Không có hai dòng trong các dòng từ \(3\) đến \(2+K\) mô tả cùng một viên gạch.

Phân nhóm

• Trong \(40\%\) dữ liệu đầu vào, \(N \le 1000\).

Ví dụ

11
4
5 2
9 7
4 4
3 9

2
3
1
3

16
7
3 7
5 2
11 6
15 2
9 7
8 12
15 16

3
2
3
2
1
2
1

JOI là học sinh lớp một. Cậu rất thích phép cộng và phép trừ vừa được học. Mỗi khi nhìn thấy một dãy chữ số, cậu lại chơi trò tạo đẳng thức bằng cách đặt dấu = giữa hai chữ số cuối cùng, rồi đặt đúng một dấu + hoặc - vào mỗi khoảng trống còn lại giữa các chữ số. Chẳng hạn, từ dãy 8 3 2 4 8 7 2 4 0 8 8, cậu có thể tạo đẳng thức

Sau khi tạo một đẳng thức, JOI tính toán để kiểm tra xem đẳng thức đó có đúng hay không. Tuy nhiên, cậu chưa biết số âm và chưa thể tính toán với các số lớn hơn \(20\). Vì vậy, trong số những đẳng thức đúng, cậu chỉ có thể kiểm tra những đẳng thức mà khi tính vế trái từ trái sang phải, mọi giá trị xuất hiện trong quá trình tính đều nằm trong khoảng từ \(0\) đến \(20\), kể cả hai đầu mút.

Chẳng hạn, đẳng thức

là đúng, nhưng biểu thức trung gian \(8+3-2-4-8\) có giá trị âm nên JOI không thể kiểm tra đẳng thức này.

Yêu cầu

Cho một dãy chữ số, hãy viết chương trình đếm số đẳng thức đúng mà JOI có thể tạo ra và kiểm tra được.

Dữ liệu vào

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

• Dòng \(1\) chứa số nguyên \(N\), là số chữ số trong dãy.
• Dòng \(2\) chứa \(N\) số nguyên từ \(0\) đến \(9\), cách nhau bởi dấu cách.

Dữ liệu ra

In ra một dòng chứa một số nguyên là số đẳng thức đúng mà JOI có thể tạo ra và kiểm tra được.

Ràng buộc

• \(3 \le N \le 100\).
• Mỗi số trong dãy là số nguyên từ \(0\) đến \(9\).
• Với mọi dữ liệu đầu vào, số đẳng thức đúng mà JOI có thể tạo ra và kiểm tra được không vượt quá \(2^{63}-1\).

Phân nhóm

• Trong \(60\%\) dữ liệu đầu vào, số đẳng thức đúng mà JOI có thể tạo ra và kiểm tra được không vượt quá \(2^{31}-1\).

Ví dụ

11
8 3 2 4 8 7 2 4 0 8 8

10

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1

7069052760

Năm nay, các nhà máy phô mai ở thị trấn JOI lại bắt đầu sản xuất phô mai, và một chú chuột thò đầu ra khỏi tổ. Thị trấn được chia thành các ô theo các hướng đông, tây, nam, bắc. Mỗi ô là tổ chuột, nhà máy phô mai, chướng ngại vật hoặc đất trống. Chú chuột xuất phát từ tổ, ghé thăm tất cả các nhà máy và ăn một miếng phô mai ở mỗi nhà máy.

Thị trấn có \(N\) nhà máy phô mai, mỗi nhà máy chỉ sản xuất một loại phô mai. Độ cứng của phô mai ở các nhà máy khác nhau là khác nhau: với mỗi độ cứng từ \(1\) đến \(N\), có đúng một nhà máy sản xuất phô mai có độ cứng đó.

Ban đầu, sức lực của chú chuột là \(1\). Mỗi lần ăn một miếng phô mai, sức lực của chú tăng thêm \(1\). Tuy nhiên, chú không thể ăn phô mai có độ cứng lớn hơn sức lực hiện tại của mình.

Yêu cầu

Chú chuột có thể di chuyển đến một ô kề theo hướng đông, tây, nam hoặc bắc trong \(1\) phút, nhưng không được đi vào ô có chướng ngại vật. Chú cũng có thể đi qua một nhà máy mà không ăn phô mai ở đó. Hãy viết chương trình tìm thời gian ngắn nhất để chú ăn hết tất cả các miếng phô mai. Có thể bỏ qua thời gian ăn phô mai.

Dữ liệu vào

Dữ liệu gồm \(H+1\) dòng:

• Dòng \(1\) chứa ba số nguyên \(H\), \(W\), \(N\) theo thứ tự này, cách nhau bởi dấu cách.
• Mỗi dòng từ \(2\) đến \(H+1\) chứa một xâu gồm \(W\) ký tự thuộc tập S, 1, 2, \(\ldots\), 9, X, ., mô tả trạng thái của các ô.

Gọi ô ở vị trí thứ \(i\) tính từ phía bắc và thứ \(j\) tính từ phía tây là \((i,j)\), với \(1 \le i \le H\) và \(1 \le j \le W\). Ký tự thứ \(j\) trên dòng \(i+1\) mô tả ô \((i,j)\) như sau:

• S: tổ chuột.
• X: chướng ngại vật.
• .: đất trống.
• 1, 2, \(\ldots\), 9: nhà máy sản xuất phô mai có độ cứng tương ứng là \(1\), \(2\), \(\ldots\), \(9\).

Đầu vào có đúng một tổ chuột và đúng một nhà máy cho mỗi độ cứng \(1\), \(2\), \(\ldots\), \(N\). Các ô còn lại đều là chướng ngại vật hoặc đất trống. Bảo đảm chú chuột có thể ăn hết tất cả các miếng phô mai.

Dữ liệu ra

In ra một dòng chứa một số nguyên là thời gian ngắn nhất, tính bằng phút, để chú chuột ăn hết tất cả các miếng phô mai.

Ràng buộc

• \(1 \le H \le 1000\).
• \(1 \le W \le 1000\).
• \(1 \le N \le 9\).

Ví dụ

3 3 1
S..
...
..1

4

4 5 2
.X..1
....X
.XX.S
.2.X.

12

10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......

91

Ủy ban Olympic Tin học Nhật Bản quyết định làm những lá cờ lấy cảm hứng từ biểu trưng JOI để quảng bá cho kỳ thi Olympic Tin học Nhật Bản (JOI) năm nay. Mỗi lá cờ phải là một “lá cờ tốt”.

Yêu cầu

Một “lá cờ tốt” là một hình chữ nhật gồm \(M\) hàng và \(N\) cột, mỗi vị trí chứa một trong ba chữ cái J, O, I, đồng thời có ít nhất một vị trí mà ba chữ cái J, O, I được sắp xếp như hình dưới đây: O ở ngay bên phải J, và I ở ngay bên dưới chính chữ J đó.

Hình dưới đây cho hai ví dụ về “lá cờ tốt”.

Hình dưới đây cho hai ví dụ về những lá cờ không phải là “lá cờ tốt”.

Hiện tại, các giá trị \(M\), \(N\) đã được xác định và một số vị trí trên lá cờ đã được ấn định chữ cái J, O hoặc I. Cho những thông tin này, hãy viết chương trình đếm số “lá cờ tốt” có thể tạo ra và in phần dư của số đó khi chia cho \(100\,000 = 10^5\).

Dữ liệu vào

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

• Dòng \(1\) chứa hai số nguyên \(M\) và \(N\), cách nhau bởi một dấu cách, biểu thị kích thước lá cờ.
• Dòng \(1+i\) (\(1 \le i \le M\)) chứa một xâu gồm \(N\) ký tự. Mỗi ký tự là J, O, I hoặc ?. Nếu ký tự thứ \(j\) (\(1 \le j \le N\)) là J, O hoặc I, vị trí ở hàng \(i\), cột \(j\) đã được ấn định chữ cái tương ứng. Nếu ký tự đó là ?, chữ cái ở vị trí này chưa được xác định.

Dữ liệu ra

In ra một dòng chứa phần dư của số “lá cờ tốt” có thể tạo ra khi chia cho \(100\,000 = 10^5\).

Ràng buộc

• \(2 \le M \le 20\).
• \(2 \le N \le 20\).
• Mỗi xâu mô tả một hàng có đúng \(N\) ký tự, chỉ gồm J, O, I, ?.

Ví dụ

2 3
??O
IIJ

4

2 2
??
??

3

3 3
??I
???
O?J

53

5 4
JOI?
????
????
????
?JOI

28218