## 10774 - Repeated Josephus

Moderator: Board moderators

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:
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
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:
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
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:
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
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

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
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:
I can't tell you what's wrong, because you didn't say whait is it supposed to do Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
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

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

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

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
There is nothing wrong with your code. It is the judge's compiler. See my post in Volume CVII.