| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2020 - Swapity Swapity Swap | 100 (p) | 4.0s | 512M |
| 2 | USACO 2020 - Triangles | 100 (p) | 4.0s | 512M |
| 3 | USACO 2020 - Clock Tree | 100 (p) | 4.0s | 512M |
\(N\) con bò của Farmer John (\(1\le N\le 10^5\)) đang đứng thành một hàng. Với mỗi \(1\le i\le N\), con bò thứ \(i\) tính từ bên trái mang nhãn \(i\).
Farmer John đã nghĩ ra một bài tập thể dục buổi sáng mới cho đàn bò. Ông đưa cho đàn bò \(M\) cặp số nguyên \((L_1,R_1),\ldots,(L_M,R_M)\), trong đó \(1\leq M\leq 100\). Sau đó, ông yêu cầu chúng lặp lại chính xác \(K\) lần (\(1\le K\le 10^9\)) quy trình gồm \(M\) bước sau:
Sau khi đàn bò đã lặp lại quy trình này đúng \(K\) lần, với mỗi \(1\le i\le N\), hãy in nhãn của con bò thứ \(i\) tính từ bên trái.
Dòng đầu tiên chứa \(N\), \(M\) và \(K\). Với mỗi \(1\le i\le M\), dòng thứ \(i+1\) chứa \(L_i\) và \(R_i\), là hai số nguyên thuộc đoạn \(1\ldots N\) và thỏa mãn \(L_i<R_i\).
Trên dòng thứ \(i\) của kết quả, in phần tử thứ \(i\) của mảng sau khi dãy chỉ dẫn đã được thực hiện \(K\) lần.
Ví dụ 1
7 2 2
2 5
3 71
2
4
3
5
7
6Ban đầu, thứ tự các con bò từ trái sang phải là \([1,2,3,4,5,6,7]\). Sau bước đầu tiên của quy trình, thứ tự là \([1,5,4,3,2,6,7]\). Sau bước thứ hai của quy trình, thứ tự là \([1,5,7,6,2,3,4]\). Lặp lại cả hai bước lần thứ hai sẽ thu được kết quả của ví dụ.
USACO 2020 February Contest, Silver - Swapity Swapity Swap: https://usaco.org/index.php?page=viewproblem2&cpid=1014
Tác giả: Brian Dean.
Farmer John muốn tạo một đồng cỏ hình tam giác cho đàn bò của mình.
Có \(N\) cọc hàng rào (\(3\le N\le 10^5\)) nằm tại các điểm phân biệt \((X_1,Y_1),\ldots,(X_N,Y_N)\) trên bản đồ hai chiều của trang trại. Ông có thể chọn ba cọc làm các đỉnh của đồng cỏ hình tam giác, miễn là một cạnh của tam giác song song với trục \(x\) và một cạnh khác song song với trục \(y\).
Tổng diện tích của tất cả các đồng cỏ mà FJ có thể tạo là bao nhiêu?
Dòng đầu tiên chứa \(N\).
Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(X_i\) và \(Y_i\), mỗi số thuộc đoạn \(-10^4\ldots 10^4\), mô tả vị trí của một cọc hàng rào.
Vì tổng diện tích không nhất thiết là số nguyên và có thể rất lớn, hãy in phần dư khi hai lần tổng diện tích được chia cho \(10^9+7\).
Ví dụ 1
4
0 0
0 1
1 0
1 23Các cọc hàng rào \((0,0)\), \((1,0)\) và \((1,2)\) tạo thành một tam giác có diện tích \(1\), còn \((0,0)\), \((1,0)\) và \((0,1)\) tạo thành một tam giác có diện tích \(0.5\). Vì vậy, đáp án là \(2\cdot(1+0.5)=3\).
USACO 2020 February Contest, Silver - Triangles: https://usaco.org/index.php?page=viewproblem2&cpid=1015
Tác giả: Travis Hance và Nick Wu.
Chuồng mới của Farmer John có một thiết kế thực sự kỳ lạ: chuồng gồm \(N\) căn phòng (\(2\leq N\leq 2500\)), được đánh số thuận tiện \(1\ldots N\), và \(N-1\) hành lang. Mỗi hành lang nối một cặp phòng sao cho có thể đi từ bất kỳ phòng nào đến bất kỳ phòng nào khác qua một dãy hành lang.
Mỗi phòng trong chuồng có một chiếc đồng hồ tròn trên tường, với các số nguyên tiêu chuẩn \(1\ldots 12\) xung quanh mặt đồng hồ. Tuy nhiên, những chiếc đồng hồ này chỉ có một kim, và kim luôn chỉ thẳng vào một trong các số trên mặt đồng hồ (không bao giờ chỉ vào khoảng giữa hai số).
Bessie muốn đồng bộ tất cả đồng hồ trong chuồng để chúng đều chỉ số \(12\). Tuy nhiên, cô khá đơn giản, và trong lúc đi quanh chuồng, mỗi khi bước vào một phòng, cô lại dịch kim đồng hồ trong phòng đó tiến thêm một vị trí. Chẳng hạn, nếu đồng hồ đang chỉ số \(5\) thì sau đó sẽ chỉ số \(6\); nếu đang chỉ số \(12\) thì sau đó sẽ chỉ số \(1\). Nếu Bessie bước vào cùng một phòng nhiều lần, mỗi lần bước vào cô đều làm đồng hồ trong phòng đó tiến thêm một vị trí.
Hãy xác định số căn phòng mà Bessie có thể bắt đầu hành trình sao cho cô có khả năng đưa tất cả đồng hồ về số \(12\). Lưu ý rằng ban đầu Bessie không làm đồng hồ trong phòng xuất phát tiến lên, nhưng cô sẽ làm nó tiến lên mỗi khi quay lại phòng đó. Các đồng hồ không tự chạy; một đồng hồ chỉ tiến lên khi Bessie bước vào phòng chứa nó. Ngoài ra, một khi Bessie đi vào một hành lang, cô phải đi ra ở đầu bên kia (không được đi một phần hành lang rồi quay ngược về cùng phòng).
Dòng đầu tiên chứa \(N\). Dòng tiếp theo chứa \(N\) số nguyên, mỗi số thuộc đoạn \(1\ldots 12\), cho biết trạng thái ban đầu của đồng hồ trong từng phòng. Mỗi dòng trong \(N-1\) dòng tiếp theo mô tả một hành lang bằng hai số nguyên \(a\) và \(b\), mỗi số thuộc đoạn \(1\ldots N\), là số hiệu hai phòng được hành lang nối với nhau.
In số căn phòng mà Bessie có thể xuất phát để có thể đưa tất cả đồng hồ về số \(12\).
Ví dụ 1
4
11 10 11 11
1 2
2 3
2 41Trong ví dụ này, Bessie có thể đưa tất cả đồng hồ về số \(12\) khi và chỉ khi cô xuất phát ở phòng \(2\) (chẳng hạn, bằng cách lần lượt đi đến các phòng \(1\), \(2\), \(3\), \(2\) và cuối cùng là \(4\)).
USACO 2020 February Contest, Silver - Clock Tree: https://usaco.org/index.php?page=viewproblem2&cpid=1016
Tác giả: Brian Dean.