| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2020 - Triangles | 100 (p) | 4.0s | 512M |
| 2 | USACO 2020 - Mad Scientist | 100 (p) | 4.0s | 512M |
| 3 | USACO 2020 - Swapity Swap | 100 (p) | 4.0s | 512M |
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 100\)) 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\).
Diện tích lớn nhất của một đồng cỏ mà Farmer John có thể tạo là bao nhiêu? Dữ liệu bảo đảm tồn tại ít nhất một đồng cỏ hình tam giác hợp lệ.
Tất cả các test tuân theo các ràng buộc đã nêu.
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 \(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ì diện tích không nhất thiết là số nguyên, hãy in hai lần diện tích lớn nhất của một tam giác hợp lệ được tạo bởi các cọc hàng rào.
Ví dụ 1
4
0 0
0 1
1 0
1 22Các cọc tại \((0,0)\), \((1,0)\) và \((1,2)\) tạo thành một tam giác có diện tích \(1\). Vì vậy, đáp án là \(2\cdot 1=2\). Chỉ có một tam giác khác, với diện tích \(0.5\).
USACO 2020 February Contest, Bronze - Triangles: https://usaco.org/index.php?page=viewproblem2&cpid=1011
Tác giả: Travis Hance.
Ben, anh họ của Farmer John, tình cờ lại là một nhà khoa học điên. Thông thường, điều này gây ra khá nhiều bất hòa trong những buổi họp mặt gia đình, nhưng đôi khi nó cũng có ích, đặc biệt là khi Farmer John phải đối mặt với những vấn đề độc đáo và khác thường liên quan đến đàn bò của mình.
Hiện tại, Farmer John đang gặp một vấn đề độc đáo và khác thường với đàn bò. Gần đây, ông đặt mua \(N\) con bò (\(1\leq N\leq 1000\)) thuộc hai giống khác nhau: Holstein và Guernsey. Trong đơn đặt hàng, ông mô tả đàn bò bằng một xâu gồm \(N\) ký tự, mỗi ký tự là H (đại diện cho Holstein) hoặc G (đại diện cho Guernsey). Không may, khi đàn bò đến trang trại và ông xếp chúng thành một hàng, thứ tự giống của chúng tạo thành một xâu khác với xâu ban đầu.
Gọi hai xâu này là \(A\) và \(B\), trong đó \(A\) là xâu các ký hiệu giống mà Farmer John mong muốn ban đầu, còn \(B\) là xâu ông thấy khi đàn bò đến. Thay vì chỉ kiểm tra xem việc sắp xếp lại các con bò trong \(B\) có đủ để thu được \(A\) hay không, Farmer John nhờ anh họ Ben dùng tài năng khoa học của mình để giúp ông giải quyết vấn đề.
Sau nhiều tháng làm việc, Ben chế tạo ra một cỗ máy phi thường mang tên máy-đảo-giống-nhiều-bò 3000, có thể chọn bất kỳ xâu con gồm các con bò liên tiếp nào và đảo giống của chúng: mọi H trong xâu con trở thành G, và mọi G trở thành H. Farmer John muốn tìm số lần ít nhất cần sử dụng cỗ máy để biến thứ tự hiện tại \(B\) thành thứ tự mong muốn ban đầu \(A\). Đáng tiếc, kỹ năng của nhà khoa học điên Ben chỉ dừng ở việc chế tạo những thiết bị tài tình, vì vậy bạn cần giúp Farmer John giải bài toán hóc búa này.
Tất cả các test tuân theo các ràng buộc đã nêu.
Dòng đầu tiên chứa \(N\), hai dòng tiếp theo lần lượt chứa các xâu \(A\) và \(B\). Mỗi xâu gồm \(N\) ký tự, mỗi ký tự là H hoặc G.
In số lần ít nhất cần sử dụng cỗ máy để biến \(B\) thành \(A\).
Ví dụ 1
7
GHHHGHH
HHGGGHH2Đầu tiên, FJ có thể đảo xâu con chỉ gồm ký tự đầu tiên, biến \(B\) thành GHGGGHH. Tiếp theo, ông có thể đảo xâu con gồm ký tự thứ ba và thứ tư để thu được \(A\). Tất nhiên, cũng có những cách kết hợp hai lần sử dụng cỗ máy khác cho kết quả đúng.
USACO 2020 February Contest, Bronze - Mad Scientist: https://usaco.org/index.php?page=viewproblem2&cpid=1012
Tác giả: Brian Dean.
\(N\) con bò của Farmer John (\(1\le N\le 100\)) đ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 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 hai 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\) và \(K\). Dòng thứ hai chứa \(A_1\) và \(A_2\), dòng thứ ba chứa \(B_1\) và \(B_2\).
Trên dòng thứ \(i\) của kết quả, in nhãn của con bò thứ \(i\) tính từ bên trái sau khi kết thúc bài tập.
Ví dụ 1
7 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, Bronze - Swapity Swap: https://usaco.org/index.php?page=viewproblem2&cpid=1013
Tác giả: Brian Dean.