| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2019 - Snakes | 100 (p) | 4.0s | 512M |
| 2 | USACO 2019 - I Would Walk 500 Miles | 100 (p) | 4.0s | 512M |
| 3 | USACO 2019 - Balancing Inversions | 100 (p) | 4.0s | 512M |
Theo truyền thuyết, Thánh Patrick đã xua đuổi tất cả rắn khỏi Mooland hơn một nghìn năm trước. Tuy nhiên, từ đó đến nay rắn đã quay trở lại Mooland! Ngày Thánh Patrick là ngày 17 tháng 3, vì vậy Bessie sẽ tưởng niệm Thánh Patrick bằng cách xua đuổi toàn bộ rắn khỏi Mooland một lần và mãi mãi.
Bessie được trang bị một chiếc lưới để bắt những con rắn phân bố thành \(N\) nhóm trên một đường thẳng (\(1 \leq N \leq 400\)). Bessie phải bắt mọi con rắn trong mọi nhóm theo thứ tự các nhóm xuất hiện trên đường thẳng. Mỗi lần bắt một nhóm, cô có thể cho những con rắn vào lồng và bắt đầu nhóm tiếp theo với chiếc lưới trống.
Một chiếc lưới có kích thước \(s\) nghĩa là Bessie có thể bắt bất kỳ nhóm nào chứa \(g\) con rắn, với \(g \leq s\). Tuy nhiên, mỗi khi Bessie bắt một nhóm gồm \(g\) con rắn bằng chiếc lưới kích thước \(s\), cô lãng phí \(s-g\) đơn vị không gian. Lưới của Bessie có thể bắt đầu với kích thước bất kỳ và cô có thể thay đổi kích thước lưới \(K\) lần (\(1 \leq K < N\)).
Hãy cho Bessie biết tổng lượng không gian lãng phí nhỏ nhất mà cô có thể tích lũy sau khi bắt hết tất cả các nhóm.
Dòng đầu tiên chứa \(N\) và \(K\). Dòng thứ hai chứa \(N\) số nguyên \(a_1,\dots,a_N\), trong đó \(a_i\) (\(0 \leq a_i \leq 10^6\)) là số rắn trong nhóm thứ \(i\).
In ra một số nguyên là lượng không gian lãng phí nhỏ nhất sau khi Bessie bắt hết tất cả rắn.
Ví dụ 1
6 2
7 9 8 2 3 23Lưới của Bessie bắt đầu với kích thước 7. Sau khi bắt nhóm rắn đầu tiên, cô đổi lưới sang kích thước 9 và giữ kích thước đó cho đến nhóm rắn thứ 4, khi cô đổi lưới sang kích thước 3. Tổng lượng không gian lãng phí là \((7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3\).
USACO 2019 US Open Contest, Gold — Snakes
Tác giả: Patrick Zhang.
Farmer John muốn chia \(N\) con bò của mình (\(N \leq 7500\)), được đánh số thuận tiện từ \(1 \ldots N\), thành \(K\) nhóm không rỗng (\(2 \leq K \leq N\)), sao cho bất kỳ hai con bò thuộc hai nhóm khác nhau muốn gặp nhau đều phải đi bộ một số dặm. Bò \(x\) và bò \(y\) (với \(1 \leq x < y \leq N\)) sẵn lòng đi bộ \((2019201913x + 2019201949y)\text{ mod } 2019201997\) dặm để gặp nhau.
Với một cách chia \(N\) con bò thành \(K\) nhóm không rỗng, gọi \(M\) là giá trị nhỏ nhất trong số quãng đường mà bất kỳ hai con bò thuộc hai nhóm khác nhau sẵn lòng đi để gặp nhau. Để kiểm tra sự tận tâm của những con bò dành cho nhau, Farmer John muốn chia tối ưu \(N\) con bò thành \(K\) nhóm sao cho \(M\) lớn nhất có thể.
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.
Dữ liệu vào chỉ gồm một dòng chứa \(N\) và \(K\), cách nhau bởi một dấu cách.
In ra \(M\) trong một phương án tối ưu.
Ví dụ 1
3 22019201769Trong ví dụ này, bò 1 và bò 2 sẵn lòng đi bộ 2019201817 dặm để gặp nhau. Bò 2 và bò 3 sẵn lòng đi bộ 2019201685 dặm. Còn bò 1 và bò 3 sẵn lòng đi bộ 2019201769 dặm. Vì vậy, bằng cách chia sao cho bò 1 ở một nhóm riêng, còn bò 2 và bò 3 ở cùng một nhóm, ta có \(M = \min(2019201817,2019201769) = 2019201769\) (đây là giá trị tốt nhất có thể đạt được trong trường hợp này).
USACO 2019 US Open Contest, Gold — I Would Walk 500 Miles
Tác giả: Brian Dean.
Bessie và Elsie đang chơi một trò chơi trên mảng Boolean \(A\) có độ dài \(2N\) (\(1 \leq N \leq 10^5\)). Điểm của Bessie là số nghịch thế trong nửa đầu của \(A\), còn điểm của Elsie là số nghịch thế trong nửa sau của \(A\). Một nghịch thế là một cặp phần tử \(A[i]=1\) và \(A[j]=0\) với \(i<j\). Ví dụ, một mảng gồm một đoạn toàn số 0 theo sau bởi một đoạn toàn số 1 không có nghịch thế nào, còn một mảng gồm một đoạn có \(X\) số 1 theo sau bởi một đoạn có \(Y\) số 0 thì có \(XY\) nghịch thế.
Farmer John tình cờ bắt gặp bàn chơi và tò mò muốn biết số lần đổi chỗ hai phần tử kề nhau ít nhất cần thực hiện để trò chơi trông như đã hòa. Hãy giúp Farmer John tìm câu trả lời cho câu hỏi này.
Dòng đầu tiên chứa \(N\), và dòng tiếp theo chứa \(2N\) số nguyên, mỗi số bằng 0 hoặc 1.
In ra số lần đổi chỗ hai phần tử kề nhau cần thiết để trò chơi hòa.
Ví dụ 1
5
0 0 0 1 0 1 0 0 0 11Trong ví dụ này, ban đầu nửa đầu của mảng có \(1\) nghịch thế, còn nửa sau có \(3\) nghịch thế. Sau khi đổi chỗ bit thứ \(5\) và bit thứ \(6\) cho nhau, cả hai mảng con đều có \(0\) nghịch thế.
USACO 2019 US Open Contest, Gold — Balancing Inversions
Tác giả: Dhruv Rohatgi.