10079 - Pizza Cutting

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

Moderator: Board moderators

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

HI~

Post by 10153EN » Fri May 17, 2002 11:19 am

I have just thought of a possible reason, will there be value overflow?

Hope can help~

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Location: BANGLADESH
Contact:

WA

Post by Jalal » Thu Jun 13, 2002 4:08 am

THen wt about this?
here is again WA! :(



#include<stdio.h>

void main()
{
long x;

for(;scanf("%ld", &x) && x>=0; )
{
long i, a=0;


for(i=x;i>0;--i)
{
a= i + a;
}

printf("%ld\n",a+1);

}
}

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » Thu Jun 13, 2002 4:22 am

The same problem exists.

In C, int and long is the same. try use long long

scari
New poster
Posts: 1
Joined: Wed Oct 16, 2002 10:11 pm

are you sure?

Post by scari » Wed Oct 16, 2002 10:32 pm

Are you guys sure to the solution is like that?

Yeah. I think so.
But my solution couldn't accepted. It return "Wrong Answer".

I guess, we must find a different solutions.
Here my whole solution.
Forgive my poor code.

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

#define MAX_DIGIT 100

char *
order (char *reversed)
{
int first = 0;
int last = strlen (reversed) - 1;
char temp = 0;

if (reversed[last] == '0')
{
reversed[last] = '\0';
--last;
}

for (; first <= last; ++first, --last)
{
temp = reversed[first];
reversed[first] = reversed[last];
reversed[last] = temp;
}

return reversed;
}

char *
add (const char *l, const char *r, char *sum)
{
int carry = 0;
int digit_sum = 0;
int idx = 0;

int l_len = strlen (l) - 1;
int r_len = strlen (r) - 1;

if (l_len <= r_len)
{
for (; l_len >= 0; --l_len, --r_len)
{
digit_sum = (l[l_len]-'0') + (r[r_len]-'0') + carry; // int
carry = 0;
if (digit_sum >= 10)
{
carry = 1;
digit_sum %= 10;
}
sum[idx++] = (digit_sum + '0'); // char
}
for (; r_len >= 0; --r_len)
sum[idx++] = r[r_len];
}

else
{
for (; r_len >= 0; --r_len, --l_len)
{
digit_sum = (l[l_len]-'0') + (r[r_len]-'0') + carry; // int
carry = 0;
if (digit_sum >= 10)
{
carry = 1;
digit_sum %= 10;
}
sum[idx++] = (digit_sum + '0'); // char
}
for (; l_len >= 0; --l_len)
sum[idx++] = l[l_len];
}

sum[idx] = '\0';
order (sum);

return sum;
}

char *
multiply (const char *l, const char *r, char *multiple)
{
int carry = 0;
int digit_multi = 0;
int idx = 0;
int i = 0;
int step = 0;

int l_len = strlen (l) - 1;
int r_len = strlen (r) - 1;

for (; l_len >= 0; --l_len, ++step)
{
for (idx = step, i = r_len; i >= 0; --i)
{
digit_multi = ((l[l_len] - '0') * (r[i] - '0')) + carry;
if (multiple[idx] != 0)
digit_multi += (multiple[idx] - '0');

carry = 0;
if (digit_multi >= 10)
{
carry = digit_multi / 10;
digit_multi %= 10;
}
multiple[idx++] = (digit_multi + '0');
}
multiple[idx++] = carry + '0';
carry = 0;
}

multiple[idx] = '\0';
order (multiple);

return multiple;
}

int
main (void)
{
long long n = 0;
//int i = 0;
char cut[MAX_DIGIT] = { 0, };
char sum[MAX_DIGIT] = { 0, };
char div[MAX_DIGIT] = { 0, };
char pices[MAX_DIGIT];
memset (pices, 0, MAX_DIGIT);

while (1)
{
scanf ("%lld", &n);
//fgets (cut, MAX_DIGIT, stdin);

if (n < 0)
return 0;
// if (cut[0] == '-')
// return 0;
/*
for (; i < MAX_DIGIT; i++)
if (!isdigit (cut[i]))
{
cut[i] = '\0';
break;
}

n = strtoul (cut, (char **) NULL, 10);
*/
sprintf (cut, "%lld", n);
sprintf (div, "%lld", n / 2);

add (cut, "1", sum);
multiply (sum, div, pices);

if (n % 2 != 0)
{
sprintf (sum, "%lld", ((n + 1) / 2));
strcpy (div, pices); // div as temp
add (div, sum, pices);
}

strcpy (div, pices); // div as temp
add (div, "1", pices);

printf ("%s\n", pices);
memset (pices, 0, MAX_DIGIT);
}

return 0;
}
--------------------------------------------------------------------------------------
oooops! There are no way to indenting my code?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Oct 17, 2002 8:10 am

use

Code: Select all

 and 
marks to indent code ... in other way it's unreadable ....

Dominik

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

10079

Post by Red Scorpion » Thu Dec 12, 2002 8:12 am

:P
Hi, I am trying to solve problem 10079, and got failed.

I use this method :

for n=an, MAX = bn
n=0 , MAX = 0
n=1, MAX = 2
n=2, MAX = 4 (2 + 2 )
n=3, MAX = 7 (4 + 3 )
n=4, MAX = 11 (7 + 4)
n=5, MAX=16 (11 + 5)
n=6, MAX=22 (b(n-1) + an)
n=7, MAX=29
n=8, MAX=37
n=9, MAX=46
n=10, MAX=56

... and so forth (and the number will be very huge)

If Anyone have time, Please tell me what wrong with this method ?

Thanks.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Dec 13, 2002 10:44 am

Do you got overflow problem?

For 210000000, the answer is 22050000105000001
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Problem : Pizza Cutting

Post by Red Scorpion » Sat Dec 14, 2002 4:42 am

No, I don't got Overflow,
and my result for 210.000.000 is :
22050000105000001. I use type : string (not integer) to stor my value, but still got WA, can you give me some sample input that 'cause WA?

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Sat Dec 14, 2002 7:51 am

You have a little bug. You can't get 0 parts of the plane. But you say that when n=0 you divide plane into 0 parts. That's buggy. :wink:

Good luck.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Dec 14, 2002 12:11 pm

Also, you don't need string math to do this problem, a 64 bit number is enough.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Problem Pizza Cutting

Post by Red Scorpion » Mon Dec 16, 2002 7:52 am

Oh, yes I have missed some description.
(for n=0, the output should be 1).

Thanks very much, Now I got accepted.

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Thu Dec 19, 2002 10:19 am

That's not enough to use long int - you should use long long int or long double. :wink:

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Problem 10079

Post by Red Scorpion » Mon Dec 23, 2002 7:30 am

Try This test cases :

input :
0
1
7
210000000

output :
1
2
29
22050000105000001

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Thu Jan 02, 2003 8:22 pm

to tanzim, if you haven't got it ac yet

I've improve your code , try this


[c]

#include "stdio.h"



void main ()
{
long long n;

while (scanf ("%lld",&n))
{
if (n<0) break;
if (n&1) printf ("%lld\n",((n*n)/2) + (n/2) + 2);
else
printf ("%lld\n",((n*n)/2) + (n/2) + 1);

}
}


[/c]

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Thu Feb 13, 2003 1:30 pm

Larry wrote:Also, you don't need string math to do this problem, a 64 bit number is enough.
How to use a 64 bit number? Can you teach me? thanks a lot!!

Post Reply

Return to “Volume 100 (10000-10099)”