POJ 2718

質問

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int numbers[10];
int length;
int n;

int permutation(int num[10]){
int i; int oneco=0;
for(i=0;i<length;i++){
if(num[i]){oneco++;}
}
int length2 = length-oneco;
if((oneco==length)||(oneco==0)){return 1000000000;}
if(abs(length2-oneco)>=2){return 1000000000;}
vector<int> one;
vector<int> two;

for(int i=0;i<length;i++){
if(num[i]){one.push_back(numbers[i]);}
else{two.push_back(numbers[i]);}
}
int len1 = one.size();
int len2 = two.size();
//cout << len1 << len2 << endl;
// int num1[10];int num2[10];
vector<int> num1;
vector<int> num2;

//cout << one[1] << one[2] << endl;
int count1=0;int count2 = 0;
sort(one.begin(),one.end());
sort(two.begin(),two.end());
do{
int num=0;
for(int i=1;i<len1;i++){
int onei = one[i];
for(int i2=0;i2<i;i2++){
onei = onei*10;
}
num = num + onei;
}//cout << num << endl;
if(one[0]==0){num = num;}
else {num = num + one[0];}
num1.push_back(num);
//cout << num << endl;
count1++;
}while(next_permutation(one.begin(),one.end()));

do{
int num = 0;
for(int i=1;i<len2;i++){
int twoi = two[i];
for(int i2 =0;i2<i;i2++){
twoi = twoi*10;
}
num = num + twoi;
// cout << num << endl;
}//cout << "here" << num << endl;
if(two[0]==0){num = num;}
else {//cout << num ;
num = num + two[0];
//cout << " " << num << endl;
}
num2.push_back(num);
//cout << "here" << num << endl;
count2++;
}while(next_permutation(two.begin(),two.end()));

int ans = 1000000000;
//cout << len2;
int dummy1 = 1;
for(int x=1;x<len1;x++){
dummy1 = dummy1*10;
}//cout << dummy1;
int dummy2 = 1;
for(int x=1;x<len2;x++){//cout << dummy2<< endl;
dummy2 = (dummy2)*10;
//cout << dummy2<< endl;
}//cout << dummy2;

for(int i=0;i<count1;i++){//cout << num1[i] << dummy1 << endl;
if((num1[i]%dummy1)==num1[i]){if(num1[i]!=0){continue;}}
for(int i2=0;i2<count2;i2++){
if((num2[i2]%dummy2)==num2[i2]){if(num1[i]!=0){continue;}}
ans = min(ans,abs(num1[i]-num2[i2]));

}
}
return ans;
}

//int permutation(int i[10]){return 1;}
int dfs(int i,int num[10]){
if(i==length) return permutation(num);
num[i]=0;
int ans1 = dfs(i+1,num);
num[i]=1;
int ans2 = dfs(i+1,num);
return min(ans1,ans2);
}

int main(){

cin >> n;
getchar();
for(int i=0;i<n;i++){
/*for(length=0;length<10;length++){
cin >> numbers[length];
char c = getchar();
if(c=='\n'){break;}
}*/
string str;
while(1){
char c = getchar();
if(c=='\n'){break;}
str += c;}

length = 0;

for(int i2=0;i2<str.length();i2=i2+2){

numbers[length] = (int)str[i2]-'0';
length++;
}
// cout << length;
int dummy[10] = {0,0,0,0,0,0,0,0,0,0};
cout << dfs(1,dummy) << endl;
}
}

上記のどこが間違っているか教えてください。POJの2718です。書いてあるテストは通りました。

回答No.2

kmee

> pojでwrong answerと出たからです

ということは、他のテストパターンではパスしなかった、ということでしょう。
実際にいくつか入力を試してみたらどうです?

これとはまったく異なるアルゴリズムで作って、二つの結果を比較するとか。
1023通り「しか」ないから、全部の結果を比較するくらい簡単です。

他は、あなたがどんなアルゴリズムで解を求めようとしているのかがわからないので、
・アルゴリズムに間違いがあるかどうか(間違いがあるなら、いくら「正しいプログラム」でも答えを間違える)
・そのアルゴリズム通りにプログラミングできているのか(アルゴリズム通りにできていなければ答えを間違える)
が判断できません。

お礼

解決しました、ありがとうございました！

回答No.1

kmee

こんなコメントのないプログラムを延々読む気はありません。

どうして間違っていると思うのですか?

> if((oneco==length)||(oneco==0)){return 1000000000;}
> if(abs(length2-oneco)>=2){return 1000000000;}
> int ans = 1000000000;

こういう定数は、マクロ、enum、const等で名前を付けるのが定石です。

> nt numbers[10];
> int length;
> int n;

グローバル変数にする意味はあるのでしょうか?

補足

>どうして間違っていると思うのか
pojでwrong answerと出たからです。自分でどうして間違っているのかわからず、質問させていただきました。

>グローバル変数
nはありませんでした。すみません。
numbersとlengthは、main関数で値を確定した後に、計算するmain関数以外の関数でまた使うため、グローバル変数にしています。