10925 - Krakovia

All about problems in Volume 109. 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
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby » Thu Apr 13, 2006 2:35 pm

Yes, I know this just "BigInt arithmetic" problem, but I've end-minded about how to change it... This's actually my first approach on BigInt problem and it's so made me stress... :cry:

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Thu Apr 13, 2006 3:14 pm

It's just a problem, nothing to be stressed about.

Read the code carefully again and again. If you're fed up with it, write a test case generator and get some big tests. You'll have to verify the answers, so write a converter from input data to bc input format and use it as an oracle.

User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby » Sat Apr 15, 2006 5:40 am

OK, I've found my bug and it's in my divide function... any suggestion how to change it? or just the algorithm is ok, I just confused and have no idea how to change it... I implement primary school division algorithm... any tutorial or help please ... :oops:

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Sat Apr 15, 2006 7:47 am

Don't be stress :D

you can use my divide function

Code: Select all

#include <stdio.h>


int Divide(char hasil[],int F,char out[])
{
	int i, j, x;

	x=0; i=0;
	while(hasil[i])
	{
		x *= 10;
		x += hasil[i++]-'0';
		if(x>=F) break;
	}

	j=0;
	do
	{
		if(x>=F)
		{
			out[j++] = (x/F)+'0';
			x = x%F;
		}
		else out[j++]='0';
		if(hasil[i]=='\0') break;
		x *= 10;
		x += hasil[i++]-'0';
	}
	while(1);

	out[j]='\0';
        return x;
}

int main()
{
	char result[10];
	int remainder;
	remainder = Divide("123",7,result);
	printf("result = %s\n",result);
	printf("remainder = %d\n",remainder);
}
"Life is more beautiful with algorithm"

User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby » Sun Apr 16, 2006 6:32 am

Thanx Timo... I'll study that... :)

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Mon Aug 07, 2006 3:27 pm

Jemerson wrote:Input:

Code: Select all

1 16
17432479801732498109834891047810
1 15
17432479801732498109834891047810
This input is not correct as the numbers should be at most 10^20.

abdullah<cse du>
New poster
Posts: 39
Joined: Mon Dec 04, 2006 2:18 pm
Location: Bangladesh(CSE DU)
Contact:

Post by abdullah<cse du> » Wed Jul 04, 2007 9:38 am

Hi all,

I have checked my code with all of the sample input in the board. And get correct ans. But still the program gives wrong ans in UVA. Please help me to locate the bugs in my code.

Code: Select all


/*code has been removed
  after accepted*/

Please help me
Thanks

ABDULLAH
Last edited by abdullah<cse du> on Fri Jul 06, 2007 11:09 am, edited 1 time in total.
We were in past, we are in past and we will go in past.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Jul 04, 2007 5:47 pm

Initialization problem. Initialize upto 'l_max+1'. Hope it helps.
Ami ekhono shopno dekhi...
HomePage

abdullah<cse du>
New poster
Posts: 39
Joined: Mon Dec 04, 2006 2:18 pm
Location: Bangladesh(CSE DU)
Contact:

Post by abdullah<cse du> » Thu Jul 05, 2007 5:18 am

Jan vai,

What do you mean by 'Initialization problem'. I can't understand. Please describe it.

Thanks

ABDULLAH.
We were in past, we are in past and we will go in past.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Jul 05, 2007 5:30 pm

1. Use l_max+1 to initialize (or to call other functions)
2. Check the following part

Code: Select all

      while(carry)
      {
         mod=carry%10;
         add[i]=mod+'0';
         carry/=10;
         i++; // You missed this line
      }
3. Check the output format and change your code.

Hope these help.
Ami ekhono shopno dekhi...
HomePage

abdullah<cse du>
New poster
Posts: 39
Joined: Mon Dec 04, 2006 2:18 pm
Location: Bangladesh(CSE DU)
Contact:

Post by abdullah<cse du> » Fri Jul 06, 2007 4:27 am

Thanks Jan vai, I got accepted.
We were in past, we are in past and we will go in past.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Jul 06, 2007 7:48 am

Remove your code.
Ami ekhono shopno dekhi...
HomePage

rezaeeEE
New poster
Posts: 25
Joined: Fri May 11, 2007 3:45 pm

got wa

Post by rezaeeEE » Sun Sep 16, 2007 12:41 am

i get wa.
can any body find my buge?
i cant find it.

Code: Select all

#include <iostream>
#include <string>

using namespace std;

string sum(string s1, string s2)
{
	string s3;
	int l1 = s1.length();
	int l2 = s2.length();
	int ptr1 = l1 - 1, ptr2 = l2 - 1, q = 0;
	while( ptr1 >= 0 || ptr2 >= 0 )
	{
		if(ptr1 >= 0)
			q += s1[ptr1--] - '0';
		if(ptr2 >= 0)
			q += s2[ptr2--] - '0';
		s3 = (char)( q % 10 + '0') + s3;
		q /= 10;
	}
	while( q )
	{
		s3 = (char)( q % 10 + '0') + s3;
		q /= 10;
	}
	return s3;
}

string div(string s, int n)
{
	string s2;
	int q = 0;
	for(int i = 0;i < s.length();i++)
	{
		q = q * 10 + s[i] - '0';
		s2 += (char)( q / n + '0');
		q = q % n;
	}
	int ptr = 0;
	while(ptr < s2.length() - 1 && s2[ptr] == '0')
		ptr++;
	s2 = s2.substr(ptr, s2.length() - ptr);
	return s2;
}

int main()
{
	int n, f, test = 1;
	while(cin >> n >> f, n || f)
	{
		if( test > 1)
			cout << endl;
		string s1 = "0", s2;
		for(int i = 0;i < n;i++)
		{
			cin >> s2;
			s1 = sum(s1, s2);
		}
		string dv = div(s1, f);
		cout << "Bill #"<<test++<<
				" costs "<<s1<<": each friend should pay "
				<<dv<<endl;
	}
	return 0;
}
thanks

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Sep 20, 2007 8:22 am

Read the description again.
After each test case, you should print a blank line.
You are printing a blank line between cases. Why?
Ami ekhono shopno dekhi...
HomePage

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

10925,WA,ples help

Post by turcse143 » Mon Dec 24, 2007 7:15 pm

This is my sample input-output,i got WA.
ples help,giving some concept or sample input-output
input:
3 3
5400000000
5400000000
5400000000
3 2
5400000000
5400000000
9000000001
0 0
output:
Bill #1 costs 16200000000: each friend should pay 5400000000

Bill #2 costs 19800000001: each friend should pay 9900000000

Press any key to continue

i don't know whats problem?
:(
''I want to be most laziest person in the world''

Post Reply

Return to “Volume 109 (10900-10999)”