10079 - Pizza Cutting

[10153EN]

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

Hope can help~

[Jalal]

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]

The same problem exists.

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

[scari]

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]

use

Code: Select all

 and 

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

Dominik

[Red Scorpion]

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.

[..]

Do you got overflow problem?

For 210000000, the answer is 22050000105000001

[Red Scorpion]

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]

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]

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

[Red Scorpion]

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

Thanks very much, Now I got accepted.

[Andrey Mokhov]

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

[Red Scorpion]

Try This test cases :

input :
0
1
7
210000000

output :
1
2
29
22050000105000001

[deddy one]

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]

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