| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2019 - Tree Boxes | 100 (p) | 4.0s | 512M |
| 2 | USACO 2019 - Compound Escape | 100 (p) | 4.0s | 512M |
| 3 | USACO 2019 - Valleys | 100 (p) | 4.0s | 512M |
Farmer John dự định xây dựng \(N\) trang trại (\(1 \leq N \leq 10^5\)), được nối với nhau bằng \(N-1\) con đường tạo thành một cây. Thông thường, mỗi khi một trang trại của ông gặp sự cố, ông không được cho biết cụ thể trang trại nào đang gặp sự cố. Thay vào đó, ông được thông báo rằng một trong các trang trại trên đường đi từ một trang trại \(A\) tới một trang trại khác \(B\) đang gặp sự cố. Điều này thường khiến Farmer John bối rối, vì ông thường lái máy kéo địa hình và không quen thuộc với hệ thống đường sá.
Farmer John coi vị trí của một trang trại là một điểm 2D. Ông muốn được thông báo rằng có sự cố tại một trong những trang trại nằm trong một hình chữ nhật có các cạnh song song với trục tọa độ được chỉ định. Bessie nói với ông rằng yêu cầu này hơi quá tham vọng, nên ông sẽ hài lòng nếu được thông báo bằng nhiều nhất hai hình chữ nhật có các cạnh song song với trục tọa độ, sao cho giao của chúng (xét trên tập các trang trại) là rỗng và hợp của chúng đúng bằng tập các trang trại trên đường đi từ \(A\) tới \(B\). Bạn phải giúp Farmer John xác định vị trí xây các trang trại sao cho điều kiện này được thỏa mãn.
Đây là một bài tương tác; bạn sẽ không sử dụng vào/ra chuẩn (hoặc vào/ra tệp). Những lời giải sử dụng vào/ra chuẩn (hoặc vào/ra tệp) sẽ bị loại. Tuy nhiên, bạn ĐƯỢC PHÉP sử dụng biến toàn cục và biến tĩnh. Bạn phải cài đặt các hàm sau để giúp Farmer John:
void addRoad(int A, int B): xử lý một con đường giữa trang trại \(A\) và \(B\) (\(0 \le A, B \le N - 1\)).void buildFarms(): xác định nơi Farmer John nên xây tất cả các trang trại.void notifyFJ(int A, int B): thông báo cho Farmer John bằng một hoặc hai hình chữ nhật thỏa mãn các điều kiện nêu trên.Phần cài đặt các hàm trên của bạn có thể gọi các hàm được cung cấp dưới đây. Bạn có thể giả sử rằng \(\texttt{notifyFJ}\) sẽ được gọi \(Q\) lần (\(1 \leq Q \leq 10^5\)).
int getN(): lấy giá trị của \(N\).int getQ(): lấy giá trị của \(Q\).void setFarmLocation(int ID, int X, int Y): xác định rằng Farmer John nên xây trang trại \(ID\) (\(0 \le ID \le N-1\)) tại vị trí \((X,Y)\), trong đó \((1 \le X, Y \le N)\). Chỉ được gọi từ \(\texttt{buildFarms}\).void addBox(int X1, int Y1, int X2, int Y2): thêm một hình chữ nhật vào thông báo cho Farmer John, trong đó \((1 \le X1 \le X2 \le N)\) và \((1 \le Y1 \le Y2 \le N)\). Chỉ được gọi từ \(\texttt{notifyFJ}\).Giao thức tương tác hoạt động như sau. Đầu tiên, \(\texttt{addRoad}\) sẽ được gọi \(N-1\) lần để thông báo cho chương trình của bạn về hệ thống đường sá. Sau đó, \(\texttt{buildFarms}\) sẽ được gọi; bạn phải xác định nơi Farmer John nên xây từng trang trại và gọi \(\texttt{setFarmLocation}\) tương ứng cho mọi trang trại. Cuối cùng, sẽ có \(Q\) lời gọi tới \(\texttt{notifyFJ}\); với mỗi lời gọi, bạn phải gọi \(\texttt{addBox}\) một hoặc hai lần để thông báo cho Farmer John.
Đảm bảo rằng luôn có một cách hợp lệ để thông báo cho Farmer John bằng một hoặc hai hình chữ nhật. Giới hạn bộ nhớ cho bài này được đặt là 512 MB, cao hơn giới hạn thông thường 256 MB.
Với lời giải C++, hãy sử dụng mẫu sau:
#include "grader.h"
void addRoad(int a, int b){
// Fill in code here
}
void buildFarms(){
// Fill in code here
}
void notifyFJ(int a, int b){
// Fill in code here
}
Với lời giải Java, hãy sử dụng mẫu sau:
import java.io.IOException;
// If you find it necessary, you may import other standard libraries here.
public class boxes extends Grader {
// Copy this exactly:
@Override
public static void main(String args[]) throws IOException { new boxes().run(); }
@Override
public void addRoad(int a, int b) {
// Fill in code here
}
@Override
public void buildFarms(){
// Fill in code here
}
@Override
public void notifyFJ(int a, int b){
// Fill in code here
}
}
Trình chấm gọi \(\texttt{addRoad(0,1)}\).
Trình chấm gọi \(\texttt{addRoad(1,2)}\).
Trình chấm gọi \(\texttt{buildFarms()}\).
Lời giải gọi \(\texttt{setFarmLocation(0,1,1)}\).
Lời giải gọi \(\texttt{setFarmLocation(1,1,2)}\).
Lời giải gọi \(\texttt{setFarmLocation(2,2,2)}\).
Lời giải kết thúc \(\texttt{buildFarms()}\).
Trình chấm gọi \(\texttt{notifyFJ(0,0)}\).
Lời giải gọi \(\texttt{addBox(1,1,1,1)}\).
Lời giải kết thúc \(\texttt{notifyFJ(0,0)}\).
Trình chấm gọi \(\texttt{notifyFJ(0,2)}\).
Lời giải gọi \(\texttt{addBox(1,1,1,2)}\).
Lời giải gọi \(\texttt{addBox(2,2,2,2)}\).
Lời giải kết thúc \(\texttt{notifyFJ(0,2)}\).
Trình chấm kết thúc và lời giải vượt qua trường hợp kiểm thử.
Lưu ý: nếu bạn không vượt qua trường hợp kiểm thử đầu tiên, trình chấm sẽ thông báo điều này như thường lệ. Tuy nhiên, lưu ý rằng phần tương tác mẫu ngắn ở trên không tương ứng với trường hợp kiểm thử đầu tiên hay bất kỳ trường hợp kiểm thử nào khác.
USACO 2019 US Open Contest, Platinum — Tree Boxes
Tác giả: Spencer Compton.
Bessie và những người bạn đã bị bắt và giam trong một khu phức hợp bí mật ở nơi cách xa trang trại, và Bessie phải lên kế hoạch trốn thoát cho cả nhóm! Khu phức hợp gồm \(NK\) phòng giam được bố trí thành một lưới hình chữ nhật \(N \times K\), với các cánh cổng nằm giữa những ô kề nhau theo chiều ngang và chiều dọc. Mỗi ô giam đúng một con bò.
Bessie đã xâm nhập được vào hệ thống và có thể mở khóa bất kỳ tập con nào của các cánh cổng, nhưng mỗi cánh cổng có một chi phí. Để những con bò trốn thoát, Bessie phải mở đủ số cổng để tất cả bò có thể tập trung trong một ô duy nhất (nhờ vậy chúng có đủ sức bò để đào đường hầm lên mặt đất!). Bessie muốn giảm thiểu tổng chi phí mở khóa.
Nhưng tình thế nghiêm trọng hơn bao giờ hết, và Bessie không thể hài lòng với chỉ một kế hoạch trốn thoát: cô cần các phương án dự phòng. Hãy giúp cô đếm số kế hoạch trốn thoát có chi phí nhỏ nhất; hai kế hoạch được coi là khác nhau nếu có một cánh cổng cần được mở khóa trong kế hoạch này nhưng không cần được mở khóa trong kế hoạch kia.
Vì số lượng này có thể rất lớn, chỉ in ra số dư của nó khi chia cho \(10^9+7\).
Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách \(N\) và \(K\) (\(2 \le N \le 30000, 2 \le K \le 6\)).
Mỗi dòng trong \(N\) dòng tiếp theo chứa \(K-1\) số nguyên cách nhau bởi dấu cách: chi phí mở khóa từng cánh cổng trên một cạnh nằm ngang.
Mỗi dòng trong \(K\) dòng tiếp theo chứa \(N-1\) số nguyên cách nhau bởi dấu cách: chi phí mở khóa từng cánh cổng trên một cạnh thẳng đứng.
Mọi chi phí đều nằm trong khoảng từ \(1\) đến \(10^9\), kể cả hai đầu mút.
In ra một số nguyên duy nhất: số kế hoạch trốn thoát có chi phí nhỏ nhất, lấy modulo \(10^{9} + 7\).
Ví dụ 1
4 3
1 1
5 6
7 8
1 1
1 1 1
2 3 4
1 1 110Trường hợp kiểm thử mô tả một lưới \(4 \times 3\):
1 1
+-----+-----+
| | |
1 | |2 | 1
| 5 | 6 |
+-----+-----+
| | |
1 | |3 | 1
| 7 | 8 |
+-----+-----+
| | |
1 | |4 | 1
| | |
+-----+-----+
1 1
Mọi kế hoạch trốn thoát có chi phí nhỏ nhất đều sử dụng cánh cửa có chi phí 2, cánh cửa có chi phí 3 và chín trong số các cánh cửa có chi phí 1. Có mười cách chọn cạnh có chi phí 1 không được sử dụng, nên đáp án là 10.
USACO 2019 US Open Contest, Platinum — Compound Escape
Tác giả: Brian Dean.
Bessie thích ngắm cảnh, và hôm nay cô đang tìm kiếm những thung lũng đẹp.
Ta xét một lưới ô vuông \(N \times N\), trong đó mỗi ô có một độ cao. Mọi ô nằm ngoài lưới vuông này có thể được coi là có độ cao vô hạn.
Một thung lũng là một vùng của lưới liên thông, không có lỗ và có tính chất mọi ô kề ngay xung quanh nó đều cao hơn tất cả các ô trong vùng.
Cụ thể hơn:
Mục tiêu của Bessie là xác định tổng kích thước của tất cả các thung lũng.
Đây là một vùng:
oo.
ooo
..o
Đây không phải là một vùng (ô ở giữa và ô ở góc dưới bên phải không liên thông theo cạnh):
oo.
oo.
..o
Đây là một vùng không có lỗ:
ooo
o..
o..
Đây là một vùng có lỗ (ô duy nhất nằm bên trong hình "bánh vòng" không liên thông theo điểm với phần "bên ngoài" của vùng):
ooo
o.o
ooo
Đây là một vùng không có lỗ khác (ô duy nhất ở chính giữa liên thông theo điểm với ô ở góc dưới bên phải):
ooo
o.o
oo.
Dòng đầu tiên chứa số nguyên \(N\), với \(1 \le N \le 750\).
Mỗi dòng trong \(N\) dòng tiếp theo chứa \(N\) số nguyên là độ cao của các ô trong lưới. Mỗi độ cao \(h\) thỏa mãn \(1 \le h \le 10^6\). Mọi độ cao đều là các số nguyên phân biệt.
In ra một số nguyên duy nhất là tổng kích thước của tất cả các thung lũng.
Ví dụ 1
3
1 10 2
20 100 30
3 11 5030Trong ví dụ này, có ba thung lũng kích thước 1:
o.o
...
o..
Một thung lũng kích thước 2:
...
...
oo.
Một thung lũng kích thước 3:
ooo
...
...
Một thung lũng kích thước 6:
ooo
o..
oo.
Một thung lũng kích thước 7:
ooo
o.o
oo.
Và một thung lũng kích thước 9:
ooo
ooo
ooo
Do đó, đáp án là \(1 + 1 + 1 + 2 + 3 + 6 + 7 + 9 = 30\).
USACO 2019 US Open Contest, Platinum — Valleys
Tác giả: Travis Hance.