TLEoj Contest #02 - Nhảy về không (bản khó)

Điểm: 1900 (thành phần)

Thời gian: 1.5s

Bộ nhớ: 586M

Input: bàn phím

Output: màn hình

Tác giả:

Sunlight, huyhau6a2

Dạng bài

Bạn được cho một số nguyên dương $n$ . Với mỗi thao tác, bạn trừ $n$ cho tổng các chữ số của nó. Đếm số thao tác cần thiết để có $n = 0$ .
Bạn phải trả lời $q$ truy vấn như vậy.

P/s: Bài này có giới hạn bộ nhớ là $600000KB$ (600 nghìn kilobytes).

Input, Output và Subtasks

Input: (bàn phím)

Dòng đầu tiên là số nguyên dương $q \le 10^5$ .
$q$ dòng tiếp theo, mỗi dòng là một số nguyên dương $n \le 10^{18}$ .

Output: (màn hình)

Gồm $q$ dòng, dòng thứ $i$ là kết quả truy vấn thứ $i$ .

Subtasks

Subtask 1 $(12\%)$ : $q = 1,n\le 10^9$ .
Subtask 2 $(12\%)$ : $n \le 10^5$ .
Subtask 3 $(16\%)$ : $n \le 10^6$ .
Subtask 4 $(16\%)$ : $n \le 10^8$ .
Subtask 5 $(24\%)$ : $n \le 10^9$ .
Subtask 6 $(20\%)$ : Không có giới hạn gì thêm.

Sample

Input (bàn phím)

Output (màn hình)

2
2
3

Notes

Ở testcase đầu tiên, $18 - 9 = 9$ và $9 - 9 = 0$ .
Ở testcase thứ hai, $19 - 10 = 9$ và $9 - 9 = 0$ .
Ở testcase thứ ba, $20 - 2 = 18$ , $18 - 9 = 9$ và $9 - 9 = 0$ .

Bình luận

Không có bình luận nào.