JOI 2008/2009 - Vòng sơ khảo

Công ty JOI dùng thẻ chấm công để quản lý thời gian nhân viên có mặt tại công ty. Khi đến làm và khi ra về, mỗi nhân viên dùng một thiết bị chuyên dụng để ghi thời điểm tương ứng lên thẻ. Các thời điểm được biểu diễn theo hệ 24 giờ.

Vì lý do an ninh, nhân viên đến công ty từ 7 giờ trở đi và đều ra về trước 23 giờ. Thời điểm ra về luôn sau thời điểm đến trong cùng ngày.

Yêu cầu

Cho thời điểm đến và thời điểm ra về của ba nhân viên \(A\), \(B\), \(C\). Hãy tính thời gian có mặt tại công ty của từng người.

Dữ liệu vào

Đọc từ đầu vào chuẩn ba dòng, lần lượt tương ứng với nhân viên \(A\), \(B\), \(C\).

Mỗi dòng chứa sáu số nguyên, cách nhau bởi dấu cách: ba số đầu biểu diễn thời điểm đến, ba số sau biểu diễn thời điểm ra về. Mỗi thời điểm được viết dưới dạng \(h\ m\ s\), nghĩa là \(h\) giờ \(m\) phút \(s\) giây.

Dữ liệu ra

Ghi ra đầu ra chuẩn ba dòng, lần lượt là thời gian có mặt tại công ty của \(A\), \(B\), \(C\).

Nếu thời gian đó là \(h\) giờ \(m\) phút \(s\) giây, ghi ba số nguyên \(h\), \(m\), \(s\) theo thứ tự này, cách nhau bởi dấu cách; số phút và số giây đều nằm trong khoảng từ \(0\) đến \(59\).

Ràng buộc

• Có đúng \(3\) nhân viên.
• Với mỗi thời điểm: \(7\le h\le22\), \(0\le m\le59\), \(0\le s\le59\).
• Thời điểm ra về luôn sau thời điểm đến trong cùng ngày.

Ví dụ

9 0 0 18 0 0
9 0 1 18 0 0
12 14 52 12 15 30

9 0 0
8 59 59
0 0 38

Một cuộc thi lập trình trực tuyến vừa được tổ chức. Câu lạc bộ tin học của hai trường đại học \(W\) và \(K\) vốn là đối thủ của nhau, nên quyết định dùng kết quả cuộc thi này để phân định thắng thua.

Mỗi trường có \(10\) người tham gia. Sau một cuộc thảo luận dài, hai bên thống nhất lấy tổng điểm của ba người có điểm cao nhất trong mỗi trường làm điểm của trường đó.

Yêu cầu

Cho điểm của các thí sinh thuộc hai trường \(W\) và \(K\). Hãy tính điểm của từng trường.

Dữ liệu vào

Đọc từ đầu vào chuẩn \(20\) dòng, mỗi dòng chứa một số nguyên:

• Các dòng từ \(1\) đến \(10\) là điểm của \(10\) thí sinh thuộc trường \(W\).
• Các dòng từ \(11\) đến \(20\) là điểm của \(10\) thí sinh thuộc trường \(K\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa điểm của trường \(W\), rồi đến điểm của trường \(K\), cách nhau bởi một dấu cách.

Ràng buộc

• Mỗi trường có đúng \(10\) thí sinh.
• Điểm của mỗi thí sinh là số nguyên từ \(0\) đến \(100\).

Ví dụ

23
23
20
15
15
14
13
9
7
6
25
19
17
17
16
13
12
11
9
5

66 61

17
25
23
25
79
29
1
61
59
100
44
74
94
57
13
54
82
0
42
45

240 250

Có \(N\) nhân vật xếp thành một cột từ trên xuống dưới. Mỗi nhân vật có một trong ba màu: đỏ, xanh lam hoặc vàng. Ban đầu, không có từ bốn nhân vật cùng màu trở lên đứng liên tiếp.

Người chơi chọn đúng một nhân vật và đổi màu của nhân vật đó thành một trong hai màu còn lại. Nếu thao tác này tạo ra một nhóm gồm ít nhất bốn nhân vật cùng màu liên tiếp, toàn bộ nhóm đó biến mất. Các nhân vật còn lại khép lại chỗ trống và giữ nguyên thứ tự tương đối. Nếu khi đó lại xuất hiện một nhóm gồm ít nhất bốn nhân vật cùng màu liên tiếp, nhóm này cũng biến mất. Phản ứng dây chuyền tiếp tục cho đến khi không còn nhóm nào như vậy.

Mục tiêu của trò chơi là làm cho số nhân vật còn lại nhỏ nhất có thể.

Yêu cầu

Cho màu của \(N\) nhân vật theo thứ tự ban đầu. Hãy tìm số nhân vật còn lại nhỏ nhất \(M\) sau khi đổi màu đúng một nhân vật và để phản ứng dây chuyền kết thúc.

Dữ liệu vào

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

• Dòng đầu chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên thuộc \(\{1,2,3\}\). Dòng thứ \(i+1\) biểu diễn màu của nhân vật thứ \(i\) từ trên xuống dưới: \(1\) là đỏ, \(2\) là xanh lam, \(3\) là vàng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên \(M\), là số nhân vật còn lại nhỏ nhất.

Ràng buộc

• \(1\le N\le10\,000\).
• Mỗi màu được biểu diễn bằng \(1\), \(2\) hoặc \(3\).
• Ban đầu không có từ bốn nhân vật cùng màu trở lên đứng liên tiếp.

Chấm điểm

Bài có \(4\) bộ dữ liệu chấm, mỗi bộ \(5\) điểm, tổng cộng \(20\) điểm.

Ví dụ

12
3
2
1
1
2
3
2
2
2
1
1
3

3

Đổi màu nhân vật thứ \(6\) từ trên xuống từ vàng thành xanh lam. Khi đó, năm nhân vật xanh lam liên tiếp biến mất. Tiếp theo, bốn nhân vật đỏ trở thành liên tiếp và cũng biến mất. Cuối cùng còn lại ba nhân vật.

12
3
2
1
1
2
3
2
1
3
2
1
3

12

Vào một ngày đông lạnh giá, JOI Taro quyết định chơi trò đập lớp băng mỏng phủ trên một quảng trường. Quảng trường có dạng hình chữ nhật, được chia thành \(m\) cột theo hướng đông–tây và \(n\) hàng theo hướng bắc–nam, tạo thành \(m\times n\) ô. Một số ô có băng mỏng, những ô khác không có băng.

Taro di chuyển và đập băng theo các quy tắc sau:

• Có thể bắt đầu tại bất kỳ ô nào có băng và đập băng ở ô đó.
• Từ ô hiện tại, chỉ có thể đi sang một ô kề cạnh về phía đông, tây, nam hoặc bắc, có băng chưa bị đập.
• Khi đến một ô, phải đập băng ở ô đó.

Yêu cầu

Hãy tìm số ô lớn nhất mà Taro có thể đi qua trong một lượt chơi, tính cả ô bắt đầu.

Dữ liệu vào

Đọc từ đầu vào chuẩn \(n+2\) dòng:

• Dòng đầu chứa số nguyên \(m\), là số cột.
• Dòng thứ hai chứa số nguyên \(n\), là số hàng.
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên \(0\) hoặc \(1\), cách nhau bởi dấu cách.

Gọi \((i,j)\) là ô ở hàng thứ \(i\) tính từ phía bắc và cột thứ \(j\) tính từ phía tây. Số thứ \(j\) trên dòng thứ \(i+2\) bằng \(1\) nếu ô \((i,j)\) có băng, và bằng \(0\) nếu ô đó không có băng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên, là số ô lớn nhất có thể đi qua.

Ràng buộc

• \(1\le m\le90\).
• \(1\le n\le90\).
• Mỗi ô được mô tả bằng \(0\) hoặc \(1\).
• Trong mỗi bộ dữ liệu, số cách di chuyển theo các quy tắc trên không vượt quá \(200\,000\).

Ví dụ

3
3
1 1 0
1 0 1
1 1 0

5

5
3
1 1 1 0 1
1 1 0 0 0
1 0 0 0 1

5

Năm hình sau minh họa một đường đi qua năm ô băng của ví dụ 2, theo thứ tự từng bước:

Có \(n\) lá bài được đánh số từ \(1\) đến \(n\). Ban đầu, các lá bài được xếp thành một chồng theo thứ tự từ trên xuống dưới là \(1,2,\ldots,n\).

Thao tác xáo bài \((x,y)\), với \(1\le x<y<n\), được thực hiện như sau:

1. Chia chồng bài hiện tại thành ba chồng: chồng \(A\) gồm các lá ở vị trí từ \(1\) đến \(x\), chồng \(B\) gồm các lá ở vị trí từ \(x+1\) đến \(y\), và chồng \(C\) gồm các lá ở vị trí từ \(y+1\) đến \(n\). Mọi vị trí đều được đếm từ trên xuống dưới.
2. Đặt chồng \(B\) lên trên chồng \(A\), rồi đặt chồng \(C\) lên trên cùng. Thứ tự các lá trong mỗi chồng con được giữ nguyên. Như vậy, thứ tự ba chồng từ trên xuống dưới trở thành \(C,B,A\).

Chẳng hạn, nếu chồng bài ban đầu có \(9\) lá, sau thao tác xáo bài \((3,5)\), thứ tự các lá từ trên xuống dưới là \(6,7,8,9,4,5,1,2,3\).

Yêu cầu

Thực hiện lần lượt \(m\) thao tác xáo bài \((x_1,y_1),(x_2,y_2),\ldots,(x_m,y_m)\) từ trạng thái ban đầu. Trong chồng bài cuối cùng, hãy đếm số lá có số hiệu không vượt quá \(r\) nằm ở các vị trí từ \(p\) đến \(q\), tính cả hai đầu và đếm từ trên xuống dưới.

Dữ liệu vào

Đọc từ đầu vào chuẩn \(m+3\) dòng:

• Dòng đầu chứa số nguyên \(n\), là số lá bài.
• Dòng thứ hai chứa số nguyên \(m\), là số thao tác xáo bài.
• Dòng thứ ba chứa ba số nguyên \(p\), \(q\), \(r\), cách nhau bởi dấu cách.
• Dòng thứ \(i+3\), với \(1\le i\le m\), chứa hai số nguyên \(x_i\), \(y_i\), cách nhau bởi một dấu cách, mô tả thao tác xáo bài thứ \(i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên, là số lá bài có số hiệu không vượt quá \(r\) nằm ở các vị trí từ \(p\) đến \(q\) sau tất cả các thao tác.

Ràng buộc

• \(3\le n\le10^9\).
• \(1\le m\le5\,000\).
• \(1\le p\le q\le n\).
• \(1\le r\le n\).
• \(1\le x_i<y_i<n\) với mọi \(1\le i\le m\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Ví dụ

9
1
3 7 4
3 5

2

Sau thao tác xáo bài \((3,5)\), thứ tự các lá bài từ trên xuống dưới là \(6,7,8,9,4,5,1,2,3\). Trong các vị trí từ \(3\) đến \(7\), có hai lá có số hiệu không vượt quá \(4\): lá số \(4\) và lá số \(1\).

12
3
3 8 5
3 8
2 5
6 10

3

Sau ba thao tác, thứ tự các lá bài từ trên xuống dưới là \(9,10,3,11,12,4,5,6,7,8,1,2\). Trong các vị trí từ \(3\) đến \(8\), có ba lá có số hiệu không vượt quá \(5\).

Một cuộc thi lập trình có truyền thống tổ chức trò chơi bingo trong buổi giao lưu sau cuộc thi. Những tấm thẻ bingo dùng trong trò chơi này khá đặc biệt và phải thỏa mãn tất cả các điều kiện sau:

• Mỗi thẻ gồm \(N\) hàng và \(N\) cột. Mỗi ô chứa một số nguyên dương và tất cả \(N^2\) số trên thẻ đôi một khác nhau.
• Mỗi số trên thẻ nằm trong khoảng từ \(1\) đến \(M\).
• Tổng tất cả các số trên thẻ bằng \(S\).
• Trong mỗi cột, các số tăng dần từ trên xuống dưới.
• Số trong mỗi ô lớn hơn mọi số thuộc bất kỳ cột nào nằm bên trái cột chứa ô đó.

Ban tổ chức muốn làm nhiều thẻ thỏa mãn các điều kiện trên nhất có thể, nhưng không được làm hai thẻ giống hệt nhau.

Yêu cầu

Cho \(N\), \(M\), \(S\). Hãy tính số thẻ bingo khác nhau có thể tạo ra và in phần dư của số đó khi chia cho \(100\,000\).

Dữ liệu vào

Đọc từ đầu vào chuẩn một dòng chứa ba số nguyên dương \(N\), \(M\), \(S\), cách nhau bởi dấu cách. Trong đó, \(N\) là kích thước thẻ, \(M\) là giới hạn trên của các số trên thẻ, và \(S\) là tổng các số trên thẻ.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên, là phần dư của số thẻ bingo khác nhau có thể tạo ra khi chia cho \(100\,000\).

Ràng buộc

• \(1\le N\le7\).
• \(1\le M\le2\,000\).
• \(1\le S\le3\,000\).
• Với mỗi bộ dữ liệu, luôn có ít nhất một thẻ bingo thỏa mãn các điều kiện.

Chấm điểm

Bài có \(4\) bộ dữ liệu chấm, mỗi bộ \(5\) điểm, tổng cộng \(20\) điểm.

Ví dụ

3 9 45

1

3 100 50

7

5 50 685

74501

Có \(642\,499\,974\,501\) thẻ khác nhau thỏa mãn dữ liệu của ví dụ \(3\). Phần dư khi chia số này cho \(100\,000\) là \(74501\).