| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2012 - Contest Timing | 100 (p) | 4.0s | 512M |
| 2 | USACO 2012 - Awkward Digits | 100 (p) | 4.0s | 512M |
| 3 | USACO 2012 - Moo Sick | 100 (p) | 4.0s | 512M |
| 4 | USACO 2012 - Cow Beauty Pageant (Bronze Level) | 100 (p) | 4.0s | 512M |
Bessie đang dần chán ngành sản xuất sữa và muốn chuyển sang một nghề nghiệp mới đầy hào hứng trong lĩnh vực máy tính. Để cải thiện kỹ năng lập trình, cô quyết định tham gia các kỳ thi USACO trực tuyến. Nhận thấy kỳ thi bắt đầu vào ngày 11 tháng 11 năm 2011 (11/11/11), cô quyết định cho vui rằng mình sẽ tải đề xuống và bắt đầu lập trình vào đúng 11 giờ 11 phút sáng ngày 11/11/11.
Không may, khả năng quản lý thời gian của Bessie khá kém, vì vậy cô muốn viết nhanh một chương trình để bảo đảm mình không làm bài lâu hơn giới hạn 3 giờ (180 phút) của kỳ thi. Cho ngày và thời điểm cô ngừng làm bài, hãy giúp Bessie tính tổng số phút cô đã dành cho kỳ thi.
Dòng duy nhất chứa ba số nguyên cách nhau bởi dấu cách \(D\), \(H\), \(M\), cho biết ngày và thời điểm Bessie kết thúc kỳ thi. \(D\) là một số nguyên trong khoảng \(11 \ldots 14\), chỉ ngày trong tháng; \(H\) và \(M\) lần lượt là giờ và phút theo đồng hồ 24 giờ (do đó có giá trị từ \(H=0, M=0\) lúc nửa đêm đến \(H=23, M=59\) lúc 11 giờ 59 phút tối).
In tổng số phút Bessie đã dành cho kỳ thi, hoặc \(-1\) nếu thời điểm kết thúc sớm hơn thời điểm bắt đầu.
Ví dụ 1
12 13 141563Bessie kết thúc kỳ thi vào lúc 13 giờ 14 phút ngày 12 tháng 11 (tức 1 giờ 14 phút chiều), sau thời điểm bắt đầu 1563 phút.
USACO 2011 November Contest, Bronze Division — Contest Timing. Tác giả đề: Brian Dean.
Bessie mới học cách chuyển đổi số giữa các hệ cơ số khác nhau, nhưng cô liên tục mắc lỗi vì không thể dễ dàng giữ bút giữa hai móng trước.
Mỗi khi Bessie chuyển một số sang một hệ cơ số mới và viết kết quả ra, cô luôn viết sai một chữ số. Chẳng hạn, nếu chuyển số 14 sang hệ nhị phân (tức hệ cơ số 2), kết quả đúng phải là 1110, nhưng cô có thể viết thành 0110 hoặc 1111. Bessie không bao giờ vô tình thêm hoặc xóa chữ số, nên cô có thể viết ra một số có chữ số 0 ở đầu nếu đó là chữ số cô viết sai.
Cho các kết quả Bessie viết ra khi chuyển một số \(N\) sang hệ cơ số 2 và hệ cơ số 3, hãy xác định giá trị ban đầu đúng của \(N\) (trong hệ cơ số 10). Có thể giả sử \(N\) không quá 1 tỷ và tồn tại duy nhất một đáp án cho \(N\).
Nếu các khái niệm về số trong hệ cơ số 2 và hệ cơ số 3 còn mới với bạn, bạn có thể tham khảo bất kỳ tài liệu trực tuyến nào mình muốn.
In giá trị đúng của \(N\).
Ví dụ 1
1010
21214Khi chuyển sai \(N\) sang hệ cơ số 2, Bessie viết 1010. Khi chuyển sai \(N\) sang hệ cơ số 3, cô viết 212. Giá trị đúng của \(N\) là 14 (1110 trong hệ cơ số 2 và 112 trong hệ cơ số 3).
USACO 2011 November Contest, Bronze Division — Awkward Digits. Tác giả đề: Brian Dean.
Ai cũng biết bò thích nghe mọi thể loại nhạc. Gần như mọi thể loại — nhà soạn nhạc vĩ đại của loài bò Wolfgang Amadeus Moozart từng phát hiện rằng một hợp âm cụ thể có xu hướng khiến bò khá khó chịu. Hợp âm này, được gọi là hợp âm bảy của động vật nhai lại, vì thế thường bị tránh trong mọi tác phẩm âm nhạc dành cho bò.
Không biết những chi tiết tinh tế trong lịch sử âm nhạc của loài bò, Farmer John quyết định phát bài hát yêu thích của mình qua loa trong chuồng. Nhiệm vụ của bạn là xác định tất cả các hợp âm bảy của động vật nhai lại trong bài hát này để ước lượng mức độ khó chịu mà nó sẽ gây ra cho đàn bò.
Bài hát FJ phát là một dãy gồm \(N\) nốt nhạc (\(1 \leq N \leq 20\,000\)), mỗi nốt là một số nguyên trong khoảng \(1 \ldots 88\). Một hợp âm bảy của động vật nhai lại được xác định bởi một dãy gồm \(C\) nốt phân biệt (\(1 \leq C \leq 10\)), cũng là các số nguyên trong khoảng \(1 \ldots 88\). Tuy nhiên, ngay cả khi các nốt này được chuyển giọng (cùng tăng hoặc cùng giảm một lượng) hoặc được sắp xếp lại, hợp âm vẫn là một hợp âm bảy của động vật nhai lại! Chẳng hạn, nếu 4 6 7 là một hợp âm bảy của động vật nhai lại, thì 3 5 6 (chuyển giọng \(-1\)), 6 8 9 (chuyển giọng \(+2\)), 6 4 7 (sắp xếp lại) và 5 3 6 (vừa chuyển giọng vừa sắp xếp lại) cũng đều là các hợp âm bảy của động vật nhai lại.
Một hợp âm bảy của động vật nhai lại là một dãy gồm \(C\) nốt liên tiếp thỏa mãn các tiêu chí trên. Vì thế, mỗi hợp âm được xác định duy nhất bởi vị trí bắt đầu của nó trong bài hát. Hãy xác định các chỉ số bắt đầu của tất cả các hợp âm bảy của động vật nhai lại.
Dòng đầu tiên chứa số lượng \(K\) hợp âm bảy của động vật nhai lại xuất hiện trong bài hát của FJ. Lưu ý rằng các lần xuất hiện khác nhau có thể chồng lấn nhau.
Mỗi dòng trong \(K\) dòng tiếp theo chứa chỉ số bắt đầu của một hợp âm bảy của động vật nhai lại (chỉ số 1 ứng với nốt đầu tiên trong bài hát của FJ, còn chỉ số \(N\) ứng với nốt cuối cùng). Các chỉ số phải được liệt kê theo thứ tự tăng dần.
Ví dụ 1
6
1
8
5
7
9
10
3
4
6
72
2
4Bài hát của FJ là \(1, 8, 5, 7, 9, 10\). Một hợp âm bảy của động vật nhai lại là một cách chuyển giọng/sắp xếp lại của \(4, 6, 7\).
Có hai hợp âm bảy của động vật nhai lại xuất hiện trong bài hát của FJ (và chúng thực sự chồng lấn nhau một nốt). Hợp âm thứ nhất là \(8, 5, 7\) (chuyển giọng \(+1\) rồi sắp xếp lại), bắt đầu tại chỉ số 2; hợp âm thứ hai là \(7, 9, 10\) (chuyển giọng \(+3\)), bắt đầu tại chỉ số 4.
USACO 2011 November Contest, Bronze Division — Moo Sick. Tác giả đề: Rob Seay.
Nghe nói xu hướng thời trang mới nhất là những con bò có hai đốm trên da, Farmer John đã mua cả một đàn bò hai đốm. Không may, các xu hướng thời trang thường thay đổi rất nhanh, và mốt thịnh hành nhất hiện nay lại là bò chỉ có một đốm!
FJ muốn giúp đàn bò của mình hợp thời hơn bằng cách sơn từng con sao cho hai đốm của nó hợp thành một. Da của một con bò được biểu diễn bằng một lưới ký tự kích thước \(N \times M\) (\(1 \leq N, M \leq 50\)) như sau:
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....
Ở đây, mỗi ký tự X biểu thị một phần của một đốm. Hai ký tự X thuộc cùng một đốm nếu chúng kề nhau theo chiều dọc hoặc chiều ngang (kề nhau theo đường chéo không được tính), vì vậy hình trên có đúng hai đốm. Mọi con bò trong đàn của FJ đều có đúng hai đốm.
FJ muốn dùng ít sơn nhất có thể để hợp nhất hai đốm thành một. Trong ví dụ trên, ông có thể làm được điều này bằng cách chỉ sơn thêm ba ký tự X (các ký tự mới được đánh dấu bằng * bên dưới để dễ nhìn hơn).
................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....
Hãy giúp FJ xác định số ký tự X mới ít nhất mà ông phải sơn để hợp nhất hai đốm thành một đốm lớn.
Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.
\(N\) dòng tiếp theo, mỗi dòng chứa một xâu độ dài \(M\) gồm các ký tự X và ., mô tả một hàng trong họa tiết trên da bò.
In số ký tự X mới ít nhất cần thêm vào họa tiết đầu vào để thu được một đốm duy nhất.
Ví dụ 1
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....3Họa tiết trong dữ liệu vào biểu diễn da một con bò với hai đốm riêng biệt, được đánh số 1 và 2 dưới đây:
................
..1111....222...
...1111....22...
.1111......222..
........22222...
.........222....
Ba ký tự X là đủ để nối hai đốm thành một:
................
..1111....222...
...1111X...22...
.1111..XX..222..
........22222...
.........222....
USACO 2011 November Contest, Bronze Division — Cow Beauty Pageant (Bronze Level). Tác giả đề: Brian Dean.