Do you have any suggestions? Below is my code. I do not have any idea what is wrong with my code.
Code: Select all
#include <stdio.h>
#include <string.h>
#include <ctype.h>
const int Length=22, HashSize=19019, HashFactor=17;
char Max[Length], Key[HashSize][Length], Val[HashSize][Length];
bool Used[HashSize];
int hash(char *String)
{
int i=0, HashVal=0;
for(i=0;i<int(strlen(String));i++)
HashVal=(((HashFactor*HashVal)+String[i]-'0')%HashSize);
return HashVal;
}
void reverse(char *String)
{
int i;
char c;
for(i=0;i<int(strlen(String))/2;i++)
{
c=String[i];
String[i]=String[strlen(String)-1-i];
String[strlen(String)-1-i]=c;
}
}
void normalize(char *String)
{
int i=strlen(String);
while(String[i-1]=='0' && i>1)
i--;
String[i]='\0';
}
bool leq(char *S1, char *S2)
{
int i;
if(strlen(S1)!=strlen(S2))
return (strlen(S1)<strlen(S2));
for(i=strlen(S1)-1;i>=0;i--)
if(S1[i]<S2[i])
return true;
else if(S1[i]>S2[i])
return false;
return true;
}
void test(char *S1, char *S2)
{
if(!leq(S1, S2))
strcpy(S2, S1);
}
bool div(char *Dividend, int Divisor, char *Quotient)
{
int Carry=0, i;
Quotient[strlen(Dividend)]='\0';
for(i=strlen(Dividend)-1;i>=0;i--)
{
Carry=10*Carry+Dividend[i]-'0';
Quotient[i]=(Carry/Divisor)+'0';
Carry=Carry-(Divisor*(Quotient[i]-'0'));
}
return (Carry==0);
}
void cut(char *String, int Pos, int Length, char *New)
{
int i;
for(i=0;i<Pos;i++)
New[i]=String[i];
for(i=Pos;i<int(strlen(String))-1;i++)
New[i]=String[i+Length];
New[strlen(String)-Length]='\0';
}
void solve(char *String)
{
char Local[Length], LocalMax[Length]="0";
int i, HashVal=hash(String);
bool Success=false;
normalize(String);
if(leq(String, Max))
return;
if(Used[HashVal])
if(strcmp(String, Key[HashVal])==0)
{
strcpy(String, Val[HashVal]);
test(String, Max);
return;
}
if(strcmp(String, "0")==0)
return;
if(div(String, 3, Local))
{
Success=true;
solve(Local);
test(Local, LocalMax);
}
if(div(String, 7, Local))
{
Success=true;
solve(Local);
test(Local, LocalMax);
}
for(i=0;i<int(strlen(String));i++)
if((String[i]=='3' || String[i]=='7') && String[i]!=String[i+1])
{
Success=true;
cut(String, i, 1, Local);
solve(Local);
test(Local, LocalMax);
}
for(i=0;i<int(strlen(String))-2;i++)
if(String[i]==String[i+1] && String[i]==String[i+2] &&
String[i]!='7' && String[i]!='3' && String[i]!=String[i+3])
{
Success=true;
cut(String, i, 3, Local);
solve(Local);
test(Local, LocalMax);
}
for(i=0;i<int(strlen(String))-6;i++)
if(String[i]==String[i+1] && String[i]==String[i+2] &&
String[i]==String[i+3] && String[i]==String[i+4] &&
String[i]==String[i+5] && String[i]==String[i+6] &&
String[i]!=String[i+7] && String[i]!='7' && String[i]!='3')
{
Success=true;
cut(String, i, 7, Local);
solve(Local);
test(Local, LocalMax);
}
Used[HashVal]=true;
strcpy(Key[HashVal], String);
if(Success)
strcpy(String, LocalMax);
test(String, Max);
strcpy(Val[HashVal], String);
}
int main()
{
int NumCases, i;
char Line[Length];
scanf("%d\n", &NumCases);
for(i=0;i<HashSize;i++)
Used[i]=false;
while(NumCases-->0)
{
gets(Line);
reverse(Line);
strcpy(Max, "0");
solve(Line);
reverse(Line);
printf("%s\n", Line);
}
return 0;
}