Contest ôn thi HSG 9-10 (số 3)

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Giai thừa 4 (p) 1.0s 256M
2 Đốt rơm 3 (p) 1.0s 512M
3 Nhà giả kim 3 (p) 3.0s 1G

1. Giai thừa

Điểm: 4 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: FACT.INP Output: FACT.OUT

Cho số tự nhiên \(n\), tính và in ra số lượng chữ số 0 tận cùng của \(n!\). Biết rằng, \(n!\) là ký hiệu cho giai thừa của \(n\), được định nghĩa là tích của các số tự nhiên từ \(1\) tới \(n\).

Input

  • Dòng duy nhất chứa số \(n\) (\(1 \le n \le 10^{18}\)).

Output

  • Dòng duy nhất chứa kết quả bài toán.

Example

Test 1

Input 
5
Output 
1
Note

\(n! = 5! = 120\) có một chữ số 0 tận cùng.

Ràng buộc

  • Subtask 1 (\(40\%\) số điểm): \(n \le 20\);
  • Subtask 2 (\(30\%\) số điểm): \(n \le 10^6\);
  • Subtask 3 (\(30\%\) số điểm): không có ràng buộc gì thêm.

2. Đốt rơm

Điểm: 3 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: FIRE.INP Output: FIRE.OUT

Small là một người đam mê khoa học, đặc biệt vật lý và các hiện tượng tự nhiên. Hôm nay, anh ấy thực hiện thí nghiệm nhằm đo tốc độ cháy của rơm khi được xếp thành những cấu hình khác nhau.

Small xếp các bó rơm thành \(n\) chồng liên tiếp nhau trên một mặt bằng, đánh số từ trái sang phải là \(1, 2, \dots, n\). Chồng rơm thứ \(i\) gồm có \(h_i\) bó rơm xếp chồng lên nhau.

Để bắt đầu thí nghiệm, Small châm lửa cùng lúc vào tất cả các bó rơm nằm ở lớp ngoài cùng. Cụ thể là những bó rơm mà bên trái, bên phải, hoặc bên trên nó không có rơm (tức là những phần tiếp xúc trực tiếp với không khí).

Toàn bộ chồng rơm sẽ cháy dần như sau:

  • Mỗi bó rơm mất đúng \(1\) phút để cháy hết hoàn toàn.
  • Ngay khi một bó rơm cháy xong hết, lửa sẽ lan sang tất cả các bó rơm nằm kề sát nó (ngay bên trái, bên phải, bên trên, và bên dưới). Lập tức, các bó rơm bên cạnh này sẽ bắt lửa và bắt đầu cháy.

Yêu cầu: Hãy giúp Small tính thời điểm mà toàn bộ \(n\) chồng rơm này cháy hết.

Input

Vào từ file văn bản FIRE.INP:

  • Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)).
  • Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2, \ldots, h_n\) (\(0 \le h_i \le 10^9\)).

Output

Ghi ra file văn bản FIRE.OUT:

  • Một số nguyên là thời điểm cháy hết của \(n\) chồng rơm (tính theo phút).

Example

Test 1

Input 
5
2 3 4 2 3
Output 
3
Note

Độ cao chồng rơm suốt quá trình đốt cháy:

  • Phút 0 (châm lửa): Các phần tiếp xúc không khí bắt đầu cháy \([2,3,4,2,3]\).
  • Phút 1: Lửa lan vào trong \([0,2,2,1,0]\).
  • Phút 2: Lửa tiếp tục lan \([0,0,1,0,0]\).
  • Phút 3: Bó rơm cuối cùng cháy hết \([0,0,0,0,0]\).

Test 2

Input 
1
0
Output 
0
Note

Không có bất kỳ bó rơm nào ngay từ đầu.

Scoring

  • Subtask 1 (\(50\%\) số điểm): \(n, h_i \le 200\).
  • Subtask 2 (\(20\%\) số điểm): \(n \le 2000\).
  • Subtask 3 (\(30\%\) số điểm): không có ràng buộc gì thêm.

3. Nhà giả kim

Điểm: 3 (p) Thời gian: 3.0s Bộ nhớ: 1G Input: ALCHEMY.INP Output: ALCHEMY.OUT

“Ta là một nhà giả kim huyền thoại. Chắc chắn ta sẽ tạo ra được thuốc thần Elixir giúp trường sinh bất lão trong truyền thuyết. Khà khà khà!!” – Canuc80k lẩm bẩm khi vừa mở tựa game Clash of Clans lên, vừa thu hoạch đầy bình dầu tím. Tuy nhiên, trên hành trình tạo ra Elixir, Canuc80k đã gặp phải vấn đề sau: trong cửa tiệm giả kim đang bày bán sẵn \(M\) loại nguyên liệu, mỗi loại có chỉ số năng lượng là \(A[i]\). Chỉ số năng lượng của tất cả nguyên liệu là đôi một khác nhau. Do ngân sách có hạn, Canuc80k chỉ được phép mua đúng \(N\) nguyên liệu bất kỳ trong số đó.

Việc pha chế khá phức tạp. Để tạo ra Elixir, Canuc80k cần \(K\) đơn vị Tinh dầu. Để tạo ra một đơn vị Tinh dầu, Canuc80k phải trộn hai nguyên liệu lại với nhau. Giả sử anh ấy trộn hai nguyên liệu có chỉ số năng lượng là \(X\) và \(Y\), quá trình phản ứng sẽ:

  • Tạo ra một đơn vị Tinh dầu.
  • Đồng thời, phản ứng sinh ra một nguyên liệu mới (phần cặn) có chỉ số năng lượng là \(\text{gcd}(X, Y)\) (Ký hiệu \(\text{gcd}(X, Y)\) là ước chung lớn nhất của \(X\) và \(Y\)). Nguyên liệu mới sinh ra này hoàn toàn có thể được dùng tiếp cho những lần pha chế sau đó.
  • Hai nguyên liệu gốc ban đầu (\(X\) và \(Y\)) sẽ biến mất sau phản ứng.

Mục tiêu của Canuc80k là tạo ra đủ \(K\) đơn vị Tinh dầu. Đồng thời, anh ấy muốn sau khi hoàn thành công việc, tổng chỉ số năng lượng của tất cả các nguyên liệu còn lại đạt giá trị lớn nhất.

Yêu cầu: Hãy giúp Canuc80k chọn mua \(N\) nguyên liệu ban đầu và đưa ra phương án pha chế sao cho tổng năng lượng của các nguyên liệu còn sót lại là tối đa.

Input

  • Dòng đầu tiên chứa ba số nguyên \(M, N, K\) (\(1 \le K < N \le M \le 5 \cdot 10^6\)) — lần lượt là số lượng nguyên liệu có trong tiệm, số lượng nguyên liệu Canuc80k được mua, và số đơn vị Tinh dầu anh ấy cần tạo ra.
  • Dòng tiếp theo chứa \(M\) số nguyên \(A[1], A[2], \dots, A[M]\) (\(1 \le A[i] \le 5 \cdot 10^6\)). Đây là chỉ số năng lượng của các nguyên liệu trong tiệm. Dữ liệu đảm bảo tất cả các số này là phân biệt.

Output

  • In ra một số nguyên duy nhất là tổng lớn nhất có thể của các nguyên liệu còn lại sau khi đã tạo đủ \(K\) đơn vị Tinh dầu.

Example

Test 1

Input 
8 6 2
14 13 12 11 2 4 8 9
Output 
42
Note

Canuc80k chọn mua các nguyên liệu: \(14, 13, 12, 11, 4, 8\). Sau đó:

  1. Trộn \(12\) và \(8\) \(\to\) tạo ra nguyên liệu mới \(\text{gcd}(12, 8) = 4\). Còn lại: \(14, 13, 4, 11, 4\).
  2. Trộn \(4\) (vừa tạo ra) và \(4\) (có sẵn) \(\to\) tạo ra nguyên liệu mới \(\text{gcd}(4, 4) = 4\). Còn lại: \(14, 13, 11, 4\). Tổng năng lượng là \(14 + 11 + 13 + 4 = 42\).

Scoring

  • Subtask \(1\) (\(10\%\) số điểm): \(M \le 5\).
  • Subtask \(2\) (\(15\%\) số điểm): \(M \le 20\).
  • Subtask \(3\) (\(35\%\) số điểm): \(M, A[i] \le 10^5\) và \(M = N\).
  • Subtask \(4\) (\(20\%\) số điểm): \(M, A[i] \le 10^5\).
  • Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.