## 10079 - Pizza Cutting

Moderator: Board moderators

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

### HI~

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
Contact:

### WA

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:
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?

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

multiply (sum, div, pices);

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

strcpy (div, pices); // div as temp

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

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
Do you got overflow problem?

For 210000000, the answer is 22050000105000001
My signature:
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

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

Good luck.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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

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
That's not enough to use long int - you should use long long int or long double.

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

### Problem 10079

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

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
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!!