| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT015D - ACM PTIT 2015 D - Quà tặng |
Tết thiếu nhi năm nay, ba bạn An, Bình, Cường lên kế hoạch làm các món quà tặng các bạn thiếu nhi ba miền Bắc, Trung, Nam. Các món quà được làm từ hai loại nguyên liệu: nguyên liệu loại A và nguyên liệu loại B. Nếu một món quà dùng x nguyên liệu loại A và y nguyên liệu loại B (x và y là các số nguyên dương), thì thời gian làm món quà đó mất 2(x-1)3(y-1). Ba bạn dự định làm các món quà với tổng thời gian là n, giả sử a, b, c tương ứng là tổng giá trị các món quà cho ba miền Bắc, Trung, Nam thì a, b, c thỏa mãn các điều kiện sau:
1) a + b + c = n; 0 < a < b < c;
2) Với mỗi miền, các món quà tạo ra không thể so sánh được với nhau, có nghĩa là không tồn tại hai món quà có giá trị 2(x-1)3(y-1) và 2(u-1)3(v-1) mà đồng thời 0 < x ≤ u và 0 < y ≤ v;
3) S(a) + S(b) + S(c) là lớn nhất, trong đó ký hiệu S(p) là tổng các chữ số của p.
Yêu cầu: Cho số nguyên dương n, hãy tìm cách tạo ra các món quà thỏa mãn điều kiện đề bài.
Input
Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa số nguyên K (K≤100), là số bộ dữ liệu.
Tiếp theo là K dòng, mỗi dòng tương ứng với một bộ dữ liệu chứa một số nguyên dương n (n ≤ 1015).
Output
Với mỗi bộ dữ liệu, ghi ra trên một dòng câu trả lời, ghi một số nguyên là giá trị S(a) + S(b) + S(c) lớn nhất tìm được.
Nếu bộ dữ liệu không tồn tại cách tạo ra các món quà thỏa mãn điều kiện đề bài thì trên dòng tương ứng chỉ ghi một số -1.
Example
Input: 2
9
21 Output: 9
21
| Được gửi lên bởi: | adm |
| Ngày: | 2015-04-19 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
