Code: Select all
thanks to sohel vai and fpavetic.
Moderator: Board moderators
Code: Select all
thanks to sohel vai and fpavetic.
Code: Select all
/* Number Theory */
#include <stdio.h>
int rear (short [], short [], short);
int resta (short [], short [], short [], short);
int division (short [], short, short []);
int printe (short [], short [], short [], short []);
int main ()
{
/*FILE *in = freopen ("c.in", "r", stdin);/**/
short a[10];
short x=0;
short flag=1;
int v=0;
while (x++<10)
a[x-1] = 0;
short g=0;
while (flag)
{
/*
if (v!=0&&x!=0&&g!=10)
{
printf("\n");
}
v++;
*/
x=0;
while (x++<10)
a[x-1] = 0;
char c='\0';
x=0;
while ((c=getchar())!='\n'&&c!=EOF)
{
a[x] = c-'0';
x++;
}
if (c==EOF)
flag=0;
short g=0;
while (a[g]==0&&g<10)
g++;
if (x==0)
g==8;
if (x!=0&&g!=10)
{
/*
if (v!=0&&x!=0&&g!=9)
{
printf("\n");
}
v++;
*/
/*
printf("POR FAVOR!!!: %d %d\n", x, g);
*/
short f=9, temp[10], ind=0;
while (f>=0)
{
short r=g;
while (r<=9)
{
if (a[r]==f)
{
/*
printf("\n:%d g:%d x:%d r:%d\n", a[r], g, x, r);
*/
temp[ind] = f;
a[r] = -1;
ind++;
}
r++;
}
f--;
}
/* PRINTING *
short k=0;
while (k++<10)
printf(":%d", temp[k-1]);
printf("\n");
k=0;
while (k++<10)
printf(":%d", a[k-1]);
printf("\n");
/* EOP */
f=0;
while (f++<x-g)
a[f-1] = temp[f-1];
while (f++<10)
a[f-1] = 0;
short y=9, z=x-g-1;
while (y>=0)
{
if (z>=0)
{
a[y] = a[z];
z--;
}
else
a[y] = 0;
y--;
}
short b[10];
rear (a, b, x);
short residuo[10];
y=0;
while (y++<10)
residuo[y-1] = 0;
resta (a, b, residuo, x);
short cociente[10];
y=0;
while (y++<10)
cociente[y-1] = 0;
/*division (residuo, 9, cociente);*/
printe (a, b, residuo, cociente);
division (residuo, 9, cociente);
/*if (x!=0&&g!=9)
{
printf("\n");
}
v++;
*/
}
}
return 0;
}
int rear (short a[], short b[], short x)
{
short z=0, k=9, zeros=0, u=0;
while (a[k]==0)
{
zeros++;
k--;
}
b[z] = a[k];
k--;
z++;
while (u++<zeros)
{
b[z] = 0;
z++;
}
while (k>0)
{
b[z] = a[k];
k--;
z++;
}
/*
while (u++<zeros)
{
b[z] = 0;
z++;
}
*/
short y=9;
short j=0;
while (a[j]==0)
j++;
z=9-j;
while (y>=0)
{
if (z>=0)
{
b[y] = b[z];
z--;
}
else
b[y] = 0;
y--;
}
/* PRINTING *
k=0;
while (k++<10)
printf(":%d", a[k-1]);
printf("\n");
k=0;
while (k++<10)
printf(":%d", b[k-1]);
printf("\n");
/* EOP */
return 0;
}
int resta (short a[], short b[], short r[], short x)
{
short idiot=0, k=0;
while (k<10&&!idiot)
{
if (a[k]>b[k])
{
k = x+10;
}
else if (b[k]>a[k])
{
idiot = 1;
}
k++;
}
/* PRINTING *
k=0;
while (k++<10)
printf(":%d", a[k-1]);
printf("\n");
k=0;
while (k++<10)
printf(":%d", b[k-1]);
printf("\n");
/* EOP */
if (idiot)
{
k=0;
while (k<10)
{
short d=a[k];
a[k] = b[k];
b[k] = d;
k++;
}
}
/* PRINTING *
k=0;
while (k++<10)
printf(":%d", a[k-1]);
printf("\n");
k=0;
while (k++<10)
printf(":%d", b[k-1]);
printf("\n");
/* EOP */
k=0;
short p[10];
while (k++<10)
p[k-1] = b[k-1];
short pides=0;
short h=0;
h=9;
while (h>=0)
{
if (pides)
{
p[h]++;
pides = 0;
}
if (p[h]>a[h])
{
pides = 1;
r[h] = a[h]+10-p[h];
}
else
r[h] = a[h]-p[h];
h--;
}
return 0;
}
int division (short r[], short x, short c[])
{
unsigned long long num= 0;
short y=0;
while (y<10)
{
num = num*10 + r[y];
y++;
}
/*printf("%i\n", num/9L);*/
unsigned int div=0, res=0;
y=0;
short b=0;
while (div/9==0&&y<10)
{
div = div*10 + r[y];
y++;
}
if (y==10&&div==0)
printf("0");
if (div/9>0)
{
c[b] = div/9;
res = div%9;
b++;
}
if (y<10)
{
div = res*10+r[y];
y++;
while (div/9==0&&y<10)
{
div = div*10 + r[y];
y++;
c[b]=0;
b++;
}
if (div/9>0)
{
c[b] = div/9;
res = div%9;
b++;
}
}
if (y<10)
{
div = res*10+r[y];
y++;
while (div/9==0&&y<10)
{
div = div*10 + r[y];
c[b]=0;
b++;
y++;
}
if (div/9>0)
{
c[b] = div/9;
res = div%9;
b++;
}
}
if (y<10)
{
div = res*10+r[y];
y++;
while (div/9==0&&y<10)
{
div = div*10 + r[y];
c[b]=0;
b++;
y++;
}
if (div/9>0)
{
c[b] = div/9;
res = div%9;
b++;
}
}
if (y<10)
{
div = res*10+r[y];
y++;
while (div/9==0&&y<10)
{
div = div*10 + r[y];
c[b]=0;
b++;
y++;
}
if (div/9>0)
{
c[b] = div/9;
res = div%9;
b++;
}
}
if (y<10)
{
div = res*10+r[y];
y++;
while (div/9==0&&y<10)
{
c[b]=0;
b++;
div = div*10 + r[y];
y++;
}
if (div/9>0)
{
c[b] = div/9;
res = div%9;
b++;
}
}
if (y<10)
{
div = res*10+r[y];
y++;
while (div/9==0&&y<10)
{
div = div*10 + r[y];
c[b]=0;
b++;
y++;
}
if (div/9>0)
{
c[b] = div/9;
res = div%9;
b++;
}
}
if (y<10)
{
div = res*10+r[y];
y++;
while (div/9==0&&y<10)
{
div = div*10 + r[y];
c[b]=0;
b++;
y++;
}
if (div/9>0)
{
c[b] = div/9;
res = div%9;
b++;
}
}
if (y<10)
{
div = res*10+r[y];
y++;
while (div/9==0&&y<10)
{
div = div*10 + r[y];
c[b]=0;
b++;
y++;
}
if (div/9>0)
{
c[b] = div/9;
res = div%9;
b++;
}
}
if (y<10)
{
div = res*10+r[y];
y++;
while (div/9==0&&y<10)
{
div = div*10 + r[y];
c[b]=0;
b++;
y++;
}
if (div/9>0)
{
c[b] = div/9;
res = div%9;
b++;
}
}
if (y<10)
{
div = res*10+r[y];
y++;
while (div/9==0&&y<10)
{
div = div*10 + r[y];
c[b]=0;
b++;
y++;
}
if (div/9>0)
{
c[b] = div/9;
res = div%9;
b++;
}
}
short w=0;
while (w++<b)
printf("%d", c[w-1]);
/*printf("B: %d", b);*/
if (r[9]==0&&b!=0)
printf("0");
/**/
printf("\n");
/**/
return 0;
}
int printe (short a[], short b[], short r[], short c[])
{
short k=0;
while (a[k]==0)
k++;
while (k++<10)
printf("%d", a[k-1]);
printf(" - ");
k=0;
while (b[k]==0)
k++;
while (k++<10)
printf("%d", b[k-1]);
printf(" = ");
k=0;
while (r[k]==0&&k<9)
k++;
while (k++<10)
printf("%d", r[k-1]);
printf(" = 9 * ");
k=0;
while (c[k]==0)
k++;
while (k++<10)
printf("%d", c[k-1]);
k=0;
return 0;
}
Code: Select all
IN
12300
OUT
32100 - 10023 = 22077 = 9 * 2453
IN
00001
OUT
1 - 1 = 0 = 9 * 0
IN
10
OUT
10 - 10 = 0 = 9 * 0
IN
102
OUT
210 - 102 = 108 = 9 * 12
IN
1234567890
OUT
9876543210 - 1023456789 = 8853086428 = 9 * 983676269
long long int doesn't work, I used double and got AC just now. Although n<=2000000000, how about 1999999999? the maximun of a-b is 9999999991 - 1999999999 = ... and the 9999999991 is greater than 2^64!rio wrote:You are using Big Integers, but actually long long int is enough.
With long long int, I think your code would be much shorter and easier to debug.
-----
Rio
Code: Select all
#define For(i,b) for(int i = 0; i < (int)b; ++i)
#define All(t) t.begin(),t.end()
string itos (int i) {stringstream s; s << i; return s.str();}
int stoi (string s) {istringstream in(s); int ret; in >> ret; return ret;}
string itos (int i) {stringstream s; s << i; return s.str();}
int stoi (string s) {istringstream in(s); int ret; in >> ret; return ret;}
int main ()
{
int n;
while(fin>>n)
{
string s=itos(n);
sort(All(s));
vector<string>v;
do
{
if(s[0]!='0')
v.push_back(s);
} while(next_permutation(All(s)));
int best=INT_MIN;
int a=0,b=0;
For(i,v.size())
{
Fori(j,i,v.size())
{
int aa=stoi(v[i]);
int bb=stoi(v[j]);
int x=abs(aa-bb);
if(x > best) {best=x;a=aa;b=bb;}
}
}
int at=a,bt=b;
a=max(at,bt);
b=min(at,bt);
int k=best/9;
printf("%d - %d = %d = 9 * %d\n",a,b,best,k);
}
return 0;
}
Plz, try to find the exactly maximum of a-b! how about cin the n as string and sort it.armansuleimenov wrote:How can I optimize my solution to run in <=1 sec? Here is my code:
Code: Select all
#define For(i,b) for(int i = 0; i < (int)b; ++i) #define All(t) t.begin(),t.end() string itos (int i) {stringstream s; s << i; return s.str();} int stoi (string s) {istringstream in(s); int ret; in >> ret; return ret;} string itos (int i) {stringstream s; s << i; return s.str();} int stoi (string s) {istringstream in(s); int ret; in >> ret; return ret;} int main () { int n; while(fin>>n) { string s=itos(n); sort(All(s)); vector<string>v; do { if(s[0]!='0') v.push_back(s); } while(next_permutation(All(s))); int best=INT_MIN; int a=0,b=0; For(i,v.size()) { Fori(j,i,v.size()) { int aa=stoi(v[i]); int bb=stoi(v[j]); int x=abs(aa-bb); if(x > best) {best=x;a=aa;b=bb;} } } int at=a,bt=b; a=max(at,bt); b=min(at,bt); int k=best/9; printf("%d - %d = %d = 9 * %d\n",a,b,best,k); } return 0; }
that may be helpful.ligregni wrote:Hi!
I tried to make my code (Is the one all disordered above) with short [] (digit by digit) because I tried to use long long int before and I got WA, and with my rudimentary method (like child) I got AC (obviously it didn't help in the contest)
I wanna ask you something:
Type Bits
int 16
long 32
long long 64
So I tried (this problem specificly) with unsigned long, now I realize it is wrong because even the input is smaller, but when permuting, it can exceed the 4,xxx,xxx,xxx that unsigned long provides.
Someone suggested me to use double... but... can double offer me the precision I need???
Can unsigned long long (in theory up to 18,xxx,xxx,xxx,xxx,xxx,xxx) solve the problem?, does unsigned long long really exists? (I know is an stupid question, but here in my computer I tried to make calculations with 10-digit numbers with unsigned long long and it make wrong answers, but clearly, it could be my compiler, and UVa can accept that)
Thanks and sorry about my english!
Sergio Ligregni, MEX