10774 - Repeated Josephus

[Gaolious]

Well the code you posted and ryan posted differs in output. My code produces the output exactly that ryan gave.

Btw galious, how is input for 3 a length of 1 . For n=3 my output is 0 3. For n=1 my output is 0 1. Your output is 1 1.

In problem it is stated that after the elimination round.For n=2 it is 1 1.

My mistake when convert to PHP language
sorry^^;;

[temper_3243]

Please tell me what is wrong with this code. Please do post me the output/zip for 1 to 31000 to temper_3243@yahoo.com

It gives the exact output for the test cases given by you.

Code: Select all

#include<iostream>
#include<map>
#include<cstdio>

using namespace std;

map < int, int >m;
map < int, int >h;

inline int
myg (int r)
{
  if (m.count (r) == 0){
      int ans, tmp = 1;
      while (r >= tmp)
	{
	  tmp = tmp * 2;
	}
      tmp = tmp / 2;
      ans = r - tmp;
      ans = (2 * ans) + 1;
      m[r] = ans;
      return m[r];
    }
  else
    return m[r];
}

inline int
compute (int n)
{
  if (m.count (n) == 1 && m[n] == n)
    return n;
  else
    {
      m[n] = myg (n);
      return m[n];
    }
}

int
main ()
{
  int a,i, z,n,no;

	for(i=1;i<=35000;i++)
	z=compute(i);

scanf("%d",&no);

for(i=1;i<=no;i++)
{
  scanf (" %d", &a);
	n=a;


	int len=0;

	while(m[n]!=n)
	{
		len++;
		n=m[n];
	}

  printf ("Case %d: %d %d\n",i, len, n);
}
  return 0;
}

[Ryan Pai]

I ran the code you posted against all possible inputs and it agreed with mine (I modified it so that it was in it's own function and then compared the output of that function with the output of mine). So I would assume that the error would be in your input/output. I typically use cin/cout so I can't be sure, but should there be a space in your scanf string?

[temper_3243]

That space is not required. Can you run it without the space in scanf.

Also i don't understand what you said by running it inside a function . What does that mean ? Please post some example.

Well thanks ryan and others for the help.

Best Regards

[Ryan Pai]

I basically did this

Code: Select all

pair<int,int> yours(int n){
  // I put the main part of your code here, but took out the scanf
  return make_pair(len,n); //and did this instead of printf
}

pair<int,int> mine(int n){
  // my code here
}

int main(){
  for(int i=1;i<N;i++)
    if(yours(i)!=mine(i)){
      cout<<"Oh pants, we don't agree on "<<i<<'\n';
      return 1;
    }
  cout<<"Everything checks out\n";
}

And it gave the all good message.

[temper_3243]

I tried running it after removing the space. It is giving me the wrong answer.
Just run this program and save the output in a file.
Run my code and your program for the same input. Diff it tell me where it fails .

Btw is your code accepted

Code: Select all

#include<stdio.h>
int main()
{
	int i;
	for(i=0;i<31000;i++)
		printf("%d\n",i);
	return 0;
}

[temper_3243]

Hi,
I am getting same output as others who have the accepted solution. This code is behaving strangely. Where is it going wrong ?

Code: Select all

#include<iostream>
#include<map>
#include<cstdio>

using namespace std;

map < int, int >m;
map < int, int >h;

inline int
myg (int r)
{
  if (m.count (r) == 0){
      int ans, tmp = 1;
      while (r >= tmp)
   {
     tmp = tmp * 2;
   }
      tmp = tmp / 2;
      ans = r - tmp;
      ans = (2 * ans) + 1;
      m[r] = ans;
      return m[r];
    }
  else
    return m[r];
}

inline int
compute (int n)
{
  if (m.count (n) == 1 && m[n] == n)
    return n;
  else
    {
      m[n] = myg (n);
      return m[n];
    }
}

int
main ()
{
  int a,i, z,n,no;

   for(i=1;i<=35000;i++)
   z=compute(i);

scanf("%d",&no);

for(i=1;i<=no;i++)
{
  scanf (" %d", &a);
   n=a;


   int len=0;

   while(m[n]!=n)
   {
      len++;
      n=m[n];
   }

  printf ("Case %d: %d %d\n",i, len, n);
}
  return 0;
} 

[N|N0]

I can't tell you what's wrong, because you didn't say whait is it supposed to do

[Ryan Pai]

Well, I ran your code and mine on every input the diff said they were exactly the same (and my code got AC).

This is a really odd situation.

[temper_3243]

It is the repeated josehpus problem .
http://online-judge.uva.es/board/viewtopic.php?t=8298

[chunyi81]

Did u use online submission or e-mail? Sometimes submitting via e-mail can cause problems.

[temper_3243]

I used online submission. Why don't the admins comment anything about this problem ?

[temper_3243]

Whats happening with this i don't know? Is there a problem with submit.php ?
is there any other way. I tried copying my code into the text box and even sending it by browse.

Well ryan if you don't mind please send me your code to temper_3243@yahoo.com

[chunyi81]

Hi temper_3243. I checked the outputs from your code inputs 1 to 30000 against my AC code, which I got AC a few minutes ago.

Your code fails for the following test case:

Input:

1
1

Correct Output:

Case 1: 0 1

Your Program Output:

Case 1: 1 0

I have also removed the space in the scanf when I compiled your code.
In fact, your code gives the following output for input 1 to 30000

Case 1: 1 0
Case 2: 1 0

Cases 3 to 30000 also give 1 0.

The environment I ran your code with is g++ 2.95 in Unix, which is similar to UVA online judge environment.

I have tried to debug your code and found one line that could be a problem.

What I can tell you is that I inserted printfs in the compute method and myg method in your code and I got something very interesting.

At the beginning of the myg method

Code: Select all

printf("myg %d %d\n",r,m.count(r));

and at the beginning of the compute method

Code: Select all

printf("compute %d %d\n",n,m.count(n));

For each n, m.count(n) = 0 is correct. But for each r, m.count(r) = 1. This should not be so.

This is a problem with the judge's compiler.

When I compiled your code with g++ 3.3.1 under Dev C++ 4.9.9.1 in Windows wthout the printfs I added and ran it with the same set of inputs and I got your program's output to be the same as from my AC program's output.

[chunyi81]

There is nothing wrong with your code. It is the judge's compiler. See my post in Volume CVII.