2. Google Code Jam 2022 - Controlled Inflation
Hàng người chờ dùng máy bơm hơi tại trạm xăng của bạn ngày càng dài! Bạn muốn tối ưu quy trình để giúp khách hàng bơm lốp xe, bóng thể thao, các con vật bóng bay khổng lồ trong lễ diễu hành và những sản phẩm khác nhanh hơn.
Máy bơm hoạt động tự động: bạn đặt áp suất thành một số pascal cụ thể rồi nối máy vào sản phẩm cần bơm; máy sẽ bơm sản phẩm đến đúng áp suất đó. Máy chỉ có hai nút: tăng và giảm. Hai nút tương ứng tăng hoặc giảm áp suất mục tiêu đúng \(1\) pascal.
Có một hàng gồm \(\mathbf{N}\) khách hàng, mỗi người mang đúng \(\mathbf{P}\) sản phẩm cần bơm bằng máy. Bạn biết áp suất mục tiêu của từng sản phẩm. Bạn có thể bơm các sản phẩm của cùng một khách theo thứ tự tùy ý, nhưng không được thay đổi thứ tự khách hàng. Cụ thể, phải bơm xong mọi sản phẩm của khách thứ \(i\) trước khi bơm bất kỳ sản phẩm nào của khách thứ \(i+1\). Giữa hai sản phẩm có áp suất mục tiêu khác nhau, bạn phải dùng các nút trên máy để điều chỉnh.
Ban đầu máy bơm được đặt ở \(0\) pascal; sau khi đã bơm tất cả sản phẩm của mọi khách, máy có thể dừng ở bất kỳ giá trị nào. Nếu sắp thứ tự sản phẩm của từng khách một cách tối ưu, số lần nhấn nút ít nhất là bao nhiêu?
Dữ liệu vào
Dòng đầu chứa số lượng bộ test \(\mathbf{T}\). Tiếp theo là \(\mathbf{T}\) bộ test.
Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(\mathbf{N}\) và \(\mathbf{P}\): số khách hàng và số sản phẩm mà mỗi khách mang đến. Tiếp theo là \(\mathbf{N}\) dòng. Dòng thứ \(i\) chứa \(\mathbf{P}\) số nguyên \(\mathbf{X}_{i,1},\mathbf{X}_{i,2},\ldots,\mathbf{X}_{i,\mathbf{P}}\), trong đó \(\mathbf{X}_{i,j}\) là áp suất mục tiêu, tính bằng pascal, của sản phẩm thứ \(j\) mà khách thứ \(i\) mang đến.
Dữ liệu ra
Với mỗi bộ test, in một dòng theo định dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là số lần nhấn nút ít nhất để bơm mọi sản phẩm đúng áp suất yêu cầu.
Ràng buộc
- \(1\le\mathbf{T}\le100\).
- \(1\le\mathbf{X}_{i,j}\le10^9\) với mọi \(i,j\).
Phân nhóm
- Test Set 1 (phán quyết hiển thị): \(2\le\mathbf{N}\le10\) và \(2\le\mathbf{P}\le3\).
- Test Set 2 (phán quyết ẩn): \(2\le\mathbf{N}\le1000\) và \(2\le\mathbf{P}\le100\).
Điểm các phân nhóm
Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 14/35 | 40% |
| Test Set 2 | 21/35 | 60% |
Ví dụ
Ví dụ 1
Input
2
3 3
30 10 40
20 50 60
60 60 50
5 2
1 1000000000
500000000 1000000000
1 1000000000
500000000 1
1 1000000000Output
Case #1: 110
Case #2: 4999999996Giải thích
Trong bộ test mẫu số 1, một cách dùng máy bơm tối ưu là:
- Nhấn nút tăng \(10\) lần, đưa máy lên \(10\); bơm sản phẩm cần \(10\) pascal của khách thứ nhất.
- Nhấn tăng \(30\) lần, đưa máy lên \(40\); bơm sản phẩm cần \(40\) pascal của khách thứ nhất.
- Nhấn giảm \(10\) lần, đưa máy xuống \(30\); bơm sản phẩm cần \(30\) pascal của khách thứ nhất.
- Nhấn giảm \(10\) lần, đưa máy xuống \(20\); bơm sản phẩm cần \(20\) pascal của khách thứ hai.
- Nhấn tăng \(30\) lần, đưa máy lên \(50\); bơm sản phẩm cần \(50\) pascal của khách thứ hai.
- Nhấn tăng \(10\) lần, đưa máy lên \(60\); bơm sản phẩm cần \(60\) pascal của khách thứ hai và cả hai sản phẩm cần \(60\) pascal của khách thứ ba.
- Cuối cùng, nhấn giảm \(10\) lần, đưa máy xuống \(50\); bơm sản phẩm cần \(50\) pascal của khách thứ ba.
Tổng cộng có \(110\) lần nhấn nút.
Trong bộ test mẫu số 2, lưu ý rằng đáp án có thể lớn hơn \(2^{32}\).
Nguồn
Google Code Jam 2022, Vòng 1B, bài Controlled Inflation.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
