Algoogle

Algorithm for Programming Contest

AOJ 2565 Broken Audio Signal

Category: AOJ Tag: implementation

Broken Audio Signal

問題概要


解法


順番に数を見ていく.
前の数と比較していけばよい.
xについては可能な一番小さい数と一番大きい数をもっておく.
xが連続した場合はnone
数自体が矛盾していてもnone
大小の比較は偶奇で分けるだけ.
最後にxについて可能の数の幅をみて複数あるならambiguous
確定するならその数を返す.
ambigiousとかambigousとかで提出しないように(何チームかやったらしい).

コード


(2565.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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <sstream>
#include <string>

#define int long long
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define INF 1e9

using namespace std;

int N;
string a[1024];

int input(){
    cin >> N;
    rep(i,N) cin >> a[i];
    return N;
}

string solve(){
    int lower = -INF * 2;
    int upper = INF * 2;
    string prev = "2000000000";
    rep(i,N){
        if(a[i] == "x"){
            if(prev == "x") return "none";
            if((i + 1) % 2) {
                upper = min(upper, (int)atoi(prev.c_str()));
                if(i < N - 1) upper = min(upper, (int)atoi(a[i+1].c_str()));
            }
            else{
                lower = max(lower, (int)atoi(prev.c_str()));
                if(i < N - 1) lower = max(lower, (int)atoi(a[i+1].c_str()));
            }
        }
        else if((i + 1) % 2 && prev != "x" && atoi(prev.c_str()) <= atoi(a[i].c_str())) return "none";
        else if((i + 1) % 2 == 0 && prev != "x" && atoi(prev.c_str()) >= atoi(a[i].c_str())) return "none";
        prev = a[i];
        if(upper - lower < 2){
            return "none";
        }
    }
    if(upper - lower > 2) return "ambiguous";
    stringstream ss;
    ss << (lower + upper) / 2;
    string ans;
    ss >> ans;
    return ans;
}

signed main(){
    while(input()) { cout << solve() << endl; }
    return 0;
}

Comments