Project Euler 38

192を1, 2, 3で掛けてみよう.

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
積を連結することで1から9のPandigital数 192384576 が得られる. 192384576を 192と(1,2,3)の連結積と呼ぶ.

同じようにして, 9を1,2,3,4,5と掛け連結することでPandigital数918273645が得られる. これは9と(1,2,3,4,5)との連結積である.

整数と(1,2,...,n) (n > 1) との連結積として得られる9桁のPandigital数の中で最大のものを答えよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2038

#include <iostream>
#include <sstream>
#include <string>
#include <set>
using namespace std;

string IntToString(int number)
{
  stringstream ss;
  ss << number;
  return ss.str();
}

bool isPandigital(string str){
	if(str.size()!=9) return false;
	set<int> s;

	for(int i=0 ; i<str.size() ; i++){
		s.insert(str[i]-48);
	}

	set<int>::iterator it = s.begin();

	if(s.size()!=9) return false;

	for(int i=1; i<=9 ; i++){
		if(*it != i) return false;
		it++;
	}
	return true;
}

int main(){
	long long max=0, tmp;

	string s;
	for(int i=1; i<=10000 ; i++){
		for(int j=2 ; j<=9 ; j++){
			s.clear();
			for(int k=1 ; k<=j ; k++){
				s += IntToString(i*k);
			}

			if(isPandigital(s)){
				tmp = atoi(s.c_str());
				if(max < tmp){
					max = tmp;
				}
			}
		}
	}
	cout << max << endl;
}

正解者数が50位以内に入らない問題になるほど難しい感じがしないなあ