| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2015 - Marathon | 100 (p) | 4.0s | 512M |
| 2 | USACO 2015 - Crosswords | 100 (p) | 4.0s | 512M |
| 3 | USACO 2015 - Cow Jog | 100 (p) | 4.0s | 512M |
| 4 | USACO 2015 - Learning by Example | 100 (p) | 4.0s | 512M |
Không hài lòng với tình trạng sức khỏe kém của đàn bò, Farmer John đăng ký cho chúng tham gia nhiều hoạt động rèn luyện thể chất khác nhau. Cô bò quý Bessie của ông tham gia một lớp chạy bộ, nơi cô được kỳ vọng cuối cùng sẽ chạy một cuộc marathon qua khu trung tâm của thành phố gần trang trại của Farmer John!
Đường chạy marathon gồm \(N\) checkpoint (\(3 \le N \le 100\,000\)) phải được ghé thăm theo thứ tự, trong đó checkpoint 1 là điểm xuất phát và checkpoint \(N\) là đích đến. Bessie lẽ ra phải lần lượt đi qua tất cả các checkpoint này, nhưng vì là một cô bò lười biếng, cô quyết định sẽ bỏ qua nhiều nhất một checkpoint để rút ngắn tổng quãng đường. Tuy nhiên, cô không thể bỏ qua checkpoint 1 hoặc checkpoint \(N\), vì làm vậy sẽ quá dễ bị phát hiện.
Hãy giúp Bessie tìm quãng đường ngắn nhất mà cô phải chạy nếu được bỏ qua nhiều nhất một checkpoint.
Lưu ý rằng vì đường chạy nằm trong khu trung tâm với mạng lưới đường phố dạng ô vuông, khoảng cách giữa hai checkpoint tại \((x_1,y_1)\) và \((x_2,y_2)\) được tính bằng \(|x_1-x_2|+|y_1-y_2|\). Cách đo khoảng cách này — lấy độ chênh lệch theo \(x\) cộng với độ chênh lệch theo \(y\) — đôi khi được gọi là khoảng cách “Manhattan”, vì trong một mạng lưới đường phố ở trung tâm thành phố, ta có thể di chuyển song song với trục \(x\) hoặc trục \(y\), nhưng không thể đi theo đường thẳng trực tiếp “như chim bay”.
Dòng đầu tiên chứa giá trị \(N\).
\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) cách nhau bởi dấu cách, biểu diễn một checkpoint (\(-1000 \le x \le 1000\), \(-1000 \le y \le 1000\)). Các checkpoint được cho theo đúng thứ tự phải ghé thăm. Lưu ý rằng đường chạy có thể tự cắt nhau nhiều lần, và nhiều checkpoint có thể nằm tại cùng một vị trí thực tế. Khi Bessie bỏ qua một checkpoint như vậy, cô chỉ bỏ qua một lần xuất hiện của checkpoint đó, chứ không bỏ qua mọi checkpoint nằm tại cùng vị trí.
In ra quãng đường ngắn nhất Bessie có thể chạy khi được bỏ qua nhiều nhất một checkpoint. Đừng quên kết thúc dữ liệu ra bằng một ký tự xuống dòng.
Ví dụ 1
4
0 0
8 3
11 -1
10 014Trong ví dụ này, bỏ qua checkpoint tại \((8,3)\) cho tổng quãng đường nhỏ nhất là 14.
USACO 2014 December Contest, Bronze — Marathon. Tác giả đề: Nick Wu, 2014.
Giống như mọi cô bò khác, Bessie thích giải ô chữ. Không may, cô em Elsie đã làm đổ sữa lên khắp cuốn sách ô chữ của Bessie, khiến chữ bị nhòe và Bessie khó nhìn ra vị trí bắt đầu của mỗi gợi ý. Nhiệm vụ của bạn là giúp Bessie khôi phục cách đánh số các gợi ý!
Bạn được cho một ô chữ chưa đánh số dưới dạng lưới \(N\) hàng và \(M\) cột (\(3 \le N \le 50\), \(3 \le M \le 50\)). Một số ô là ô trống (thường có màu trắng), còn một số ô bị chặn (thường có màu đen). Với bố cục này, việc đánh số gợi ý là một quy trình đơn giản gồm hai bước logic:
Bước 1: Xác định mỗi ô có bắt đầu một gợi ý theo chiều ngang hoặc chiều dọc hay không. Nếu một ô bắt đầu một gợi ý theo chiều ngang, ô đó phải là ô trống, ô ngay bên trái phải bị chặn hoặc nằm ngoài lưới ô chữ, và hai ô bên phải phải là ô trống (nghĩa là một gợi ý theo chiều ngang chỉ có thể biểu diễn một từ gồm ít nhất 3 ký tự). Quy tắc đối với một ô bắt đầu gợi ý theo chiều dọc cũng tương tự: ô phía trên phải bị chặn hoặc nằm ngoài lưới, và hai ô phía dưới phải là ô trống.
Bước 2: Gán số cho mỗi ô bắt đầu một gợi ý. Các ô được gán các số liên tiếp bắt đầu từ 1, theo đúng thứ tự đọc sách: các ô ở hàng trên cùng được gán số từ trái sang phải, sau đó đến hàng thứ hai, v.v. Chỉ những ô bắt đầu một gợi ý mới được gán số.
Ví dụ, xét lưới sau, trong đó . biểu thị một ô trống và # biểu thị một ô bị chặn.
...
#..
...
..#
.##
Các ô có thể bắt đầu một gợi ý theo chiều ngang hoặc chiều dọc được đánh dấu bằng ! dưới đây:
!!!
#..
!..
..#
.##
Nếu gán số cho các ô này, ta được:
123
#..
4..
..#
.##
Lưu ý rằng ô chữ được mô tả trong dữ liệu vào có thể không thỏa mãn những điều kiện thường thấy ở các ô chữ đã xuất bản. Chẳng hạn, một số ô trống có thể không thuộc bất kỳ gợi ý nào.
Dòng đầu tiên chứa \(N\) và \(M\), cách nhau bởi một dấu cách.
\(N\) dòng tiếp theo, mỗi dòng mô tả một hàng của lưới và chứa \(M\) ký tự. Mỗi ký tự là . (một ô trống) hoặc # (một ô bị chặn).
Trên dòng đầu tiên, in ra số lượng gợi ý.
Trên mỗi dòng còn lại, in ra hàng và cột xác định vị trí của một gợi ý, theo thứ tự đã mô tả ở trên. Ô trên cùng bên trái có vị trí \((1,1)\). Ô dưới cùng bên phải có vị trí \((N,M)\).
Ví dụ 1
5 3
...
#..
...
..#
.##4
1 1
1 2
1 3
3 1USACO 2014 December Contest, Bronze — Crosswords. Tác giả đề: Mark Gordon, 2014.
Đàn bò lại ra ngoài vận động móng guốc! Có \(N\) cô bò đang chạy bộ trên một đường chạy một làn dài vô hạn (\(1 \le N \le 100\,000\)). Mỗi cô bò xuất phát tại một vị trí khác nhau trên đường chạy, và một số cô bò chạy với tốc độ khác nhau.
Vì đường chạy chỉ có một làn, các cô bò không thể vượt nhau. Khi một cô bò nhanh hơn bắt kịp một cô bò khác, cô phải chạy chậm lại để tránh đâm vào cô bò phía trước và trở thành một thành viên của cùng nhóm chạy.
Cuối cùng, sẽ không còn cô bò nào bắt kịp cô bò khác. Farmer John muốn biết khi đó còn lại bao nhiêu nhóm. Hãy giúp ông tính con số này.
Dòng đầu tiên chứa số nguyên \(N\).
\(N\) dòng tiếp theo, mỗi dòng chứa vị trí ban đầu và tốc độ của một cô bò. Vị trí là một số nguyên không âm, còn tốc độ là một số nguyên dương; cả hai số đều không vượt quá 1 tỷ. Tất cả các cô bò xuất phát tại những vị trí khác nhau, và các vị trí này được cho theo thứ tự tăng dần trong dữ liệu vào.
In ra một số nguyên duy nhất cho biết số nhóm còn lại.
Ví dụ 1
5
0 1
1 2
2 3
3 2
6 12USACO 2014 December Contest, Bronze — Cow Jog. Tác giả đề: Mark Gordon, 2014.
Farmer John đã đọc rất nhiều về lĩnh vực học máy đầy thú vị, nơi người ta có thể khám phá những quy luật thú vị và đôi khi bất ngờ bằng cách phân tích dữ liệu lớn (ông thậm chí còn bắt đầu gọi một trong những cánh đồng ở trang trại là “cánh đồng học máy”!). FJ quyết định dùng dữ liệu về đàn bò hiện có để xây dựng một bộ phân loại tự động có thể dự đoán một cô bò có đốm hay không.
Không may, FJ không giỏi theo dõi dữ liệu về đàn bò của mình. Với mỗi cô bò trong số \(N\) cô bò (\(1 \le N \le 50\,000\)), ông chỉ biết khối lượng của cô bò và cô bò đó có đốm hay không. Mỗi cô bò có một khối lượng khác nhau. Từ dữ liệu này, ông xây dựng một thứ gọi là “bộ phân loại láng giềng gần nhất”. Để dự đoán một cô bò mới \(C\) có đốm hay không, trước tiên FJ tìm cô bò \(C'\) trong đàn có khối lượng gần với khối lượng của \(C\) nhất. Nếu \(C'\) có đốm, FJ dự đoán \(C\) cũng có đốm; nếu \(C'\) không có đốm, FJ cũng dự đoán như vậy về \(C\). Nếu không tồn tại một láng giềng gần nhất \(C'\) duy nhất mà có hai cô bò của FJ cùng gần nhất, thì FJ dự đoán \(C\) có đốm nếu một hoặc cả hai láng giềng gần nhất này có đốm.
FJ muốn thử nghiệm bộ dự đoán đốm tự động mới trên một nhóm bò mới vừa đến trang trại. Sau khi cân những cô bò này, ông nhận thấy lô bò mới có một cô bò ứng với mỗi khối lượng nguyên từ \(A\) đến \(B\), kể cả hai đầu. Hãy xác định có bao nhiêu cô bò trong số này sẽ được bộ phân loại mới của FJ phân loại là có đốm. Lưu ý rằng bộ phân loại chỉ đưa ra quyết định dựa trên dữ liệu từ \(N\) cô bò hiện có của FJ, chứ không dựa trên bất kỳ cô bò mới nào. Cũng lưu ý rằng vì \(A\) và \(B\) đều có thể rất lớn, chương trình của bạn nhiều khả năng sẽ không đủ nhanh nếu lặp qua từng số từ \(A\) đến \(B\) để đếm.
Dòng đầu tiên chứa ba số nguyên \(N\), \(A\) và \(B\) (\(1 \le A \le B \le 1\,000\,000\,000\)).
\(N\) dòng tiếp theo, mỗi dòng mô tả một cô bò. Mỗi dòng chứa S W, biểu thị một cô bò có đốm với khối lượng \(W\), hoặc NS W, biểu thị một cô bò không có đốm với khối lượng \(W\). Các khối lượng đều là số nguyên trong khoảng từ 1 đến \(1\,000\,000\,000\).
In ra một số nguyên duy nhất là số bò mới mà thuật toán của FJ sẽ phân loại là có đốm.
Ví dụ 1
3 1 10
S 10
NS 4
S 16Trong ví dụ này, các cô bò mới có khối lượng 1, 2, 7, 8, 9 và 10 đều sẽ được phân loại là có đốm.
USACO 2014 December Contest, Bronze — Learning by Example. Tác giả đề: Brian Dean, 2014.