Google Code Jam 2019 - Pancake Pyramid
Xem PDFĐề bài
Bạn vừa nấu ăn xong cho một số thực khách tại Nhà Bánh kếp Vô hạn. Có tất cả \(S\) chồng bánh kếp và bạn đã xếp chúng thành một hàng, sao cho chồng thứ \(i\) tính từ bên trái (đánh số bắt đầu từ \(1\)) có \(P_i\) chiếc bánh.
Người giám sát của bạn chuẩn bị mang các chồng bánh ra cho khách thì chợt nhận ra rằng một bức ảnh chụp chúng có thể là quảng cáo hay. Tuy nhiên, cô ấy lo rằng có thể có quá nhiều chồng bánh, nên dự định bỏ đi \(L\) chồng ngoài cùng bên trái và \(R\) chồng ngoài cùng bên phải, trong đó \(L,R\) là các số nguyên không âm thỏa mãn \(L+R\le S-3\). (Lưu ý rằng sau khi bỏ đi, vẫn còn ít nhất \(3\) chồng bánh.)
Người giám sát cũng cho rằng các chồng còn lại sẽ trông đẹp mắt nếu chúng có tính chất kim tự tháp. Một dãy \(N\) chồng có chiều cao \(H_1,H_2,\ldots,H_N\) có tính chất kim tự tháp nếu tồn tại số nguyên \(j\) (\(1\le j\le N\)) sao cho
và
(Dãy này có thể trông không giống một “kim tự tháp” thông thường cho lắm — một nhóm các chồng có cùng kích thước vẫn có tính chất kim tự tháp, và một nhóm có chiều cao không giảm từ trái sang phải cũng vậy, cùng với nhiều ví dụ khác.)
Dãy còn lại sau khi người giám sát bỏ \(L\) chồng ngoài cùng bên trái và \(R\) chồng ngoài cùng bên phải có thể chưa có tính chất kim tự tháp... nhưng bạn có thể khắc phục bằng cách thêm bánh vào một hoặc nhiều chồng! Chi phí kim tự tháp hóa của một dãy là tổng số bánh ít nhất phải thêm vào các chồng để dãy có tính chất kim tự tháp.
Trong lúc người quản lý cân nhắc nên chọn \(L,R\) nào, bạn tự hỏi tổng chi phí kim tự tháp hóa trên mọi cách chọn \(L,R\) hợp lệ là bao nhiêu. Hãy tính tổng này theo modulo số nguyên tố \(10^9+7\) (\(1000000007\)).
Dữ liệu vào
Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng chứa số nguyên \(S\): số chồng bánh. Sau đó là một dòng chứa \(S\) số nguyên \(P_1,P_2,\ldots,P_S\). Số thứ \(i\) là số bánh ở chồng thứ \(i\) tính từ bên trái.
Dữ liệu ra
Với mỗi bộ test, in một dòng dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)), còn y là tổng chi phí kim tự tháp hóa trên mọi cách chọn \(L,R\) hợp lệ, theo modulo \(10^9+7\) (\(1000000007\)).
Ràng buộc
- \(1\le T\le100\).
- \(1\le P_i\le10^9\) với mọi \(i\).
Phân nhóm
Test Set 1 (Hiển thị)
- \(S=3000\) đối với tối đa \(20\) bộ test.
- \(3\le S\le500\) đối với tất cả bộ test còn lại.
Test Set 2 (Ẩn)
- \(S=10^6\) đối với tối đa \(1\) bộ test.
- \(S=10^5\) đối với tối đa \(3\) bộ test.
- \(3\le S\le10000\) đối với tất cả bộ test còn lại.
Đ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 | 5/22 | 22,73% |
| Test Set 2 | 17/22 | 77,27% |
Ví dụ
Ví dụ 1
Dữ liệu mẫu và phần giải thích chính thức được trình bày đầy đủ ngay bên dưới.
Giải thích
Input
3
3
2 1 2
5
1 6 2 5 7
4
1000000000 1 1 1000000000
Output
Case #1: 1
Case #2: 16
Case #3: 999999991
Trong Ví dụ #1, người giám sát buộc phải chọn \(L=0,R=0\), nên đó là trường hợp duy nhất cần xét. Tối ưu là thêm một chiếc bánh vào chồng giữa. Dù dãy thu được trông phẳng, nó có tính chất kim tự tháp; thực tế mọi chỉ số đều có thể làm \(j\).
Trong Ví dụ #2, sau đây là mọi cách chọn \(L,R\), dãy còn lại và việc cần làm:
- \(L=0,R=0\): \(H=[1,6,2,5,7]\). Thêm bốn bánh vào chồng thứ ba và một bánh vào chồng thứ tư. Ta được \([1,6,6,6,7]\), có tính chất kim tự tháp với \(j=5\).
- \(L=0,R=1\): \(H=[1,6,2,5]\). Thêm ba bánh vào chồng thứ ba. Ta được \([1,6,5,5]\), có tính chất kim tự tháp với \(j=2\).
- \(L=0,R=2\): \(H=[1,6,2]\). Dãy đã có tính chất kim tự tháp với \(j=2\).
- \(L=1,R=0\): \(H=[6,2,5,7]\). Thêm bốn bánh vào chồng thứ hai và một bánh vào chồng thứ ba. Ta được \([6,6,6,7]\), có tính chất kim tự tháp với \(j=4\).
- \(L=1,R=1\): \(H=[6,2,5]\). Thêm ba bánh vào chồng thứ hai. Ta được \([6,5,5]\), có tính chất kim tự tháp với \(j=1\).
- \(L=2,R=0\): \(H=[2,5,7]\). Dãy đã có tính chất kim tự tháp với \(j=3\).
Vì vậy, đáp án là \((5+3+0+5+3+0)\) modulo \((10^9+7)\), bằng \(16\).
Trong Ví dụ #3, ta chỉ cần thêm bánh để tạo tính chất kim tự tháp khi \(L=0,R=0\). Tối ưu là thêm \(999999999\) bánh vào mỗi chồng thứ hai và thứ ba. (Hy vọng các thực khách đang đói!) Vì vậy đáp án là \((999999999+999999999)\) modulo \((10^9+7)\), bằng \(999999991\).
Nguồn
Google Code Jam 2019, Vòng 3, bài Pancake Pyramid.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Kỳ thi:
- Google Code Jam 2019 - Round 3 (8 Tháng sáu, 2019)
Bình luận