11371 - Number Theory for Newbies

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

S.M.ferdous
New poster
Posts: 13
Joined: Fri Nov 03, 2006 2:53 pm
Location: bangladesh
Contact:

11371 - Number Theory for Newbies

Post by S.M.ferdous » Sat Dec 29, 2007 8:41 pm

Code: Select all

        
        thanks to sohel vai and fpavetic.

Last edited by S.M.ferdous on Sun Dec 30, 2007 7:32 am, edited 1 time in total.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sat Dec 29, 2007 8:50 pm

I don't think you are handling the 'leading 0 case' properly.

What is your output for 12300?

S.M.ferdous
New poster
Posts: 13
Joined: Fri Nov 03, 2006 2:53 pm
Location: bangladesh
Contact:

Post by S.M.ferdous » Sat Dec 29, 2007 9:00 pm

for 12300 my output is:

32100 - 123 = 31977 = 9 * 3553

is it wrong?

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

Post by fpavetic » Sat Dec 29, 2007 9:06 pm

S.M.ferdous wrote:for 12300 my output is:

32100 - 123 = 31977 = 9 * 3553

is it wrong?
yes, it is.
all digits must occur in both a and b

ligregni
New poster
Posts: 11
Joined: Thu Nov 29, 2007 12:41 am
Location: Queretaro, M
Contact:

I'm getting WA!!!!

Post by ligregni » Sun Dec 30, 2007 1:39 am

Hi, here is my code

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;
}
I know it is a mess, but here are some tests I made:

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
I don't know what is wrong, I use short arrays so I don't have problems with large numbers.

THANKS

Sergio Ligregni, MEX
C: multum in parvo

"a lot since quite few"

http://acmicpc-live-archive.uva.es/nuev ... user=12539

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Dec 30, 2007 1:57 am

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

ligregni
New poster
Posts: 11
Joined: Thu Nov 29, 2007 12:41 am
Location: Queretaro, M
Contact:

Long long

Post by ligregni » Sun Dec 30, 2007 3:12 am

Thanks for your interest, but I'm a little scary about long long int, I used it in many problems and it didn't work,

so I started implementing short [], and I make the sustraction and division like elementary school,

I firstly wanna know I my tests are wrong, if there is a special number who could make wrong answers, and I could modify my code (I accept it is a terrible mess, it is in part because test printing).

Again, thanks!

Sergio Ligregni, MEX
C: multum in parvo

"a lot since quite few"

http://acmicpc-live-archive.uva.es/nuev ... user=12539

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Dec 30, 2007 3:16 am

I just try your code with 1999999999 and it gives an obviously incorrect answer. I guess you are not initializing correctly?

Ah by the way, even if you feel uneasy with long long int, I think you may consider using double / long double.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

dma
New poster
Posts: 8
Joined: Wed Dec 12, 2007 1:05 pm

Post by dma » Sun Dec 30, 2007 4:27 am

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
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!

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » Sun Dec 30, 2007 4:41 am

"...and the 9999999991 is greater than 2^64!" == FALSE

armansuleimenov
New poster
Posts: 15
Joined: Tue Sep 25, 2007 3:07 am
Location: Astana, Kazakhstan
Contact:

Post by armansuleimenov » Sun Dec 30, 2007 7:43 am

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;
}

dma
New poster
Posts: 8
Joined: Wed Dec 12, 2007 1:05 pm

Post by dma » Sun Dec 30, 2007 7:47 am

sonyckson wrote:"...and the 9999999991 is greater than 2^64!" == FALSE
sorry. you're right. But in C++, long long int seams to be 32-bits.

dma
New poster
Posts: 8
Joined: Wed Dec 12, 2007 1:05 pm

Post by dma » Sun Dec 30, 2007 7:57 am

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;
}
Plz, try to find the exactly maximum of a-b! how about cin the n as string and sort it.

ligregni
New poster
Posts: 11
Joined: Thu Nov 29, 2007 12:41 am
Location: Queretaro, M
Contact:

long long... double... HELP!

Post by ligregni » Sun Dec 30, 2007 8:43 am

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
C: multum in parvo

"a lot since quite few"

http://acmicpc-live-archive.uva.es/nuev ... user=12539

dma
New poster
Posts: 8
Joined: Wed Dec 12, 2007 1:05 pm

Re: long long... double... HELP!

Post by dma » Sun Dec 30, 2007 9:11 am

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
that may be helpful.
http://www.thescripts.com/forum/thread63790.html

Post Reply

Return to “Volume 113 (11300-11399)”