トップページに戻る
次のC++のサンプルへ
前のC++のサンプルへ
Problem43 独特な部分列被整除性を持つPandigital数
問題
数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので).
この数は部分列が面白い性質を持っている.
d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する.
この記法を用いると次のことが分かる.
d2 d3 d4=406は2で割り切れる
d3 d4 d5=063は3で割り切れる
d4 d5 d6=635は5で割り切れる
d5 d6 d7=357は7で割り切れる
d6 d7 d8=572は11で割り切れる
d7 d8 d9=728は13で割り切れる
d8 d9 d10=289は17で割り切れる
このような性質をもつ0から9のPandigital数の総和を求めよ.
ソース
#include <stack>
#include <string>
#include <Windows.h>
bool IsEdakiri(std::string pTarget);
void main()
{
std::stack<std::string> stk;
for (int I=0;I<=9;I++){
char wkCharArr[10];wsprintf(wkCharArr,"%d",I);
stk.push(wkCharArr);
}
__int64 Answer = 0;
while(stk.empty() == false){
std::string Popped = stk.top(); stk.pop();
if(Popped.size() == 10) {
Answer += _atoi64(Popped.c_str());
printf("%sは、条件を満たすPandigital数\n",Popped.c_str());
}
for (int I = 0; I <= 9; I++) {
char wkCharArr[10];wsprintf(wkCharArr,"%d",I);
if(Popped.find(wkCharArr) == std::string::npos){
std::string WillPush = Popped + wkCharArr;
if (IsEdakiri(WillPush) == false) {
stk.push(WillPush);
}
}
}
}
printf("答えは、%I64d\n", Answer);
}
bool IsEdakiri(std::string pTarget)
{
int Size = pTarget.size();
if (Size == 4) return (atoi(pTarget.substr(1,3).c_str()) % 2) != 0;
if (Size == 5) return (atoi(pTarget.substr(2,3).c_str()) % 3) != 0;
if (Size == 6) return (atoi(pTarget.substr(3,3).c_str()) % 5) != 0;
if (Size == 7) return (atoi(pTarget.substr(4,3).c_str()) % 7) != 0;
if (Size == 8) return (atoi(pTarget.substr(5,3).c_str()) % 11) != 0;
if (Size == 9) return (atoi(pTarget.substr(6,3).c_str()) % 13) != 0;
if (Size == 10) return (atoi(pTarget.substr(7,3).c_str()) % 17) != 0;
return false;
}
実行結果
4160357289は、条件を満たすPandigital数
4130952867は、条件を満たすPandigital数
4106357289は、条件を満たすPandigital数
1460357289は、条件を満たすPandigital数
1430952867は、条件を満たすPandigital数
1406357289は、条件を満たすPandigital数
答えは、16695334890
解説
枝切りしながらの深さ優先探索を行ってから、
printf関数の書式指定でI64dを使用してます。(__int64型のため)
MSDN --- printf関数の書式指定