Algoogle

Algorithm for Programming Contest

AOJ 2524 Mysterious Operator

Category: AOJ Tag: brute-force

Mysterious Operator

問題概要


解法


2つの数の差を頭に, 和を後ろに置くという操作.
元の式が
x + y = z
だとするとz = |x - y| * (int)log10(x + y) + x + y
まあlog10あたりが面倒くさいので文字列でやるのが楽でよい
x - y = a
x + y = b
とすると
x = (a + b) / 2
y = (b - a) / 2
とわかる.
つまり, 適当な場所で区切ったときの前後の和が2で割り切れれば,
その組み合わせがひとつあることになる.
それをすべての区切り方で試せばいい.

コード


(2524.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define rep(i,a) for(int i = 0;i < (a); i++)
using namespace std;

int main(){
    string a;
    cin >> a;
    int ans = 0;
    rep(i,a.size()){
        if(i == 0){
            int s = atoi(a.c_str());
            if(s % 2 == 0) ans++;
        }
        else{
            int s = atoi(a.substr(0,i).c_str());
            if(a.substr(i)[0] == '0') continue;
            int t = atoi(a.substr(i).c_str());
            if(s > t) break;
            if((s + t) % 2 == 0) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Comments