| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - Promotion Counting | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Building a Tall Barn | 100 (p) | 4.0s | 512M |
| 3 | USACO 2017 - Subsequence Reversal | 100 (p) | 4.0s | 512M |
Đàn bò lại một lần nữa thử thành lập công ty khởi nghiệp, vì chúng quên mất kinh nghiệm trong quá khứ rằng bò là những nhà quản lý tồi tệ!
Đàn bò, được đánh số thuận tiện từ \(1 \ldots N\) (\(1 \leq N \leq 100\,000\)), tổ chức công ty theo cấu trúc cây, với bò \(1\) là chủ tịch (gốc của cây). Mỗi con bò trừ chủ tịch có đúng một người quản lý ("nút cha" của nó trên cây). Mỗi bò \(i\) có một chỉ số năng lực phân biệt \(p(i)\), mô tả mức độ thành thạo công việc của nó. Nếu bò \(i\) là tổ tiên (chẳng hạn người quản lý của người quản lý của người quản lý) của bò \(j\), ta gọi \(j\) là cấp dưới của \(i\).
Đáng tiếc, đàn bò nhận thấy một người quản lý thường có năng lực thấp hơn một số cấp dưới của mình; khi đó, người quản lý nên cân nhắc đề bạt một vài cấp dưới. Nhiệm vụ của bạn là giúp đàn bò xác định khi nào điều này xảy ra. Với mỗi bò \(i\) trong công ty, hãy đếm số cấp dưới \(j\) thỏa mãn \(p(j)>p(i)\).
Dòng đầu tiên chứa \(N\).
\(N\) dòng tiếp theo chứa các chỉ số năng lực \(p(1) \ldots p(N)\) của đàn bò. Mỗi chỉ số là một số nguyên phân biệt trong khoảng \(1 \ldots 1\,000\,000\,000\).
\(N-1\) dòng tiếp theo mô tả người quản lý (nút cha) của các con bò \(2 \ldots N\). Nhớ rằng bò \(1\) không có người quản lý vì nó là chủ tịch.
In \(N\) dòng. Dòng thứ \(i\) cho biết số cấp dưới của bò \(i\) có năng lực cao hơn bò \(i\).
Ví dụ 1
5
804289384
846930887
681692778
714636916
957747794
1
1
2
32
0
1
0
0USACO 2017 January Contest, Platinum — Promotion Counting. Tác giả đề: Karthik Nair.
Farmer John đang xây một chuồng bò hoàn toàn mới gồm \(N\) tầng với sự giúp đỡ của \(K\) con bò (\(1 \leq N \leq K \leq 10^{12}\) và \(N \leq 10^5\)). Để xây xong nhanh nhất có thể, ông cần bạn giúp phân bổ công việc cho đàn bò.
Mỗi con bò phải được phân công làm việc ở đúng một tầng cụ thể trong tổng số \(N\) tầng của chuồng, và mỗi tầng phải có ít nhất một con bò được phân công. Tầng thứ \(i\) cần tổng cộng \(a_i\) đơn vị công việc, và mỗi con bò hoàn thành một đơn vị công việc mỗi giờ; do đó, nếu có \(c\) con bò làm việc ở tầng \(i\), tầng này sẽ hoàn thành sau \(a_i/c\) đơn vị thời gian. Vì lý do an toàn, tầng \(i\) phải được hoàn thành trước khi có thể bắt đầu xây tầng \(i+1\).
Hãy tính tổng thời gian nhỏ nhất để hoàn thành chuồng khi đàn bò được phân bổ giữa các tầng một cách tối ưu. In số này sau khi làm tròn đến số nguyên gần nhất; đảm bảo rằng nghiệm cách ranh giới làm tròn giữa hai số nguyên hơn \(0.1\).
Dòng đầu tiên chứa \(N\) và \(K\).
\(N\) dòng tiếp theo chứa \(a_1 \ldots a_N\), mỗi giá trị là một số nguyên dương không quá \(10^{12}\).
In thời gian nhỏ nhất cần để xây xong chuồng, được làm tròn đến số nguyên gần nhất.
Ví dụ 1
2 5
10
45USACO 2017 January Contest, Platinum — Building a Tall Barn. Tác giả đề: Yang Liu.
Farmer John đang xếp \(N\) con bò thành một hàng để chụp ảnh (\(1 \leq N \leq 50\)). Chiều cao của con bò thứ \(i\) trong hàng là \(a(i)\), và Farmer John cho rằng bức ảnh sẽ đẹp mắt nếu hàng bò có một dãy con tăng dài xét theo chiều cao.
Nhắc lại, một dãy con là một tập \(a(i_1), a(i_2), \ldots, a(i_k)\) gồm các phần tử trong dãy bò, được chọn tại một dãy chỉ số \(i_1<i_2<\ldots<i_k\). Ta gọi dãy con là tăng nếu \(a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)\).
Farmer John muốn thứ tự đàn bò của mình chứa một dãy con tăng dài. Để đạt được điều này, ban đầu ông cho phép mình chọn một dãy con bất kỳ và đảo ngược thứ tự các phần tử của nó.
Chẳng hạn, giả sử ta có dãy:
1 6 2 3 4 3 5 3 4
Ta có thể đảo ngược các phần tử được chọn:
1 6 2 3 4 3 5 3 4
^ ^ ^ ^
để thu được:
1 4 2 3 4 3 3 5 6
^ ^ ^ ^
Hãy chú ý rằng dãy con sau khi bị đảo vẫn sử dụng đúng các chỉ số mà nó chiếm giữ ban đầu, còn những phần tử khác không thay đổi.
Hãy tìm độ dài lớn nhất có thể của một dãy con tăng, khi bạn được chọn một dãy con bất kỳ và đảo ngược nó một lần.
Dòng đầu tiên chứa \(N\). \(N\) dòng còn lại chứa \(a(1) \ldots a(N)\), mỗi giá trị là một số nguyên trong khoảng \(1 \ldots 50\).
In số phần tử lớn nhất có thể tạo thành một dãy con tăng dài nhất sau khi đảo ngược các phần tử của nhiều nhất một dãy con.
Ví dụ 1
9
1
2
3
9
5
6
8
7
49USACO 2017 January Contest, Platinum — Subsequence Reversal. Tác giả đề: Lewin Gan.