Bài 6: Kẹo - Tài liệu Tin học

Đăng bởi Admin

Tháng 10 7, 2022

https://chuyenhalong.ucode.vn/problems/keo-118684

Sau khi vượt qua một bài kiểm tra, Vasya đã nhận cho mình một hộp có $n$ kẹo. Anh quyết định ăn một lượng kẹo bằng nhau mỗi sáng cho đến khi không còn kẹo nữa. Tuy nhiên, Petya cũng chú ý đến chiếc hộp và quyết định lấy một ít kẹo cho mình.

Điều này có nghĩa là quá trình ăn kẹo là như sau: ban đầu Vasya chọn một số nguyên duy nhất là $\mathrm{k}$ , giống nhau cho tất cả các ngày. Sau đó, vào buổi sáng anh ấy ăn $\mathrm{k}$ cái kẹo từ hộp (nếu có ít hơn $\mathrm{k}$ cái kẹo trong hộp, anh ấy ăn tất cả), sau đó vào buồi tối Petya ăn $10 \%$ số kẹo còn lại trong hộp. Nếu vẫn còn kẹo trong hộp, quá trình lặp lại – ngày hôm sau Vasya ăn $k$ kẹo một lần nữa, và Petya $-10 \%$ kẹo còn lại trong một hộp và như vậy. Nếu số lượng kẹo trong hộp không chia hết cho 10 , Petya làm tròn số lượng anh ta lấy từ hộp xuống. Ví dụ, nếu có 97 Kẹo trong hộp, Petya sẽ chỉ ăn 9 của họ. Đặc biệt, nếu có ít hơn 10 cái kẹo trong hộp, Petya sẽ không ăn chút nào.

Nhiệm vụ của bạn là tìm ra số lượng tối thiểu $\mathrm{k}$ mà Vasya có thể chọn để anh ta ăn ít nhất một nưa trong $\mathrm{n}$ cái kẹo anh ban đầu có. Lưu ý rằng số $\mathrm{k}$ phải là số nguyên.

Đầu vào
– Dòng đầu tiên chứa một số nguyên duy nhất $\mathrm{n}\left(1 \leq \mathrm{n} \leq 10^{18}\right)$ – số lượng kẹo ban đầu trong hộp.

Đầu ra
– Xuất ra một số nguyên duy nhất – số lượng tối thiểu $\mathrm{k}$ điều đó sẽ cho phép Vasya ăn ít nhất một nửa số kẹo mà anh ta có.

Ví dụ

Sample input	Sample output
68	3

Chú ý: Trong mẫu, lượng kẹo, với k $=3$ , sẽ thay đổi theo cách sau (Vasya ăn trước)

$68 \rightarrow 65 \rightarrow 59 \rightarrow 56 \rightarrow 51 \rightarrow 48 \rightarrow 44 \rightarrow 41 \rightarrow 37 \rightarrow 34 \rightarrow 31 \rightarrow 28 \rightarrow 26 \rightarrow 23 \rightarrow 21 \rightarrow 18 \rightarrow 17 \rightarrow 14 \rightarrow$

$13 \rightarrow 10 \rightarrow 9 \rightarrow 6 \rightarrow 6 \rightarrow 3 \rightarrow 3 \rightarrow 0 \text {. }$

Tổng cộng, Vasya sẽ ăn 39 viên kẹo, trong khi Petya 29.
Ràng buộc:
– Có $70 \%$ số điểm thỏa mãn điều kiện: $\mathrm{n} \leq 10^6$ .
– $30 \%$ số điểm còn lại thỏa mãn điều kiện $\mathrm{n} \leq 10^{18}$ .