10774 - Repeated Josephus

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

Moderator: Board moderators

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

Post by Gaolious » Tue Jun 14, 2005 10:12 am

temper_3243 wrote: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
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Tue Jun 14, 2005 3:37 pm

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
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Wed Jun 15, 2005 9:32 am

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?
I'm always willing to help, if you do the same.

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Wed Jun 15, 2005 1:38 pm

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
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Wed Jun 15, 2005 3:29 pm

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.
I'm always willing to help, if you do the same.

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Wed Jun 15, 2005 5:14 pm

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
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Strange code

Post by temper_3243 » Wed Jun 15, 2005 5:16 pm

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

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Wed Jun 15, 2005 8:59 pm

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

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Thu Jun 16, 2005 2:20 am

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.
I'm always willing to help, if you do the same.

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

See this thread

Post by temper_3243 » Thu Jun 16, 2005 7:12 am

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

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Thu Jun 16, 2005 7:34 am

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

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Thu Jun 16, 2005 5:10 pm

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

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Thu Jun 16, 2005 5:12 pm

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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Fri Jun 17, 2005 6:54 am

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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Fri Jun 17, 2005 9:21 am

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

Post Reply

Return to “Volume 107 (10700-10799)”