Tham lam #1

Rùa có một cái xô nước đang chứa \(L\) lít nước. Rùa muốn lấy cái xô làm việc khác nên Rùa muốn chuyển lượng nước sang những chiếc gàu nước.
Biết rằng, nhà Rùa có vô tận những chiếc gàu thuộc 2 loại, loại chứa được \(5\) lít và loại chứa được \(2\) lít. Hỏi, tổng số gàu ít nhất Rùa cần sử dụng để đong ít nhất \(L\) lít nước là bao nhiêu?

Input

• Một dòng duy nhất chứa một số nguyên \(L\) \((1 \leq L \leq 10^{18})\)

Output

• In ra tổng số gàu ít nhất Rùa cần sử dụng

27

6

30

6

Bạn muốn mua \(N\) lít xăng, không thừa không thiếu. Tại một tiệm xăng nọ có hai phương thức mua xăng:

• 1L: Mua 1 lít với giá \(a\) đồng
• 2L: Mua 2 lít với giá \(b\) đồng

Cho ba số \(N\), \(a\), \(b\). Hãy tính chi phí ít nhất cần để mua đúng chính xác \(N\) lít xăng.

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) \((1 \leq N \leq 10^9)\)
• Dòng thứ hai chứa hai số nguyên dương lần lượt là \(a\) và \(b\) \((1 \leq a, b \leq 10^9)\)

Output

In ra một số nguyên, là số tiền tối thiểu cần để mua đúng chính xác \(N\) lít xăng tại tiệm xăng đó.

Example

5
1 1

3

7 
1 7

7

Rùa có rất nhiều thắc mắc trong đầu. Hôm nay Rùa đặc biệt thắc mắc đến câu hỏi số 99, với nội dung như sau:

Có một số nguyên dương \(N\), số nguyên dương nhỏ nhất có tổng các chữ số của nó bằng \(N\) là số mấy?

Input

Số nguyên dương \(N\) \((1 \leq N \leq 10^{6})\)

Output

Số nguyên dương nhỏ nhất mà có tổng các chữ của nó bằng \(N\).

Example

10

19

18

99

Bạn là một hacker chuyên nghiệp, hiện tại đã một cách thành công xâm nhập vào cơ sở dữ liệu nơi chứa điểm của bạn. Điểm của bạn là một danh sách gồm \(N\) số thực, có giá trị trong đoạn \([0.0, 10.0]\) và chỉ có một chữ số ở hàng thập phân.

Trong khả năng của mình, bạn có thể sửa một số trong \(N\) số đó mà không bị phát hiện. Hỏi, tổng điểm sau khi đã sửa cao nhất có thể là bao nhiêu?

Lưu ý, không thể sửa một điểm quá \(10.0\) hoặc thấp hơn \(0.0\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) \((1 \leq N \leq 10^5)\)
• Dòng thứ hai chứa \(N\) số thực cách nhau bởi 1 ký tự khoảng trống, có giá trị trong đoạn \([0.0, 10.0]\) và chỉ có một chữ số ở phần thập phân.

Output

• Gồm một dòng, trên đó có một số thực là tổng điểm cao nhất có thể sau khi sửa 1 con điểm.
• Đáp án sẽ được chấp nhận đúng nếu output của bạn và output của bộ test lệch nhau không quá \(0.0001\).

Example

3
10.0 10.0 8.0

30.0

1
10.0

10.0

Bạn được cho một số nguyên \(n\). Ở mỗi bước, bạn có thể trừ \(n\) đi một lượng bằng một trong các chữ số của nó.

Cần bao nhiêu bước để làm cho \(n\) bằng \(0\)?

Input

• Gồm một dòng duy nhất chứa số nguyên \(n\) \((1 \leq n \leq 10^6)\).

Output

• In ra một số nguyên duy nhất là số bước tối thiểu cần dùng.

Example

27

5

Cho số nguyên \(n\), hãy phân tích \(n\) thành tổng của \(k\) số nguyên tố sao cho \(k\) lớn nhất có thể.

Input

• Dòng đầu tiên là số nguyên \(n (2 \leq n \leq 10^5)\).

Output

• Dòng đầu in ra một số nguyên là \(k\).
• Dòng thứ hai in ra \(k\) số nguyên có tổng bằng \(n\) theo thứ tự tăng dần.

Example

5 

2
2 3

Bạn được cho một mảng gồm \(n\) số nguyên dương. Bạn cần biến đổi sao cho mảng này được sắp xếp theo trình tự tăng dần, và mọi phần tử trong mảng đều không nhỏ hơn phần tử đứng trước.

Trong mỗi lần biến đổi, bạn có thể tăng một phần tử lên một đơn vị. Hãy tìm số lần biến đổi ít nhất để thoả mản điều kiện trên.

Input

• Dòng đầu chỉ chứa số nguyên dương \(n\) là độ dài của mảng
• Dòng thứ hai gồm \(n\) số nguyên dương \(x_1, x_2, \ldots, x_n\), là các phần tử của mảng

Constraints

• \(1 \leq n \leq 2\cdot 10^5\)
• \(1 \leq x_i \leq 10^9\)

Output

• In ra số lần biến đổi ít nhất

Example

5
3 2 5 1 7

5

Cho \(n\) số nguyên dương \(e_1,e_2,...e_n\).

Yêu cầu: Tìm \(4\) số nguyên dương \(a,b,c,d\) (\(a,b,c,d\) khác nhau từng đôi một) từ dãy trên sao cho \((a - b) \times (c - d)\) đạt giá trị lớn nhất.

Input

• Dòng đầu ghi số nguyên dương \(n\) (\(n \leq 10^5\)).
• Dòng thứ hai ghi ra \(n\) số nguyên dương \(e_1,e_2,...e_n\) (\(1 \leq e_i \leq 10^9\)).

Output

• Ghi ra giá trị lớn nhất thỏa mãn yêu cầu đề bài.

Example

5
1 3 5 7 9

36

Nhân dịp Tết, ba bé Bo chuẩn bị \(n\) túi lì xì cho bé Bo. Trong túi thứ \(i\) có số tiền là \(a_i\) và một số nguyên \(b_i\) \((b_i ≥ 0)\). Nếu \(b_i > 0\) thì bé Bo được phép chọn thêm \(b_i\) túi lì xì khác. Việc chọn thêm này là tích lũy. Đầu tiên, bé Bo chọn một túi bất kỳ, sau đó giả sử bé Bo đang có tổng số tiền là \(A\) và số túi được phép chọn thêm là \(B\) \((B > 0)\), nếu bé Bo chọn thêm túi thứ \(i\) thì tổng số tiền là \(A + a_i\) và tổng số túi được chọn thêm là \(B -1 + b_i\). Cứ như vậy cho đến khi không được phép chọn thêm \((B=0)\) hoặc đã chọn hết \(n\) túi.

Yêu cầu: Bạn hãy giúp bé Bo xác định thứ tự chọn túi sao cho tổng số tiền bé có được là lớn nhất nhé.

Input

• Dòng đầu tiên là số nguyên \(n\) \((1 \leq n \leq 100)\).

• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) gồm \(2\) số nguyên \(a_i\) và \(b_i\) cách nhau một khoảng trắng \((1 \leq a_i \leq 100, 0 \leq b_i \leq 100)\).

Output

• Là số nguyên xác định số tiền nhiều nhất mà bé Bo có được.

Example

3
1 0
2 0
0 2 

3

5
0 0
2 0
2 0
3 0
5 1

8