130 - Roman Roulette

[Morning]

thanx so much

[_.B._]

Greetings!.
Please, correct me if I am wrong, since I've seen different I/O in other posts, and I still get WA :
Input
5 2
7 3
0 0
Output
4
1

If correct, is it because?:

1 2 3 4 5
1 X 3 4 5
1 4 3 5
1 4 3 X
1 3 4
1 X 4
1 4
X 4
4

1 2 3 4 5 6 7
1 2 X 4 5 6 7
1 2 6 4 5 7
1 2 6 4 5 X
1 2 4 5 6
1 2 X 5 6
2 1 5 6
X 1 5 6
6 1 5
X 1 5
1 5
1 X
1

Any critical I/O for this problem??.
Thanks in advance!.

[HerrAachen]

I also get WA on 130. I tried the i/o you gave. It was all correct except from n=100 k=53. My result is 51 there. Has anyone a spontaneous explanation for that?

Herr Aachen

[HerrAachen]

i think you misunderstood the problem. What you do is finding out the sole survivor, but the actual task is to find out the position where the counting should start to let number one be the sole survivor. That's quite a different thing.

Herr Aachen

[_.B._]

Indeed Herr Aachen!.
Thanks!.
Will try to make it that way.
Keep posting!.

[Examiner]

Thanks for your hint. I got accepted.

[sunnycare]

i got WA when i submit prob130

but i got AC when i submit prob 133 151 and 440

they are the same kind of problem ....why?

here is my code ....
who can test my code , and give me some sample ..of course i will test it ,too. thanks...

Code: Select all

//130 Roman roulette
#include <iostream>
using namespace std;
//here i use the struct  when i used in the prob 133 :)
struct dole
{
	int num;
	dole *left;
	dole *right;
};
struct cycle
{
	dole *head;
	int totol;

};
//insert left to the No.1
void insert(dole *p,cycle &c)
{
	if(c.head==NULL)
	{
		c.head=p;
		p->left=p;
		p->right=p;
	}
	else
	{
		p->left=c.head->left;
		p->right=c.head;
		c.head->left->right=p;
		c.head->left=p;
	}
	c.totol++;
}

void del(dole *p,cycle &c)
{
	p->left->right=p->right;
	p->right->left=p->left;
	if(c.head==p)
	{
		if(c.head->left!=p)
			c.head=p->left;
		else
			c.head=NULL;
	}
	delete p;
	c.totol--;
}
void buildCycle(int n,cycle &c)
{
	dole *p;
	int i;
	for(i=1;i<=n;i++)
	{
		p=new dole;
		p->num=i;
		p->left=NULL;
		p->right=NULL;
		insert(p,c);
	}
}
void main()
{
	
	int n,k;
	cin>>n>>k;
	cycle c;
	c.head=NULL;
	c.totol=0;
	dole *p=NULL;
	dole *pre=NULL;
	bool bury=false;
	long i;
	while(n!=0||k!=0)
	{
		
		buildCycle(n,c);
		bury=false;
		p=c.head;
		pre=NULL;
		while(c.totol>1)
		{
			for(i=1;i<k;i++)
			{	
				p=p->right;
			}
			if(!bury)
			{
				
				pre=p->left;
				del(p,c);
				p=pre->right;
			}
			else
			{
				if(p!=pre)
				{
					p->left->right=p->right;
					p->right->left=p->left;
					p->right=pre->right;
					pre->right->left=p;
					p->left=pre;
					pre->right=p;
				}
				p=p->right;
			}
			bury=!bury;
		}
		if(p->num==1)
			cout<<1<<endl;
		else
            cout<<(2+n-p->num)<<endl;
		cin>>n>>k;


	}

}

[Jemerson]

Mine aint working for 100 53 too, i got 51 as answer, in fact i noticed that for the answer 13 be possible the safe place must be 88, printing my array i noticed that the position 88 is getting lost missing just a few steps to the end of the running. This is driving me nuts.

[linux]

Try these inputs:

Code: Select all

Input:
    1 1
    1 5
    5 2
    7 3
    50 9
    100 9
    100 53
    100 5
    5 4
    11 93
    0 0

Output:
1
1
3
1
45
34
13
40
5
2

Your output is different. Hope this helps.

[bdm]

hi all

I think this problem is a simulation problem, and I have solved this problem by "poor" algorithm.

Could anyone share a better method for this problem?

~~~

[Joarder]

Here is my code...
Plz... Someone help me....


/*
* File: 130 - Roman Roulette.cpp
* Tag: Ad Hoc, Simulation
* http://uva.onlinejudge.org/external/1/130.html


* Runtime:
* Author: Shoshi
* Created on November 30, 2011, 4:00 AM
*/

#pragma warning (disable : 4786)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

using namespace std;

int last_standing_item (int n,int k,int j) {
list<int>l;
int i;
for(i=j;i<=n;i++)
l.push_back(i);
for(i=1;i<j;i++)
l.push_back(i);
while(l.size()>1) {
for(i=1;i<=k;i++) {
l.push_back(l.front());
l.pop_front();
}
l.pop_front();
}
return l.front();
}

int main() {
//freopen("130 - Roman Roulette_in.txt", "r", stdin);
int n,k,m,i;
while(cin>>n>>k) {
if(n==0 && k==0)
break;
i=m=0;
while(m!=1) {
i++;
m=last_standing_item(n,k,i);
}
cout<<i<<"\n";
}
return 0;
}