USACO 2020 - Tháng 2 - Hạng Bạch Kim

Trang trại của Farmer John gồm \(N\) đồng cỏ (\(2\leq N\leq 10^5\)) được nối bởi \(N-1\) con đường sao cho có thể đi từ bất kỳ đồng cỏ nào đến bất kỳ đồng cỏ nào khác. Nói cách khác, trang trại là một cây. Nhưng sau 28 năm xử lý những bài toán thuật toán hóc búa chắc chắn nảy sinh từ cây, FJ đã quyết định rằng một trang trại có dạng cây đơn giản là quá phức tạp. Ông tin rằng các bài toán thuật toán sẽ đơn giản hơn trên các đường đi.

Vì vậy, kế hoạch của ông là phân hoạch tập hợp các con đường thành nhiều đường đi và giao trách nhiệm về những đường đi này cho các người làm công xứng đáng. Ông không quan tâm đến số lượng đường đi. Tuy nhiên, ông muốn bảo đảm rằng tất cả các đường đi đều dài nhất có thể, để không người làm công nào có thể dùng những thuật toán kém hiệu quả về mặt tiệm cận mà vẫn thoát tội!

Hãy giúp Farmer John xác định số nguyên dương \(K\) lớn nhất sao cho có thể phân hoạch các con đường thành những đường đi có độ dài ít nhất \(K\).

Phân nhóm

• Trong các test 2-4, cây có dạng hình sao; nhiều nhất một đỉnh có bậc lớn hơn hai.
• Các test 5-8 thỏa mãn \(N\le 10^3\).
• Các test 9-15 không có ràng buộc bổ sung.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\).

Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\) cách nhau bởi dấu cách, mô tả một cạnh nối đỉnh \(a\) với đỉnh \(b\). Cả \(a\) và \(b\) đều thuộc đoạn \(1\ldots N\).

Dữ liệu ra

In \(K\).

Ví dụ

8
1 2
1 3
1 4
4 5
1 6
6 7
7 8

3

Nguồn

USACO 2020 February Contest, Platinum - Delegation: https://usaco.org/index.php?page=viewproblem2&cpid=1020

Tác giả: Mark Gordon và Dhruv Rohatgi.

Đồng cỏ của Farmer John có thể được biểu diễn bằng một lưới ô vuông \(N\times N\) (\(1\le N\le 300\)), gồm các vị trí \((i,j)\) với mọi \(1\le i,j\le N\). Với mỗi ô vuông của lưới, ký tự tương ứng trong dữ liệu vào là * nếu có đúng một con bò tại vị trí đó, và là . nếu không có con bò nào tại đó.

FJ tin rằng vẻ đẹp của đồng cỏ tỉ lệ thuận với số bộ ba con bò có vị trí cách đều nhau. Nói cách khác, chúng tạo thành một tam giác đều. Không may, chỉ mới gần đây FJ nhận ra rằng vì tất cả bò của ông đều nằm tại các tọa độ nguyên, không thể tồn tại bất kỳ bộ ba đẹp nào nếu sử dụng khoảng cách Euclid! Do đó, FJ quyết định chuyển sang sử dụng khoảng cách "Manhattan". Một cách chính thức, khoảng cách Manhattan giữa hai vị trí \((x_0,y_0)\) và \((x_1,y_1)\) bằng \(|x_0-x_1|+|y_0-y_1|\).

Cho lưới biểu diễn vị trí của các con bò, hãy tính số bộ ba cách đều.

Phân nhóm

Ngoài ví dụ, có mười bốn test, mỗi test ứng với một giá trị trong dãy

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\).

Với mỗi \(1\le i\le N\), dòng thứ \(i+1\) của dữ liệu vào chứa một xâu độ dài \(N\) chỉ gồm các ký tự * và .. Ký tự thứ \(j\) cho biết có một con bò tại vị trí \((i,j)\) hay không.

Dữ liệu ra

In một số nguyên duy nhất là đáp án. Có thể chứng minh rằng đáp án nằm trong phạm vi của số nguyên 32 bit có dấu.

Ví dụ

3
*..
.*.
*..

1

Nguồn

USACO 2020 February Contest, Platinum - Equilateral Triangles: https://usaco.org/index.php?page=viewproblem2&cpid=1021

Tác giả: Benjamin Qi.

Bessie được cho \(N\) đoạn thẳng (\(1\le N\le 10^5\)) trên một trục số một chiều. Đoạn thẳng thứ \(i\) chứa mọi số thực \(x\) thỏa mãn \(l_i\le x\le r_i\).

Định nghĩa hợp của một tập các đoạn thẳng là tập hợp mọi \(x\) nằm trong ít nhất một đoạn thẳng. Định nghĩa độ phức tạp của một tập các đoạn thẳng là lũy thừa bậc \(K\) của số miền liên thông được biểu diễn trong hợp của chúng (\(2\le K\le 10\)).

Bessie muốn tính tổng độ phức tạp trên tất cả \(2^N\) tập con của tập \(N\) đoạn thẳng đã cho, lấy phần dư theo \(10^9+7\).

Thông thường, nhiệm vụ của bạn là giúp Bessie. Nhưng lần này, bạn chính là Bessie và không có ai giúp bạn. Hãy tự giúp mình!

Phân nhóm

• Test 2 thỏa mãn \(N\le 16\).
• Các test 3-5 thỏa mãn \(N\le 1000\), \(K=2\).
• Các test 6-8 thỏa mãn \(N\le 1000\).
• Với mỗi \(T\in[9,16]\), test \(T\) thỏa mãn \(K=3+(T-9)\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(l_i\) và \(r_i\). Dữ liệu bảo đảm \(l_i<r_i\) và tất cả các giá trị \(l_i,r_i\) là những số nguyên đôi một phân biệt thuộc đoạn \(1\ldots 2N\).

Dữ liệu ra

In đáp án lấy phần dư theo \(10^9+7\).

Ví dụ

3 2
1 6
2 3
4 5

10

Nguồn

USACO 2020 February Contest, Platinum - Help Yourself: https://usaco.org/index.php?page=viewproblem2&cpid=1022

Tác giả: Benjamin Qi.