SRM 505 Mid PerfectSequences

問題

http://www.topcoder.com/stat?c=problem_statement&pm=11397&rd=14434 (要ログイン)

• 数列 a[1], a[2], ..., a[n] が以下の2条件を満たす時、その数列は perfect であると言う。
  • a[1] + ... + a[n] = a[1] * ... * a[n]
  • a[1] >= 0, ..., a[n] >= 0
• 適当な数列が与えられるので、「丁度1個」を変更することで、その数列を perfect に出来るかどうか判定せよ

方針

• a[i] を変更することで a[1], ..., a[n]が perfect になるかどうかは、(a[i] 以外全部の和) + x = (a[i] 以外全部の積) * x を満たす整数 x が存在するかどうかと同じ
• 但し、「丁度1個」を変更しないといけないので、x が a[i] に等しくないことは確認しないとだめ
• あと、ゼロ割に気を付けないとだめ
• あと、桁あふれに気を付けないとだめ

回答

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;

class PerfectSequences{
public:
  vector<int> seq;


  bool check(size_t i){
    long long s = 0, p = 1;
    for(size_t j = 0; j < seq.size(); j++){
      if(j != i){
	s += seq[j];
	p *= seq[j];
      }
    }

    // s + x = p * x
    if(p - 1 == 0){
      if(s == 0){
	return "Yes";
      }
    }
    else if(s % (p - 1) == 0){
      long long x = s / (p - 1);
      if(x >= 0 && x != seq[i]) return "Yes";
    }

    return false;
  }

  bool all_pos(size_t i){
    bool ret = true;
    for(size_t j = 0; j < seq.size(); j++){
      if(j != i) ret = ret && seq[j] >= 0;	
    }
    return ret;
  }

  string fixIt(vector <int> seq_){
    seq = seq_;

    for(size_t i = 0; i < seq.size(); i++){
      if(check(i) && all_pos(i)) return "Yes";
    }
    return "No";
  }



};