130 - Roman Roulette

Moderator: Board moderators

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
thanx so much
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

130 > Roman Roulette

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??.
_.
HerrAachen
New poster
Posts: 12
Joined: Sat Apr 03, 2004 11:01 pm
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
New poster
Posts: 12
Joined: Sat Apr 03, 2004 11:01 pm
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._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Ouch!.

Indeed Herr Aachen!.
Thanks!.
Will try to make it that way.
Keep posting!.
_.
Examiner
New poster
Posts: 28
Joined: Thu Feb 19, 2004 1:19 pm
Thanks for your hint. I got accepted.
sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

problem 130 WA need some sample

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
{
int totol;

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

void del(dole *p,cycle &c)
{
p->left->right=p->right;
p->right->left=p->left;
{
else
}
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.totol=0;
dole *p=NULL;
dole *pre=NULL;
bool bury=false;
long i;
while(n!=0||k!=0)
{

buildCycle(n,c);
bury=false;
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
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:
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
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

Re: problem 130 WA need some sample

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.
Solving for fun..
bdm
New poster
Posts: 1
Joined: Wed Oct 21, 2009 2:28 pm

130 faster method

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
New poster
Posts: 3
Joined: Mon Nov 28, 2011 11:26 pm

130 - Roman Roulette getting WA!!!!

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

/*
* File: 130 - Roman Roulette.cpp
* 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;
}