Question

ACM问题 我的代码怎么不对呢？？ http://acm.swjtu.edu.cn/JudgeOnline/showproblem?problem_id=1634

http://acm.swjtu.edu.cn/JudgeOnline/showproblem?problem_id=1634
我的代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <ctype.h>
#include <map>
#include <string>
#include <set>
#include <bitset>
#include <utility>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <iostream>
#include <fstream>
#include <list>
using namespace std;
const int MAXL = 500;
struct BigNum
{
int num[MAXL];
int len;
};
//高精度比较 a > b return 1, a == b return 0; a < b return -1;
int Comp(BigNum &a, BigNum &b)
{
int i;
if(a.len != b.len) return (a.len > b.len) ? 1 : -1;
for(i = a.len-1; i >= 0; i--)
if(a.num[i] != b.num[i]) return (a.num[i] > b.num[i]) ? 1 : -1;
return 0;
}
//高精度除以低精度,除的结果为c, 余数为f
void Div1(BigNum &a, int &b, BigNum &c, int &f)
{
int i, len = a.len;
memset(c.num, 0, sizeof(c.num));
f = 0;
for(i = a.len-1; i >= 0; i--)
{
f = f*10+a.num[i];
c.num[i] = f/b;
f %= b;
}
while(len > 1 && c.num[len-1] == 0) len--;
c.len = len;
}
//将字符串转为大数存在BigNum结构体里面
BigNum ToNum(char *s)
{
int i, j;
BigNum a;
a.len = strlen(s);
for(i = 0, j = a.len-1; s[i] != '\0'; i++, j--)
a.num[i] = s[j]-'0';
return a;
}

void Init(BigNum &a, char *s, int &tag)
{
int i = 0, j = strlen(s);
if(s[0] == '-') {j--; i++; tag *= -1;}
a.len = j;
for(; s[i] != '\0'; i++, j--)
a.num[j-1] = s[i]-'0';
}
int main()
{
BigNum a, c;
char s1[101], s2[100],b[100];
int t,count=1;
int b15=15,remainder;
int i,j,sign=0;
cin>>t;
getchar();
while(count<=t)
{
sign=0;
gets(s1);
int tag = 1;
Init(c, s2, tag);
int h=strlen(s1);
for(i=0;i<h;i++)
{
memset(b,0,sizeof(b));
for(j=i;j<=h;j++)
{
b[j-i]=s1[j];
}
Init(a,b,tag);
//高精度除以低精度,除的结果为c, 余数为f
Div1(a,b15,c,remainder);
if(remainder==0)
{
sign=1;
break;
}
}
if(sign==1)
cout<<"Test #"<<count<<": "<<b<<endl;
else
{
cout<<"Test #"<<count<<": impossible"<<endl;
}
count++;
}
return 0;
}

Answer 1

我觉得用不着这么麻烦...
要构造整除15的数字嘛，就是要满足可以同时整除3和5
那么也就是保证末尾是0或5并且各位数字加和可以整除3咯

先提供一个思路，希望你自己思考一下，AC的代码在下面，如果你实在过不了再看，另外注意格式(我悲剧的在格式问题上卡了4轮...)：

#include <iostream>
#include <cstring>
using namespace std;

int cmp(const void *a, const void *b)
{
return *(char*)b - *(char*)a;
}

int main()
{
int cases, n, i, len, mos, mo1, mo2, mv1, mv2, i1[2], i2[2];
long sum;
char input[101];
bool flag;

cin>>cases;
for(n = 0; n < cases; n++)
{
cin>>input;
len = strlen(input);
for(i = 0, flag = false, sum = 0; i < len; i++)
{
sum += input[i] - '0';
if(!((input[i] - '0') % 5))
{
flag = true;
}
}
if(flag)
{
qsort(input,len,sizeof(char),cmp);
// cout<<input;
mos = sum % 3;
mo1 = 0;
mo2 = 0;

mv1 = mos; //mos=1时，mv1=1；mos=2时，mv1=2，1+1=2
mv2 = 3 - mos; //mos=2时，mv2=1；mos=1时，mv2=2，2+2=4，4 % 3 = 1

if(input[len - 1] != '0')
{
for(i = len - 1; i >= 0; i --)
{
if(input[i] == '5')
{
strcpy(&input[i],&input[i + 1]);
input[len - 1] = '5';
break;
}
}
}
for(i = len - 2; i >= 0; i --)
{
if((input[i] - '0') % 3 == 1 && mo1 != mv1)
{
i1[mo1 ++] = i;
}
if((input[i] - '0') % 3 == 2 && mo2 != mv2)
{
i2[mo2 ++] = i;
}
}
if((mo1 == mv1 || mo2 == mv2 || sum % 3 == 0))
flag = true;
else
flag = false;
}
if(flag)
{
if(mv1 < mv2 && mo1 == mv1)
{
for(i = 0; i < mo1; i ++)
{
strcpy(&input[i1[i]], &input[i1[i] + 1]);
}
}
else if(mv2 < mv1 && mo2 == mv2)
{
for(i = 0; i < mo2; i ++)
{
strcpy(&input[i2[i]], &input[i2[i] + 1]);
}
}
else
{
if(mo1 == mv1)
{
for(i = 0; i < mo1; i ++)
{
strcpy(&input[i1[i]], &input[i1[i] + 1]);
}
}
else
{
for(i = 0; i < mo2; i ++)
{
strcpy(&input[i2[i]], &input[i2[i] + 1]);
}
}
}

if(input[0] == '0')
input[1] = 0;
cout<<"Test #"<<n+1<<": "<<input<<endl;
}
else
cout<<"Test #"<<n+1<<": "<<"impossible"<<endl;
}

return 0;
}

Answer 2

你试一下不要把x/y,直接3*x/y,取整输出，你的程序应该是a=(double)x/(double)y;的算法有点问题吧 ，还有一点x/y==1的时候正确答案是.3000000000；
仅供参考：
#include<stdio.h>
int main()
{
int i,t,x,y;
int c[10],sign=0;
double a=0;
char ch;
scanf("%d",&t);
getchar();
while(t--)
{
scanf("%d",&x);
scanf("%c",&ch);
scanf("%d",&y);
a=(double)x/(double)y;

printf(".");
for(i=0;i<10;i++)
{
x=x*3;
c[i]=(int)(x/y);
x=x%y;
printf("%d",c[i]);
}
printf("\n");
}
return 0;
}