| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2021 - Comfortable Cows | 100 (p) | 4.0s | 512M |
| 2 | USACO 2021 - Year of the Cow | 100 (p) | 4.0s | 512M |
| 3 | USACO 2021 - Just Green Enough | 100 (p) | 4.0s | 512M |
Đồng cỏ của Farmer Nhoj được xem là một lưới lớn gồm các ô vuông hai chiều. Ban đầu, đồng cỏ trống.
Farmer Nhoj lần lượt thêm \(N\) con bò vào đồng cỏ (\(1\le N\le10^5\)). Con bò thứ \(i\) chiếm một ô \((x_i,y_i)\) khác mọi ô đã có bò (\(0\le x_i,y_i\le1000\)).
Một con bò được gọi là "thoải mái" nếu có đúng ba con bò khác kề với nó theo phương ngang hoặc dọc. Không may, những con bò quá thoải mái thường giảm sản lượng sữa, nên Farmer Nhoj muốn thêm bò cho đến khi không còn con nào, kể cả các con mới thêm, cảm thấy thoải mái. Tọa độ \(x\) và \(y\) của những con bò được thêm không nhất thiết nằm trong đoạn \(0\ldots1000\).
Với mỗi \(i\) trong đoạn \(1\ldots N\), giả sử ban đầu đồng cỏ chỉ có các bò \(1\ldots i\). Hãy tính số bò ít nhất Farmer Nhoj cần thêm để không còn con bò nào thoải mái.
Dòng đầu tiên chứa số nguyên \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên, cách nhau bởi dấu cách, là tọa độ \((x,y)\) của ô có một con bò.
Với mỗi \(i\) trong \(1\ldots N\), in số bò ít nhất Farmer Nhoj cần thêm trên một trong \(N\) dòng riêng biệt.
Tất cả các test tuân theo các ràng buộc đã nêu.
Ví dụ 1
9
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2
4 10
0
0
1
0
0
1
2
4Với \(i=4\), Farmer Nhoj phải thêm một con bò tại \((2,1)\) để bò tại \((1,1)\) không còn thoải mái.
Với \(i=9\), cách tốt nhất là thêm bò tại \((2,0)\), \((3,0)\), \((2,-1)\) và \((2,3)\).
USACO 2021 February Contest, Silver - Comfortable Cows: https://usaco.org/index.php?page=viewproblem2&cpid=1110
Tác giả: Benjamin Qi.
Những chú bò của Farmer John rất hào hứng khi biết Tết Nguyên đán vừa được tổ chức, mở đầu năm Sửu, một năm luôn được loài bò yêu thích.
Mười hai con giáp của lịch Trung Quốc lặp theo chu kỳ 12 năm: Sửu, Dần, Mão, Thìn, Tỵ, Ngọ, Mùi, Thân, Dậu, Tuất, Hợi, Tý, rồi lại đến Sửu. Ít người biết rằng vào mỗi năm Sửu, một cổng thời gian bí ẩn mở ra, cho phép bò đi tới bất kỳ năm Sửu nào khác trong quá khứ hoặc tương lai.
Bessie muốn dùng cổng thời gian mở trong năm nay để thăm \(N\) tổ tiên nổi tiếng từng sống từ lâu, với \(1\le N\le 0x10000\). Viết cận của \(N\) theo hệ thập lục phân rất hợp với năm Sửu; lưu ý 0x10000 bằng 65536.
Không may, du hành thời gian khiến Bessie hơi buồn nôn nên cô muốn thực hiện nhiều nhất \(K\) lần nhảy qua thời gian (\(1\le K\le N\)). Hãy tính số năm ít nhất để Bessie thăm tất cả tổ tiên rồi trở về năm hiện tại, với tổng cộng không quá \(K\) lần nhảy qua thời gian.
Bessie không bắt buộc dùng cổng trong một năm Sửu. Các cổng nối ngày đầu tiên của mọi năm Sửu với nhau; chẳng hạn, nếu Bessie đến một cổng rồi chờ 12 năm tới cổng tiếp theo, cô mất đúng 12 năm. Bessie bắt đầu vào ngày đầu tiên của năm Sửu hiện tại nên có thể lập tức đi ngược thời gian. Không tổ tiên nào của Bessie sống trong năm Sửu.
Dòng đầu tiên chứa \(N\) và \(K\). \(N\) dòng tiếp theo chứa \(N\) số nguyên phân biệt trong đoạn \(1\ldots10^9\), mỗi số cho biết một trong \(N\) tổ tiên của Bessie sống cách đây bao nhiêu năm.
In số năm ít nhất để Bessie thăm tất cả tổ tiên rồi trở về năm hiện tại.
Tất cả các test tuân theo các ràng buộc đã nêu.
Ví dụ 1
5 3
101
85
100
46
9536Một cách để Bessie thăm tất cả tổ tiên và trở về trong 36 năm là:
USACO 2021 February Contest, Silver - Year of the Cow: https://usaco.org/index.php?page=viewproblem2&cpid=1111
Tác giả: Brian Dean và David Yang.
Đồng cỏ của Farmer John được xem là một lưới \(N\times N\) gồm các ô cỏ vuông (\(1\le N\le500\)). Do đất không đồng đều, cỏ ở một số ô xanh hơn các ô khác. Mỗi ô \((i,j)\) có một mức độ xanh nguyên \(G(i,j)\) trong đoạn \(1\ldots200\).
Farmer John muốn chụp ảnh một lưới con hình chữ nhật của đồng cỏ. Ông muốn lưới con đủ xanh nhưng không xanh quá mức, nên quyết định chụp một lưới con có giá trị nhỏ nhất của \(G\) đúng bằng 100. Hãy xác định số bức ảnh khác nhau có thể chụp.
Lưới con có thể lớn bằng toàn bộ đồng cỏ hoặc nhỏ chỉ một ô. Tổng cộng có \(N^2(N+1)^2/4\) lưới con; giá trị này có thể không vừa trong số nguyên 32 bit nên có thể cần kiểu số nguyên 64 bit như long long trong C++.
Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa \(N\) số nguyên; tất cả các dòng cùng mô tả các giá trị \(G(i,j)\) của đồng cỏ \(N\times N\).
In số bức ảnh phân biệt Farmer John có thể chụp, tức số lưới con hình chữ nhật có mức độ xanh nhỏ nhất đúng bằng 100. Kết quả có thể cần kiểu số nguyên 64 bit.
Ví dụ 1
3
57 120 87
200 100 150
2 141 1358USACO 2021 February Contest, Silver - Just Green Enough: https://usaco.org/index.php?page=viewproblem2&cpid=1112
Tác giả: Brian Dean.