Người Gửi: Sai
- Problem:
Cho một số nguyên N (có thể chứa các số 0 ở đầu). Hỏi phải cộng thêm tối thiểu bao nhiêu để N trở thành số đối xứng (số cộng thêm là một số nguyên không âm - khi cộng tính cả các số 0 ở đầu nhé).
Input
Gồm nhiều bộ test, mỗi bộ test gồm một dòng chứa số nguyên N – có từ 2 đến 9 chữ số, không có dấu cách, có thể có các số 0 ở đầu.
Dữ liệu vào kết thúc bởi dòng chứa số 0.
Output
Mỗi bộ test in trên một dòng chứa kết quả của bộ test.
Example:
Input
100000100001004560001210
Output:
1097944
- Solution:
- Phương án tốt nhất là:
+ Với mỗi cặp số tại i và n-1-i (n là length xâu) (VD: 12345 có các cặp số là 1-5, 2-4, 3-3)
+ Nếu mỗi cặp có [i] = [n-1-i] thì không cần xét đến vì nó đã đối xứng rồi. (VD: 1405231 thì cặp 1-1 không phải xét nữa).
+ Nếu cặp [i] > [n-1-i] thì chỉ cần chuyển [n-1-i]=[i] (VD: 1405231 -> 1415241 : cặp 4-3 -> 4-4)
+ Nếu cặp [i] < [n-1-i] thỉ chuyển [n-1-i]=[i] và tăng tiếp các số [n-1-i-j] thêm 1 nếu còn nhớ 1 (j:(1->i)) (VD: 1415241 -> 1416141 : cặp 1-2 -> 1-1 và 5 thêm 1->6)
*Tại sao lại tăng thêm 1? Vì để chuyển 2->1 thì số phải chạy qua 10, có nghĩa là 2+9=11 ->lấy 11/10 -> 1 nên phải tăng thêm vào số kề trước nó để đúng quy tắc cộng số (vì đây là cộng số tạo đối xứng vậy nên nếu không tăng thêm theo quy tắc cộng số thì số tạo ra có thể < số ban đầu).
*Tại sao lại tăng thêm 1 nếu còn nhớ 1? VD: 1992 -> 1991 (nhớ 1) -> 2001 -> 2002; => Nếu chỉ nhớ 1 lần thì chỉ tạo ra 1992 -> 1901. Vậy nên nếu cộng vào số tiếp theo mà vẫn còn tiếp tục nhớ 1 thì phải tiếp tục cộng thêm 1 cho số tiếp theo cho đến khi nhớ 0.
1410141 -> 1410141
Quá trình lặp lại cho đến khi tạo được số đối xứng.
VD:
1409231 -> 1409241
1409241 -> 1409041 (nhớ 1) -> 1410041
1410041 -> 1410141