ROBOT VẬN CHUYỂN PIN

Một nhà máy có ~3~ khối pin với dung lượng lần lượt là ~A~, ~B~ và ~C~.

Một robot được giao nhiệm vụ vận chuyển các khối pin đến phòng thí nghiệm. Robot có thể mang một hoặc hai khối pin trong một lần di chuyển.

Để bảo đảm an toàn, tổng dung lượng của các khối pin mà robot mang không được vượt quá ~K~.

Robot muốn lựa chọn các khối pin sao cho tổng dung lượng mang về là lớn nhất nhưng vẫn không vượt quá ~K~.

Hãy tính tổng dung lượng lớn nhất mà robot có thể mang về.

Dữ liệu

Gồm ~4~ dòng:

• Dòng thứ nhất chứa số nguyên ~A~.
• Dòng thứ hai chứa số nguyên ~B~.
• Dòng thứ ba chứa số nguyên ~C~.
• Dòng thứ tư chứa số nguyên ~K~.

Trong đó:

~1 \le A, B, C, K \le 10^9~

Kết quả

In ra tổng dung lượng lớn nhất mà robot có thể mang về nhưng không vượt quá ~K~.

Nếu không có khối pin nào có thể mang được, in ra ~-1~.

Ví dụ

Dữ liệu

8
3
10
14

Kết quả

13

Giải thích

Robot có thể lựa chọn:

• Khối pin ~8~: tổng dung lượng là ~8~.
• Khối pin ~3~: tổng dung lượng là ~3~.
• Khối pin ~10~: tổng dung lượng là ~10~.
• Hai khối ~8~ và ~3~: tổng dung lượng là ~11~.
• Hai khối ~8~ và ~10~: tổng dung lượng là ~18~, vượt quá ~K = 14~.
• Hai khối ~3~ và ~10~: tổng dung lượng là ~13~.

Tổng dung lượng lớn nhất không vượt quá ~14~ là ~13~.

NHỮNG CHIẾC GHẾ CÒN TRỐNG

Trong một hội trường có ~N~ chiếc ghế, được đánh số liên tiếp từ ~1~ đến ~N~.

Ban tổ chức thực hiện hai lần đánh dấu:

1. Lần thứ nhất: Đánh dấu những chiếc ghế có số thứ tự chia hết cho ~3~.
2. Lần thứ hai: Đánh dấu những chiếc ghế có số thứ tự không chia hết cho ~5~.

Những chiếc ghế đã được đánh dấu sẽ không được sử dụng.

Hãy tính số lượng ghế chưa bị đánh dấu và còn có thể sử dụng.

Dữ liệu

Một dòng chứa số nguyên dương N (1 < N < 10^9).

Kết quả

In ra số lượng ghế chưa bị đánh dấu.

Ví dụ

Dữ liệu

20

Kết quả

3

Giải thích

Với ~N = 20~, những chiếc ghế chưa bị đánh dấu là:

~5, 10, 20~

Vậy có tất cả ~3~ chiếc ghế còn sử dụng được.

NUÔI ĐÀN CÁ

Một hồ cá có ~2~ con cá khi bắt đầu nuôi. Đàn cá phát triển theo hai giai đoạn luân phiên:

• Ở giai đoạn thứ nhất, số lượng cá tăng gấp đôi.
• Ở giai đoạn thứ hai, hồ được thả thêm ~3~ con cá.

Sau giai đoạn thứ hai, quá trình lại quay về giai đoạn thứ nhất.

Ban đầu, đàn cá chuẩn bị bước vào giai đoạn thứ nhất.

Hãy tính số lượng cá trong hồ sau ~N~ lần phát triển.

Dữ liệu

Một dòng chứa số nguyên ~N~ ~(0 \le N \le 100)~.

Kết quả

In ra số lượng cá trong hồ sau ~N~ lần phát triển.

Ví dụ

Dữ liệu

5

Kết quả

34

Giải thích

Với ~N = 5~, số lượng cá thay đổi như sau:

• Ban đầu: ~2~ con cá.
• Lần 1: ~2 \times 2 = 4~.
• Lần 2: ~4 + 3 = 7~.
• Lần 3: ~7 \times 2 = 14~.
• Lần 4: ~14 + 3 = 17~.
• Lần 5: ~17 \times 2 = 34~.

Vậy sau ~5~ lần phát triển, hồ có ~34~ con cá.

Test case mẫu

Đầu vào mẫu 1

567

Đầu ra mẫu 1

363605759

Đầu vào mẫu 2

54

Đầu ra mẫu 2

306341

A and B

Đề bài

Bạn có hai số nguyên a và b.

Bạn có thể thực hiện các thao tác sau:

• Ở lần thao tác thứ 1, chọn một trong hai số và tăng nó thêm 1.
• Ở lần thao tác thứ 2, chọn một trong hai số và tăng nó thêm 2.
• ...
• Ở lần thao tác thứ i, chọn một trong hai số và tăng nó thêm i.

Bạn được quyền tự chọn số lượng thao tác cần thực hiện.

Ví dụ, nếu a = 1, b = 3, ta có thể thực hiện 3 thao tác:

1. Cộng 1 vào a → a = 2, b = 3
2. Cộng 2 vào b → a = 2, b = 5
3. Cộng 3 vào a → a = 5, b = 5

Yêu cầu

Hãy tính số thao tác nhỏ nhất cần thực hiện để hai số a và b trở nên bằng nhau.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 100) --- số lượng bộ dữ liệu.
• Mỗi bộ dữ liệu gồm một dòng chứa hai số nguyên a và b (1 ≤ a, b ≤ 10^9).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là số thao tác nhỏ nhất cần thực hiện để hai số a và b bằng nhau.

Ví dụ

Input

3
1 3
11 11
30 20

Output

3
0
4

Giải thích

• Bộ dữ liệu 1: Thực hiện đúng chuỗi thao tác trong ví dụ của đề bài để thu được a = b = 5.
• Bộ dữ liệu 2: Hai số đã bằng nhau ngay từ đầu nên đáp án là 0.
• Bộ dữ liệu 3: Thực hiện 4 thao tác đầu tiên đều trên số b:

20 + 1 + 2 + 3 + 4 = 30

Khi đó b trở thành 30, bằng với a.

Xếp hàng học sinh

Trong giờ thể dục, thầy giáo muốn xếp N học sinh (được đánh số báo danh từ 1 đến N) thành một hàng ngang. Để tạo sự thú vị, thầy yêu cầu các bạn xếp hàng theo quy tắc sau:

• Nhóm 1: Các bạn có số báo danh chia hết cho 5 sẽ đứng lên đầu hàng, xếp theo thứ tự số báo danh tăng dần.
• Nhóm 2: Tiếp theo là các bạn có số báo danh chia hết cho 3 (nhưng không chia hết cho 5), xếp theo thứ tự số báo danh giảm dần.
• Nhóm 3: Cuối cùng là các bạn còn lại, xếp theo thứ tự số báo danh tăng dần.

Yêu cầu

Cho hai số nguyên dương N và K. Hãy tìm số báo danh của bạn học sinh đứng ở vị trí thứ K trong hàng.

Dữ liệu

• Một dòng duy nhất chứa hai số nguyên dương N và K (1 ≤ K ≤ N ≤ 10^12).

Kết quả

• In ra một số nguyên duy nhất là số báo danh của bạn học sinh đứng ở vị trí thứ K.

Chấm điểm

• 60% số điểm với N ≤ 10^5.
• 40% số điểm với 10^5 < N ≤ 10^12.

Ví dụ

Nhập vào

10 4

In ra

6

Giải thích

• Nhóm 1 (chia hết cho 5): [5, 10]
• Nhóm 2 (chia hết cho 3, không chia hết cho 5): [9, 6, 3]
• Nhóm 3 (còn lại): [1, 2, 4, 7, 8]
• Hàng sau khi xếp: [5, 10, 9, 6, 3, 1, 2, 4, 7, 8]
• Bạn đứng ở vị trí thứ 4 (tính từ 1) là bạn mang số báo danh 6.