TLE-oj Cup Round 3 - Nhảy về không

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

Thời gian: 1.5s

Bộ nhớ: 586M

Input: COUNTSUB.inp

Output: COUNTSUB.out

Tác giả:

Sunlight

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: (COUNTSUB.inp)

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^9$ .

Output: (COUNTSUB.out)

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

Subtasks

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

Sample

Input (COUNTSUB.inp)

Output (COUNTSUB.out)

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.