[白俊]10610号:30

9503 ワード
白駿 supin2 cpp テキストリンク
回答日:2021-09-23

質問する


質問リンク:https://www.acmicpc.net/problem/10610

アクセスと解析


問題を読むと無知な解決策は、入力した数字の桁数を順番に並べ、各ケースが30に分かれているかどうかをチェックすることです.
しかし、そうするのは当然間違っている.問題をよく見る条件は以下の通りです.
N入力を受け付けます.Nは最大10^5個の数字からなり、0で始まることはありません.
つまり、10,000桁の数字も入力されます.long long範囲にも範囲外の値が表示される場合があります.次のエラーコードに無邪気に従って作成すると、実行時のエラーやタイムアウトの結果が表示されます.
どうしようか悩んだこれらの問題の多くはO(n)内で終わらないとタイムアウトが発生する確率が高いので,O(n)で実現する方法を考えた.
質問で30の倍数を探さなければならない理由は、30の倍数が3の倍数、10の倍数であるべきだ.
3の倍数は全桁加算時の3の倍数で、10の倍数は最後の桁に0を加えた倍数です.
このような考えを持って、以下のように体現しています.
  • で指定された数値(実際には文字列として入力される)の桁数を降順に並べ替えます.
    (降順で並べ替えた理由は、ゼロかどうかは不明で、30の倍数であれば最大数を見つけたいからです.)
  • 最後の位置に0があるかどうかを確認します.
    2-1. 0がなければどうしても10の倍数を生成できないので、-1を出力して終了します.
    2-2. 0があれば、すべての桁数を加えて3の倍数であることを確認します.
  • 条件を満たすと、その数が出力されます.

    • コード（実行時）

    // 백준 10610번 : 30
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    string str = "";
    cin >> str;

    sort(str.begin(), str.end());

    long long maxNum = -1;
    do {
        long long num = stoll(str);
        if (num % 30 == 0) {
            maxNum = max(maxNum, num);
        }
    } while (next_permutation(str.begin(), str.end()));

    if (maxNum == -1) {
        cout << "-1";
    } else {
        cout << maxNum;
    }
    return 0;
}

    コード#コード#

    // 백준 10610번 : 30
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    string str = "";
    cin >> str;

    long long maxNum = 0;
    sort(str.begin(), str.end(), greater<>());

    if (str.back() != '0') {
        cout << -1;
    } else {
        for (char ch : str) {
            maxNum += ch - '0';
        }
        if (maxNum % 3 == 0) {
            cout << str;
        } else {
            cout << -1;
        }
    }
    
    return 0;
}

    結果



    フィードバック


    熟考し、間違った時に問題を解決する思考能力を育成する.
    iOSプロジェクトgitignoreファイルにファイルタイプの解釈が含まれています
    解決npm build--prod、ERROR in budgets、maximum exceeded for initial.Budget 5 MB was exceeded by 750 kBの問題