Tìm số (THTA Vòng Chung kết)

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Thời gian:

Scratch 10.0s

Tác giả:

Small , zipdang04

Dạng bài

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho số tự nhiên \(N\). Tìm số tự nhiên \(A\) thoả mãn các điều kiện sau:

\(A < N\);
\(A\) lớn nhất có thể;
Số lượng chữ số của \(A\) bằng số lượng chữ số của \(N\);
Tổng các chữ số của \(A\) bằng tổng các chữ số của \(N\).

Input

Dữ liệu nhập vào từ bàn phím gồm số tự nhiên \(N (N \le 10^{15})\).

Output

In ra màn hình một số \(A\) duy nhất thoả mãn điều kiện đề bài, nếu không tìm được số nào thoả mãn thì in ra \(0\).

Example

Test 1

Input

Output

Note

Có nhiều số như \(155, 227, 236 ...\) nhỏ hơn \(245\), đều có ba chữ số và có tổng các chữ số bằng \(11\) nhưng \(236\) là số lớn nhất thỏa mãn.

Test 1

Input

Output

Note

Không có số tự nhiên nào nhỏ hơn \(9\) mà có tổng các chữ số bằng \(9\).

Bình luận

sao lại TLE??? Rõ O(N) mà!!!

#include<bits/stdc++.h>
#define int long long
main() {
    try{
        std::vector<int> a;
        int N;
        std::cin >> N;
        for (int i = 1; i < N; ++i) {
            int sum_i = 0;
            int sum_N = 0;
            std::string str_i = std::to_string(i);
            std::string str_N = std::to_string(N);
            for (char c : str_i) {sum_i += c - '0';}
            for (char c : str_N) {sum_N += c - '0';}
            if (sum_i == sum_N && str_i.length() == str_N.length()) {a.push_back(i);}}
        if (!a.empty()) {std::cout << *std::max_element(a.begin(), a.end());}else{std::cout << 0;}
    } catch (std::invalid_argument&) {std::cout << 0;}}

2 bình luận nữa