SRM 517 DIV1 Easy - CompositeSmash

SRM 517 DIV1 Easy - CompositeSmash

10:58

問題


http://community.topcoder.com/stat?c=problem_statement&pm=11535&rd=14542

正の整数Ｎとtargetが与えられる。
Ｎはスマッシュするとx*y=N（x,yは整数）となるｘとｙに分割することができる。
このとき、どうスマッシュしてもtargetが得られるならYes,得られないならNoを返す。

解き方


ＤＦＳで全探索。
１つの判定関数の中で全ての割り切れる数に対してtrueとなり、
かつ割り切れる数で得られるx,yのいずれかが判定関数でtrueとなるか判定する。

dp化しなければ計算量が超えそうかと思ったけど超えなかった。
こちらのソリューションでメモ化した方がよいかも。
http://community.topcoder.com/stat?c=problem_solution&cr=22263204&rd=14542&pm=11535

コード


int T;

class CompositeSmash {

public:

bool f(int N){
if(N==T)return true;

bool allfound=true,flag=false;

for(int i=2;i*i<=N;i++){
if(N%i==0){
flag=true;
allfound&=f(i)|f(N/i);
}
}

return flag ? allfound : false;
}

string thePossible(int N, int target) {
T=target;
return f(N) ?"Yes" : "No" ;
}

};

using namespace std;

#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

int dp[100001];

class CompositeSmash {

public:


string thePossible(int N, int target) {
memset(dp,0,sizeof(dp));
dp[target]=1;
for(int i=target+1;i<=N;i++){
int valid=1,flag=0;
for(int j=2;j*j<=i;j++){
if(i%j==0){
flag=1;
valid&=(dp[j]||dp[i/j]);
}
}
if(flag)dp[i]=valid;
}

return dp[N] ? "Yes" : "No";
}

};

Share this

Google Facebook Twitter More

Related Posts