【AOJ 2565】Broken Audio Signal
問題
Broken Audio Signal | Aizu Online Judge
方針
- 区間を狭めていって, その区間によって結果を出力する.
- xが偶数番目のときに上界, 奇数番目のときに下界を決めることができる.
- xが連続した時はnone, 上界がないなど様々な場合分けがあってとてもつらい.
コード
#include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) #define MAX_V 1000000000 using namespace std; typedef long long ll; int n; string data[10000]; ll toNum(string s){ return (int)atoi(s.c_str()); } string solve(){ ll upper, lower; string prev; upper = MAX_V * 2; lower = -MAX_V * 2; prev = to_string(upper); rep(i, n){ if(data[i] == "x"){ if(prev == "x") return "none"; // xが連続 if((i+1) % 2 == 1){ // odd upper = min(upper, toNum(prev)); if(i < n-1) upper = min(upper, toNum(data[i+1])); }else{ // even lower = max(lower, toNum(prev)); if(i < n-1) lower = max(lower, toNum(data[i+1])); } }else{ // 数字のときに正しいか判別 if((i+1)%2 == 1 && prev != "x"){ if((toNum(prev)) <= toNum(data[i])) return "none"; }else if(prev != "x"){ if((toNum(prev)) >= toNum(data[i])) return "none"; } } prev = data[i]; if(upper - lower < 2) return "none"; } if(upper - lower > 2) return "ambiguous"; return to_string((upper + lower) / 2); } signed main(){ while(cin >> n, n){ rep(i, n){ cin >> data[i]; } cout << solve() << endl; } }