| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - The Lost Cow | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Bovine Genomics | 100 (p) | 4.0s | 512M |
| 3 | USACO 2017 - Modern Art | 100 (p) | 4.0s | 512M |
Farmer John đã làm lạc mất cô bò Bessie quý giá và ông cần tìm cô!
May mắn thay, chỉ có một con đường dài chạy ngang qua trang trại, và Farmer John biết rằng Bessie phải đang ở một vị trí nào đó trên con đường này. Nếu coi con đường như một trục số, Farmer John hiện đang ở vị trí \(x\) còn Bessie đang ở vị trí \(y\) (Farmer John không biết vị trí này). Nếu biết Bessie ở đâu, Farmer John có thể đi thẳng đến chỗ cô với quãng đường \(|x-y|\). Tiếc rằng bên ngoài trời tối và Farmer John không thể nhìn thấy gì. Cách duy nhất để tìm Bessie là đi tới đi lui cho đến khi ông tới được vị trí của cô.
Trong lúc tìm chiến lược tốt nhất để đi tới đi lui, Farmer John tham khảo các công trình nghiên cứu khoa học máy tính và khá thích thú khi phát hiện rằng bài toán chính xác này không những đã được các nhà khoa học máy tính nghiên cứu trước đây mà thực sự còn được gọi là "Bài toán chú bò đi lạc" (điều này hoàn toàn có thật!).
Phương án được khuyến nghị để Farmer John tìm Bessie là di chuyển đến vị trí \(x+1\), sau đó đổi hướng và di chuyển đến vị trí \(x-2\), rồi đến vị trí \(x+4\), và cứ tiếp tục như vậy theo hình "zích zắc", trong đó sau mỗi bước, khoảng cách đến vị trí xuất phát ban đầu lại gấp đôi lần trước. Qua việc nghiên cứu các thuật toán giải bài toán chú bò đi lạc, ông biết rằng cách này đảm bảo trong trường hợp xấu nhất, trước khi tìm thấy Bessie, ông sẽ đi không quá \(9\) lần khoảng cách trực tiếp \(|x-y|\) giữa hai người (điều này cũng đúng, và hệ số \(9\) thực sự là bảo đảm trường hợp xấu nhất nhỏ nhất mà một chiến lược bất kỳ có thể đạt được).
Farmer John muốn kiểm chứng kết quả này. Cho \(x\) và \(y\), hãy tính tổng quãng đường ông sẽ đi theo chiến lược tìm kiếm zích zắc nêu trên cho đến khi tìm thấy Bessie.
Dòng duy nhất chứa hai số nguyên phân biệt \(x\) và \(y\), cách nhau bởi dấu cách. Cả hai đều nằm trong khoảng \(0 \ldots 1\,000\).
In một dòng chứa quãng đường Farmer John sẽ đi để đến chỗ Bessie.
Ví dụ 1
3 69USACO 2017 US Open Contest, Bronze — The Lost Cow. Tác giả đề: Brian Dean.
Farmer John sở hữu \(N\) con bò có đốm và \(N\) con bò không có đốm. Vừa hoàn thành một khóa học về di truyền học ở bò, ông tin rằng các đốm trên bò của mình là do những đột biến tại một vị trí duy nhất trong hệ gen của bò.
Farmer John phải bỏ ra một khoản chi phí rất lớn để giải trình tự hệ gen của đàn bò. Mỗi hệ gen là một chuỗi độ dài \(M\) được tạo bởi bốn ký tự A, C, G và T. Khi căn chỉnh hệ gen của các con bò, ông thu được một bảng như sau, minh họa với \(N=3\):
Vị trí: 1 2 3 4 5 6 7 ... M
Bò đốm 1: A A T C C C A ... T
Bò đốm 2: G A T T G C A ... A
Bò đốm 3: G G T C G C A ... A
Bò không đốm 1: A C T C C C A ... G
Bò không đốm 2: A C T C G C A ... T
Bò không đốm 3: A C T T C C A ... T
Quan sát kỹ bảng này, ông phỏng đoán rằng vị trí \(2\) có thể là một vị trí trong hệ gen giải thích được đặc điểm có đốm. Nghĩa là chỉ cần nhìn vào ký tự tại vị trí này, Farmer John có thể dự đoán con bò nào có đốm và con bò nào không có đốm (ở đây, A hoặc G biểu thị bò đốm còn C biểu thị bò không đốm; T không liên quan vì không xuất hiện ở vị trí \(2\) trong bất kỳ con bò nào của Farmer John). Riêng vị trí \(1\) không đủ để giải thích đặc điểm có đốm, vì ký tự A tại vị trí này có thể thuộc về một con bò đốm hoặc một con bò không đốm.
Cho hệ gen của đàn bò Farmer John, hãy đếm số vị trí mà mỗi vị trí tự nó có thể giải thích được đặc điểm có đốm.
Dòng đầu tiên chứa \(N\) và \(M\), cả hai đều là số nguyên dương không lớn hơn \(100\). \(N\) dòng tiếp theo, mỗi dòng chứa một chuỗi gồm \(M\) ký tự, mô tả hệ gen của các con bò đốm. \(N\) dòng cuối mô tả hệ gen của các con bò không đốm.
In số vị trí trong hệ gen có khả năng giải thích đặc điểm có đốm (một số nguyên trong khoảng \(0 \ldots M\)). Một vị trí có khả năng giải thích đặc điểm có đốm nếu chỉ bằng cách quan sát vị trí đó trong hệ gen, ta có thể dự đoán hoàn toàn chính xác đặc điểm có đốm trong quần thể bò của Farmer John.
Ví dụ 1
3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT1USACO 2017 US Open Contest, Bronze — Bovine Genomics. Tác giả đề: Brian Dean.
Giới phê bình nghệ thuật trên toàn thế giới chỉ mới bắt đầu công nhận thiên tài sáng tạo của Picowso, nữ họa sĩ bò vĩ đại.
Picowso vẽ tranh theo một cách rất đặc biệt. Cô bắt đầu với một bức vẽ trống kích thước \(N \times N\), được biểu diễn bởi một lưới \(N \times N\) chứa toàn số \(0\), trong đó số \(0\) biểu thị một ô còn trống trên bức vẽ. Sau đó, cô vẽ \(9\) hình chữ nhật lên bức vẽ, mỗi hình bằng một trong \(9\) màu (được đánh số tiện lợi từ \(1 \ldots 9\)). Chẳng hạn, cô có thể bắt đầu bằng cách tô một hình chữ nhật màu \(2\), tạo ra bức vẽ trung gian sau:
2220
2220
2220
0000
Tiếp theo, cô có thể tô một hình chữ nhật màu \(7\):
2220
2777
2777
0000
Rồi cô có thể tô một hình chữ nhật nhỏ màu \(3\):
2230
2737
2777
0000
Các cạnh của mỗi hình chữ nhật song song với các cạnh của bức vẽ; một hình chữ nhật có thể lớn bằng toàn bộ bức vẽ hoặc nhỏ chỉ bằng một ô. Mỗi màu từ \(1 \ldots 9\) được dùng đúng một lần, mặc dù các màu được tô sau có thể che phủ hoàn toàn một số màu được tô trước.
Cho trạng thái cuối cùng của bức vẽ, hãy đếm xem có bao nhiêu màu vẫn còn nhìn thấy trên bức vẽ có thể đã được tô đầu tiên.
Dòng đầu tiên chứa \(N\), kích thước của bức vẽ (\(1 \leq N \leq 10\)). \(N\) dòng tiếp theo mô tả bức tranh cuối cùng, mỗi dòng chứa \(N\) chữ số trong khoảng \(0 \ldots 9\). Dữ liệu vào được đảm bảo là đã được vẽ theo cách mô tả ở trên, bằng cách lần lượt tô các hình chữ nhật với những màu khác nhau.
Trong số tất cả các màu nhìn thấy được trên bức vẽ cuối cùng, hãy in ra số màu có thể đã được tô đầu tiên.
Ví dụ 1
4
2230
2737
2777
00001Trong ví dụ này, chỉ màu \(2\) có thể đã được tô đầu tiên. Rõ ràng màu \(3\) phải được tô sau màu \(7\), và màu \(7\) phải được tô sau màu \(2\).
USACO 2017 US Open Contest, Bronze — Modern Art. Tác giả đề: Brian Dean.