| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - Counting Haybales | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Cities and States | 100 (p) | 4.0s | 512M |
| 3 | USACO 2017 - Moocast | 100 (p) | 4.0s | 512M |
Farmer John vừa sắp xếp \(N\) kiện cỏ khô (\(1 \leq N \leq 100\,000\)) tại nhiều vị trí khác nhau dọc theo con đường chạy xuyên qua trang trại, được xem như một trục một chiều. Để đảm bảo chúng được đặt cách nhau hợp lý, hãy giúp ông trả lời \(Q\) truy vấn (\(1 \leq Q \leq 100\,000\)), mỗi truy vấn hỏi số kiện cỏ khô nằm trong một đoạn cụ thể trên con đường.
Dòng đầu tiên chứa \(N\) và \(Q\).
Dòng tiếp theo chứa \(N\) số nguyên phân biệt, mỗi số nằm trong khoảng \(0 \ldots 1\,000\,000\,000\), cho biết có một kiện cỏ khô tại mỗi vị trí tương ứng.
Mỗi dòng trong \(Q\) dòng tiếp theo chứa hai số nguyên \(A\) và \(B\) (\(0 \leq A \leq B \leq 1\,000\,000\,000\)), biểu thị một truy vấn về số kiện cỏ khô nằm giữa \(A\) và \(B\), tính cả hai đầu mút.
In \(Q\) dòng. Với mỗi truy vấn, in số kiện cỏ khô trong đoạn tương ứng.
Ví dụ 1
4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 102
2
3
4
1
0USACO 2016 December Contest, Silver — Counting Haybales. Tác giả đề: Nick Wu.
Để kích thích trí tuệ của đàn bò, Farmer John đã treo một tấm bản đồ lớn của Hoa Kỳ lên tường chuồng. Vì đàn bò dành nhiều giờ trong chuồng để nhìn tấm bản đồ này, chúng bắt đầu nhận thấy một số quy luật kỳ lạ. Chẳng hạn, hai thành phố Flint, MI và Miami, FL có một mối quan hệ rất đặc biệt: hai chữ cái đầu của Flint tạo thành mã tiểu bang (FL) của Miami, còn hai chữ cái đầu của Miami tạo thành mã tiểu bang (MI) của Flint.
Ta gọi hai thành phố là một "cặp đặc biệt" nếu chúng thỏa mãn tính chất này và thuộc hai tiểu bang khác nhau. Đàn bò muốn biết có bao nhiêu cặp thành phố đặc biệt. Hãy giúp chúng giải câu đố địa lý thú vị này!
Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 200\,000\)), là số thành phố trên bản đồ.
\(N\) dòng tiếp theo, mỗi dòng chứa hai xâu: tên một thành phố (một xâu gồm từ \(2\) đến \(10\) chữ cái in hoa) và mã tiểu bang gồm hai chữ cái của thành phố đó (một xâu gồm \(2\) chữ cái in hoa). Lưu ý rằng mã tiểu bang có thể là một mã như ZQ, không tương ứng với tiểu bang có thật nào của Hoa Kỳ. Có thể tồn tại nhiều thành phố cùng tên, nhưng chúng sẽ thuộc các tiểu bang khác nhau.
In số cặp thành phố đặc biệt.
Ví dụ 1
6
MIAMI FL
DALLAS TX
FLINT MI
CLEMSON SC
BOSTON MA
ORLANDO FL1USACO 2016 December Contest, Silver — Cities and States. Tác giả đề: Brian Dean.
\(N\) con bò của Farmer John (\(1 \leq N \leq 200\)) muốn tổ chức một hệ thống "moo-cast" khẩn cấp để truyền những thông điệp quan trọng cho nhau.
Thay vì rống gọi nhau từ xa, đàn bò quyết định tự trang bị bộ đàm, mỗi con một chiếc. Mỗi bộ đàm có bán kính truyền hữu hạn: một bộ đàm có công suất \(P\) chỉ có thể truyền tới những con bò khác cách nó không quá \(P\) (lưu ý rằng bò A có thể truyền tới bò B ngay cả khi bò B không thể truyền ngược lại, do công suất của bò A lớn hơn công suất của bò B). May mắn thay, đàn bò có thể chuyển tiếp thông điệp cho nhau theo một đường đi gồm nhiều chặng, nên không nhất thiết mọi con bò đều phải truyền trực tiếp được tới mọi con bò khác.
Do tính bất đối xứng của việc truyền bằng bộ đàm, xét cả khả năng chuyển tiếp, thông điệp phát từ một số con bò có thể tiếp cận nhiều con bò nhận hơn thông điệp phát từ những con khác. Hãy giúp đàn bò xác định số lượng bò lớn nhất mà một thông điệp phát từ một con bò duy nhất có thể tiếp cận.
Dòng đầu tiên chứa \(N\).
\(N\) dòng tiếp theo, mỗi dòng chứa tọa độ \(x\), \(y\) của một con bò (các số nguyên trong khoảng \(0 \ldots 25\,000\)), tiếp theo là \(p\), công suất của bộ đàm mà con bò này mang.
In một dòng chứa số lượng bò lớn nhất mà một thông điệp phát từ một con bò duy nhất có thể tiếp cận. Con bò phát thông điệp cũng được tính trong số này.
Ví dụ 1
4
1 3 5
5 4 3
7 2 1
6 1 13Trong ví dụ trên, thông điệp phát từ bò \(1\) có thể tiếp cận tổng cộng \(3\) con bò, tính cả bò \(1\).
USACO 2016 December Contest, Silver — Moocast. Tác giả đề: Brian Dean.