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

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

Post by cytmike »

pushpush

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

Post by UFP2161 »

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().

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

Post by cytmike »

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

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

Post by UFP2161 »

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]".

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

Post by cytmike »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

For example,

Code: Select all

   3
   2
Your program print more.

Post Reply

Return to “Volume 101 (10100-10199)”