結果

問題 No.297 カードの数式
コンテスト
ユーザー peroon
提出日時 2019-04-24 19:14:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 4,135 bytes
コンパイル時間 2,367 ms
コンパイル使用メモリ 178,608 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-08 18:17:15
合計ジャッジ時間 2,913 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl

// 構文解析セット
typedef string::const_iterator State;
class ParseError {};
ll number(State &begin) {
    ll ret = 0;
    while (isdigit(*begin)) {
        ret *= 10;
        ret += *begin - '0';
        begin++;
    }
    return ret;
}
ll term(State &begin) {
    ll ret = number(begin);
    for (;;) {
        if (*begin == '*') {
            begin++;
            ret *= number(begin);
        } else if (*begin == '/') {
            begin++;
            ret /= number(begin);
        } else {
            break;
        }
    }
    return ret;
}
ll expression(State &begin) {
    ll ret = term(begin);
    for (;;) {
        if (*begin == '+') {
            begin++;
            ret += term(begin);
        } else if (*begin == '-') {
            begin++;
            ret -= term(begin);
        } else {
            break;
        }
    }
    return ret;
}
// 構文解析セットおわり

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin >> N;

    ll plus = 0;
    ll minus = 0;
    string s;

    FOR(i, 0, N){
        char c;
        cin >> c;
        if(c=='+') plus++;
        if(c=='-') minus++;
        if(isdigit(c)) s.push_back(c);
    }

    string s_max;
    string s_min;

    // 全て+
    if(minus==0){
        // 最小値
        string t = s;
        sort(ALL(t));
        ll L = plus+1;
        string box[L];
        ll index = 0;
        for(char c : t){
            box[index].push_back(c);
            index++;
            index %= L;
        }
        stringstream ss;
        FOR(i, 0, L){
            if(i){
                ss << '+';
            }
            ss << box[i];
        }
        s_min = ss.str();

        // 最大値
        stringstream ss_max;
        t = s;
        L = s.size();
        sort(ALL(t));
        string sub = t.substr(0, plus);
        for(char c : sub){
            ss_max << c << '+';
        }
        string rest = t.substr(plus);
        sort(ALL(rest), greater<char>());
        ss_max << rest;
        s_max = ss_max.str();
    }
    else if(plus==0 && minus>0){
        // マイナスのみ
        // 最大値
        string t = s;
        sort(ALL(t), greater<char>());
        ll L = t.size();
        stringstream ss;
        ss << t.substr(0, L-minus);
        string sub = t.substr(L-minus);
        for(char c : sub){
            ss << '-' << c;
        }
        s_max = ss.str();

        // 最小値
        t = s;
        sort(ALL(t));
        stringstream ss_min;
        FOR(i, 0, minus){
            ss_min << t[i] << '-';
        }
        sub = t.substr(minus);
        sort(ALL(sub), greater<char>());
        ss_min << sub;
        s_min = ss_min.str();
    }
    else{
        // +, -の混合
        // 最大値
        string t = s;
        sort(ALL(t));
        string s_for_minus = t.substr(0, minus);
        string s_for_plus = t.substr(minus, plus);
        string rest = t.substr(minus+plus);
        sort(ALL(rest), greater<char>());
        stringstream ss;
        ss << rest;
        for(char c : s_for_plus){
            ss << '+' << c;
        }
        for(char c : s_for_minus){
            ss << '-' << c;
        }
        s_max = ss.str();
        
        // 最小値
        t = s;
        sort(ALL(t));
        s_for_plus = t.substr(0, plus);
        s_for_minus = t.substr(plus, minus);
        rest = t.substr(plus+minus);
        sort(ALL(rest), greater<char>());
        
        stringstream ss2;
        for(char c : s_for_plus){
            ss2 << c << '+';
        }
        for(char c : s_for_minus){
            ss2 << c << '-';
        }
        ss2 << rest;
        s_min = ss2.str();
    }

    State it = s_max.begin();
    ll ma = expression(it);
    
    State it2 = s_min.begin();
    ll mi = expression(it2);

    p2(ma, mi);
    
    return 0;
}
0