BOI 2006 - Ngày 2

Một trạm không gian sẽ sử dụng \(N\) người. Thành phố dành cho họ được xây trên các lô đất vuông quanh trạm. Trạm nằm tại \((0,0)\); mỗi lô khác có tọa độ nguyên \((x,y)\). Trên mỗi lô có thể xây một tòa nhà không quá \(K\) tầng, mỗi tầng có đúng một căn hộ, và mỗi người sống trong một căn hộ riêng.

Do giao thông chỉ đi trên các đường giữa các lô, khoảng cách từ lô \((x,y)\) đến trạm là

Chi phí xây một tòa nhà bằng tổng chi phí xây từng tầng. Chi phí tầng chỉ phụ thuộc vào độ cao của tầng, không phụ thuộc vị trí. Trong \(30\) năm sử dụng, chi phí đưa một người đi lại giữa nhà và trạm là \(T\cdot d\), với \(d\) là khoảng cách từ tòa nhà đến trạm.

Hãy tìm tổng chi phí nhỏ nhất để xây đủ nhà ở và vận hành giao thông trong \(30\) năm.

Dữ liệu vào

Dòng đầu chứa \(N,T,K\). Mỗi dòng thứ \(i\) trong \(K\) dòng tiếp theo chứa \(c_i\), chi phí xây căn hộ ở tầng \(i\) khi các tầng thấp hơn đã được xây.

Dữ liệu ra

In một số nguyên: tổng chi phí nhỏ nhất.

Ràng buộc

• \(1\le N\le 10^{12}\).
• \(1\le T\le 500\,000\).
• \(1\le K\le 20\,000\).
• \(1\le c_i\le 2\,000\,000\,000\).
• \(c_1<c_2<\cdots<c_K\).
• Đáp án không vượt quá \(8\cdot 10^{18}\).

Ví dụ

17 5 4
100
107
114
121

1778

RLE là một phương pháp nén các dãy có nhiều ký tự giống nhau liên tiếp. Bảng chữ cái gồm \(n\) ký tự, biểu diễn bởi các số trong

Mã của một dãy cũng là một dãy ký tự thuộc \(\Sigma\). Tại mọi thời điểm có một ký tự đánh dấu lặp \(e\); ban đầu \(e=0\), nhưng ký tự này có thể thay đổi trong quá trình giải mã.

• Mọi ký tự \(a\ne e\) trong mã biểu diễn chính nó.
• Nếu gặp \(e\), hai ký tự \(b,k\) tiếp theo được hiểu như sau:
  • nếu \(b=e\), bộ ba \(e,e,k\) biểu diễn \(k+1\) lần ký tự \(e\);
  • nếu \(b\ne e\) và \(k=0\), từ thời điểm đó ký tự đánh dấu lặp đổi thành \(b\); bộ ba này không sinh ký tự nào;
  • nếu \(b\ne e\) và \(k>0\), bộ ba \(e,b,k\) biểu diễn \(k+3\) lần ký tự \(b\).

Một dãy có thể có nhiều mã với độ dài khác nhau. Cho một mã hợp lệ, hãy tìm một mã ngắn nhất biểu diễn cùng dãy đã giải mã.

Dữ liệu vào

Dòng đầu chứa \(n\). Dòng thứ hai chứa \(m\), độ dài mã đã cho. Dòng cuối chứa \(m\) số nguyên thuộc \(\Sigma\).

Dữ liệu ra

Dòng đầu chứa \(m'\), độ dài nhỏ nhất của một mã biểu diễn cùng dãy. Dòng cuối chứa \(m'\) số nguyên của một mã ngắn nhất. Nếu có nhiều đáp án, có thể in bất kỳ đáp án nào.

Ràng buộc

• \(2\le n\le 100\,000\).
• \(1\le m\le 2\,000\,000\).

Ví dụ

4
20
1 0 0 1 0 2 3 0 3 2 0 1 0 0 3 0 2 1 0 1

19
1 0 1 0 0 0 1 2 3 1 3 2 0 3 0 2 1 0 1

14
15
10 10 10 0 10 0 10 10 13 10 10 13 10 10 13

9
0 10 13 0 10 13 0 10 10

Một bảng trò chơi \(n\times n\) chứa một số nguyên không âm trong mỗi ô. Bạn bắt đầu ở góc trên bên trái và cần đến góc dưới bên phải. Số trong ô hiện tại là độ dài bắt buộc của bước nhảy tiếp theo. Mỗi bước chỉ được đi sang phải hoặc đi xuống và không được ra ngoài bảng. Ô chứa \(0\) là ngõ cụt.

Hãy tính số đường đi hợp lệ từ góc trên bên trái đến góc dưới bên phải.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\). Mỗi dòng trong \(n\) dòng tiếp theo chứa \(n\) số nguyên mô tả bảng.

Dữ liệu ra

In một số nguyên: số đường đi hợp lệ.

Ràng buộc

• \(4\le n\le 100\).
• Mỗi ô chứa một số nguyên từ \(0\) đến \(9\).
• Đáp án có không quá \(100\) chữ số thập phân.

Phân nhóm

• Có thể đạt \(70\%\) số điểm nếu dùng kiểu số nguyên \(64\) bit.
• Để đạt toàn bộ số điểm, cần xử lý số nguyên lớn.

Ví dụ

4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

3