結果

問題 No.3245 Payment with 8-rep Currency
コンテスト
ユーザー GOTKAKO
提出日時 2025-08-22 22:46:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 137 ms / 2,000 ms
コード長 1,799 bytes
コンパイル時間 2,067 ms
コンパイル使用メモリ 201,176 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-22 22:46:31
合計ジャッジ時間 10,533 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long all = 9872/8;
    
    long long n = all*10;
    vector<tuple<long long,long long,long long,long long>> V(n);
    for(long long v=0; v<n; v++){
        long long best = 1001001001;
        bool ok = false;
        for(long long d=0; d*1111<=v&&ok==false; d++){
            for(long long c=0; c*111+d*1111<=v&&ok==false; c++){
                for(long long b=0; b*11+c*111+d*1111<=v&&ok==false; b++){
                    long long a = v-d*1111-c*111-b*11;
                    long long sum = a+b+c+d,use = max({a,b,c,d});
                    if(use+use < sum) V.at(v) = {a,b,c,d},ok = true;
                    else if(best > use+use-sum) best = use+use-sum,V.at(v) = {a,b,c,d};
                }
            }
        }
        if(v){
            auto [a,b,c,d] = V.at(v);
            assert(a+b+c+d != 0); 
        }
        //if(!ok){cout << v << " " << best << endl;}
    }

    long long T; cin >> T;
    while(T--){
        long long N; cin >> N;
        if(N%8){cout << "-1\n"; continue;}
        N /= 8;
        if(N < n){
            auto [a,b,c,d] = V.at(N);
            long long use = max({a,b,c,d}),sum = a+b+c+d;
            assert(a+b*11+c*111+d*1111 == N);

            if(use+use >= sum) cout << "-1\n";
            else cout << a << " " << b << " " << c << " " << d << "\n";
        }
        else{
            long long pos = N%all,memo = N;
            N -= n-all+pos;
            auto [a,b,c,d] = V.at(pos+n-all);
            assert(N%all == 0);
            N /= all;
            a += N,b += N,c += N,d += N;
            assert(a+b*11+c*111+d*1111 == memo);
            cout << a << " " << b << " " << c << " " << d << "\n";
        }
    }
}
0