10106 - Product

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

Moderator: Board moderators

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Thu May 27, 2004 2:57 pm

pushpush

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Thu May 27, 2004 5:42 pm

Your TLE stems from input such as
0
1
You'll get WA since input is like:
xxxx[newline]
xxxxxxx[newline]
Note the last newline and what it does to !cin.eof().

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Fri May 28, 2004 1:04 am

but my program can respond to two numbers on two lines correctly... :cry:

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri May 28, 2004 1:15 am

Hrmm, on Linux, a simple file like
0
1
with two newlines will come out as 4 bytes long.

If you're using Windows, find an editor that'll let you save in UNIX format, and then save your file. Make sure it's four bytes (if you input the above). If it's 3, then you have "0[newline]1[EOF]".

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Fri May 28, 2004 6:00 pm

i can save it like
0[newline]1[newline][eof]

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

10106 WA

Post by helmet » Mon Jun 28, 2004 11:03 am

My program gives correct op for all tescases in forum yet WA...

Any more testcases?

Dejected...
Just another brick in the wall...

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Wed Jul 28, 2004 1:52 pm

Hi,

do you mean: how many digits will have 10^250? I didn't understand your question.
kiha

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Wed Jul 28, 2004 3:39 pm

Hello

I've got the same problem. My program works for all test cases I have seen on the board. Despite that I've got WA. Please put more test cases.

With regards
kiha

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm

Post by Andrew Neitsch » Wed Jul 28, 2004 6:32 pm

input:
0
2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222
2
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
9239538994338789151251557336598603050049616822294053424980870425131464466182353830814916071789845042370142421852990439213459450627013510493542232079586565952646636598169299756958773885685805728065441653009173744078838973219505500897158270221204367245
9896336400014021081112872660026786571823539120528457013481728314902092185310581449120208631014862091874106743950514845492688570616578189552019550880999626199354705816824577956144319588556564026758407650715151019940083959555421056787710369504463191742
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

Ouput:
0
19999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998
91437586069023901335141066474711666537718790039237144985051289985350175432524770084824378427555002818097099309346160871667571286412924312245148206827831443006000924957609921550337260262953945785774998477067644833241060308469618958625980383949243282674332743009843156607612702745027529447743579967907340959122060977535403916274356199174936757805300947243257666366727345740624830784342794119256500258114097942703603683608916604350586797991674579535204948315352029368384842883219960490930872682219290790
99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999980000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm

Post by Andrew Neitsch » Wed Jul 28, 2004 6:35 pm

10^250 is a 1 followed by 250 zeroes, so it will have 251 digits. Since that is the limit for your two inputs, the output will be at maximum (10^250)^2=10^500, which has 501 digits.

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Wed Jul 28, 2004 10:38 pm

Hello

how silly copmuters are :[
When I ran my program on your tests, it gave too few numbers in output
[later I realised that when reading from console in Turbo Pascal the
maximum length of a string can be 127 :/]. I thought it is because string
limit [255] is too small -- so in few minutes I changed data type to array
of chars. After few whiles of debugging, I got AC. Nonetheless I don't
understand why it was WA before: does string if Free Pascal [if reading
from console] have maximum length 127 or 255? Ok whatever, I got
AC :D

Thanks anyway ;)
kiha

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm

Post by Andrew Neitsch » Wed Jul 28, 2004 10:48 pm

Reading from console is probably 127 characters; always read from input file. Put the input in a file 10106.in, then do

10106 < 10106.in

There should be no limit on the length of the string; but the console-reading (with gets() or something) has a very small buffer.

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Post by roticv » Sat Dec 11, 2004 9:30 am

Hello

Can someone tell me what is wrong with my code? I tested with the sample test data given here and it was all correct.

[c]#include <stdio.h>
#include <string.h>

char str1[300];
char str2[300];
char final[600];
int i, j, len1, len2, tmp, limit, result;


int main(){
while (scanf("%s %s",str1, str2)!=EOF){
for (i=0; i<600; i++){
final = 0;
}
len1 = strlen(str1);
len2 = strlen(str2);
for (i=0;i<(len1+1)/2;i++){
tmp = str1 - '0';
str1 = str1[len1-i-1] - '0';
str1[len1-i-1] = tmp;
}
for (i=0;i<(len2+1)/2;i++){
tmp = str2 - '0';
str2 = str2[len2-i-1] - '0';
str2[len2-i-1] = tmp;
}
for (i=0;i<len1;i++){
for (j=0;j<len2;j++){
tmp = str2[j] * str1;
final[i+j] += tmp;
final[i+j+1] += final[i+j]/10;
final[i+j] = final[i+j] % 10;
}
}
for (i=300;final==0;i--){
if (i==0){
break;
}
}
for (;i>=0;i--){
printf("%c",final+'0');
}
printf("\n");
}
return 0;
}
[/c]

eyeabhi
New poster
Posts: 11
Joined: Fri Apr 28, 2006 4:16 pm
Location: Bangladesh
Contact:

10106

Post by eyeabhi » Sun May 14, 2006 9:58 pm

Hi,
my code gives proper output in all test cases I tested, but i am getting WA all the time. Plz any one tell me whts wrong, or give me some tricky input. Here's my code

Code: Select all

/*
	Product
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DIGIT 300

/* Adds preceding zero */
void adzero(char *p, int n)
{
	int x;
	for(x = 0; p[x]; x++)
		;
	if(n - x <= 0)
		return;
	else{
		p[n--] = '\0';
		while(x > 0){
			p[n--] = p[x - 1];
			x--;
		}
		while(n >= 0){
			p[n] = '0';
			n--;
		}
		return;
	}
}

/* Removes Preceding Zero From  a Number in STRING Form */
void unzero(char *p)
{
	int i, x;

	for(i = 0; p[i] == '0'; i++)
		;
	for(x = 0; p[x + i]; x++)
		p[x] = p[x + i];
	if(x == 0){
		p[x] = '0';
		p[x + 1] = '\0';
	}
	else
		p[x] = '\0';
	return;
}

/* Calculates Addition of 2 Numbers in the Form of String */
void add(char *p, char *q, char *a)
{
	int x, y, z, t, least;

	for(x = 0; p[x]; x++)
		;
	for(y = 0; q[y]; y++)
		;
	if(x > y){
		adzero(q, x);
		z = x - 1;
	}
	else if(y > x){
		adzero(p, y);
		z = y - 1;
	}
	else if(x == y)
		z = x - 1;
	if(z >= DIGIT){
		printf("\n\tDIGIT OVERFLOW!");
		exit(1);
	}
	t = z;
	least = 0;
	while(z >= 0){
		a[z] = (p[z] - '0' + q[z] - '0' + least) % 10 + '0';
		least = (p[z] - '0' + q[z] - '0' + least) / 10;
		z--;
	}

	if(least == 0)
		a[t + 1] = '\0';
	else{
		if(t + 1 >= DIGIT){
			printf("\n\tDIGIT OVERFLOW!");
			exit(1);
		}
		else{
			a[t + 2] = '\0';
			while(t >= 0){
				a[t + 1] = a[t];
				t--;
			}
			a[0] = least + '0';
		}
	}
	unzero(p);
	unzero(q);
	unzero(a);
	return;
}

/* Multiplies two numbers in string form */
void multiply(char *p, char *q, char *a)
{
	int x, y, z, least, r, s, t;
	char m[DIGIT + 1], o[DIGIT +1];

	a[0] = '0';
   a[1] = '\0';
	for(x = 0; p[x]; x++)
		;
	for(y = 0; q[y]; y++)
		;
	t = x - 1;
	s = y - 1;
	for(y = s; y >= 0; y--){
		z = t + 1;
		least = 0;
		for(x = t; x >= 0; x--){
			m[z] = ((p[x] - '0') * (q[y] - '0') + least) % 10 + '0';
			least = ((p[x] - '0') * (q[y] - '0') + least) / 10;
			z--;
		}
		m[z] = least + '0';
		r = 0;
		while(s - y - r){
			m[t + 2 + r] = '0';
			r++;
		}
		m[t + 2 + r] = '\0';
		add(m, a, o);
		strcpy(a, o);
	}
   return;
}

void main()
{
	char a[DIGIT + 1], b[DIGIT + 1], p[DIGIT + DIGIT];

	while(gets(a) != NULL){
		gets(b);
		unzero(a);
		unzero(b);
		multiply(a, b, p);
		printf("%s\n", p);
	}
}
:cry:

Thanks in advance.
Abhishek Roy
Undergraduate Student,
Department of Computer Science and Engineering,
Bangladesh University of Engineering and Technology, Dhaka.

a123123123888
New poster
Posts: 7
Joined: Fri Mar 31, 2006 1:22 pm

..

Post by a123123123888 » Wed May 17, 2006 2:44 pm

For example,

Code: Select all

   3
   2
Your program print more.

Post Reply

Return to “Volume 101 (10100-10199)”