616 - Coconuts, Revisited

[anupam]

should i count it down to 2 or from 2 to sqrt(..)?
what is the cause for the formula before it?

[Jalal]

Better to from 2 to sqrt(coconut).
coz i did in this way
But can u tell me is it really make any problem to
solve th e problem?

[kelfin]

Why I get "Wrong Answer"? Have anyone help me.

Code: Select all

#include<stdio.h>
#include<math.h>
main()
{
 float coconuts;
 unsigned long temp_c,ok,i,j,max_people;
 while(scanf(" %f",&coconuts)){
  if(coconuts<0) break;
  temp_c=coconuts;   ok=0;
  max_people=(unsigned)pow(coconuts,0.5)+2;
  for(i=max_people;i>1;i--){
   temp_c=coconuts;
   for(j=i;j>0;j--){
    if((temp_c-1)%i==0){
     temp_c=temp_c-(temp_c-1)/i-1;
     ok=1;
    }
    else{
     ok=0;
     break;
    }
   }
   if(ok){
    printf("%.0f coconuts, %lu people and 1 monkey\n",coconuts,i);
    break;
   }
  }
  if(!ok)
   printf("%.0f coconuts, no solution\n",coconuts);
 }
}

[makbet]

If n is the number of people, then
(n^n-n+1) is the number of coconuts. Am I right? And if I am, then why do I get WA? Is the input larger than 2^64-1?

[ec3_limz]

If n is the number of people, then
(n^n-n+1) is the number of coconuts. Am I right? And if I am, then why do I get WA?

The formula n^n-n+1 does not work.

[technobug]

simulate in range sqrt(coconuts)+1 down to 2.

how did you come up with the upper bound? that is always my problem with this type of problem (ugh...)

i tried from coconuts down to 2 and TLE.... so i tried coconuts/2 as upperbound..... still not (although it did not know why....)

anyone can help?

thanks

guilherme

[Heartattack!]

Hey guys, I just got AC after a WA. I thought I'd share a couple of strange things about the problem:
1. Input is terminated with a negative number. You must process 0s.
2. Special case:
Say in the morning there are no coconuts left. The description says that the coconuts left in the morning are divided between all the people and this time there is none left over. Now, look at the following:

Code: Select all

No. of coconuts: 3
No. of people: 2

The first guy wakes up, divides the 3 coconuts into two piles and gives the remaining coconut to the monkey. So, there's only 1 coconut left when the second guy wakes up. He divides the 1 coconut into 2 piles and gives the remaining coconut to the monkey. So there are 0 coconuts left in the morning. In the morning these 0 coconut/s are divided between the 2 people with each person getting 0 coconut/s. 

Logically, this is not a good solution. I think it should be "no solution" in this case. But I thought it might be like this and submitted the problem resulting in an WA. I just took out one condition and got AC. These things are frustrating, I know. That's what this post is for....

[JaviGS]

Hi, what is the output for 1 and 0? Should it be "1 coconut, no solution" or "1 coconuts, no solution"?
Anyway, could anyone give the output for the following numbers?
0
1
2
3
7
253
509
65529
16777209

Thanks in advance!
Javi

[jichen1234]

Output:
0 coconuts, no solution
1 coconuts, no solution
2 coconuts, no solution
3 coconuts, 2 people and 1 monkey
7 coconuts, no solution
253 coconuts, no solution
509 coconuts, no solution
65529 coconuts, no solution
16777209 coconuts, no solution
[/quote]

[Karthekeyan]

Someone help me please....Dunno why i get WA for this code

Code: Select all

removed after getting ac

[Jan]

Test the i/o set...

Input:

Code: Select all

24
36
74
-1

Output:

Code: Select all

24 coconuts, no solution
36 coconuts, no solution
74 coconuts, no solution

Hope it works.

[Karthekeyan]

thanks a lot dude....got it corrected

[IRA]

I don't know why do I got WA!?
Please give me some input and output data to test my program.
Or help me to find the mistake.....Please
Thanks in advance...

Code: Select all

I find my mistake and got Acc...Thanks!

[a123123123888]

Because you have to check the result can be divide by people.

For example, 25.

(25-1)/3=8

so after first person, still 16 coconuts left.

(16-1)/3=5

so after second person, still 10 coconuts left.

and after third person, 6 coconuts left. ----> result

AND,

6 can be divide by 3, so 3 people is right.

if the result can not divide by 3, you should calculate next.

your answer is wrong when input is:

Code: Select all

253
509
65539
16777209

the correct output are all no solution.

[Mushfiqur Rahman]

I am getting WA with this, but I didn't found any wrong. Plese help some body. Here is my code.

Code: Select all

Removed after AC