TOTALODD - Số lẻ hoàn toàn

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
 
using namespace std;
 
#define Rep(i,n) for(int i=0;i<(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fi first
#define se second
#define pb push_back
#define MP make_pair
 
typedef pair<int,int> PII;
typedef vector<int> VI;
 
class RepresentableNumbers {
public:
  int getNext(int);
};
 
int cs[55];
int nc;
int F[55][10][2][2][2];
 
int go(int pos,int need,int gr,int k1,int k2){
  if(pos == -1) {
    if(need != 0 || (!k1) || (!k2)) return -2;
    else return 0;
  }
  int&ret=F[pos][need][gr][k1][k2];
  if(ret!=-1)return ret;
  // need = need * 10 + cs[pos];
  ret=-2;
  for(int ad=0;ad<10;++ad) if(ad>=cs[pos] || gr){
    int cur = need * 10 + ad;
    for(int x1=k1?1:0;x1<=9;x1+=2){
      for(int x2=k2?1:0;x2<=9;x2+=2){
      int s = x1+x2;    
      if(s == cur || s + 1 == cur){
        int tmp = go(pos-1,cur-s,gr || ad>cs[pos],k1||x1>0,k2||x2>0);
        if(tmp!=-2){
          int z = ad;
          Rep(ii,pos)z*=10;
          if(ret == -2 || ret > z + tmp)
          	ret = z + tmp;
        }
      }
      if(x2==0)x2--;
      }
      if(x1==0)x1--;
    }    
  }
  return ret;
}
 
int RepresentableNumbers::getNext(int X) {
  nc=0;
  while(X>0){
    cs[nc++]=X%10;
    X/=10;
  }
  memset(F,-1,sizeof(F));
  int tmp = go(nc-1,0,0,0,0);
  if(tmp!=-2)return tmp;
  int t=1;
  Rep(i,nc)t*=10;
  return t;
}

RepresentableNumbers run;

int main() {
	while(true){
		string s;
		cin>>s;
		if(s=="[END]")break;
		int n;
		cin>>n;
		cout<< run.getNext(n) << endl;
	}		
}

Download