130 - Roman Roulette

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

Moderator: Board moderators

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning »

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

Post by _.B._ »

Greetings!.
Please, correct me if I am wrong, since I've seen different I/O in other posts, and I still get WA :o :
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
New poster
Posts: 12
Joined: Sat Apr 03, 2004 11:01 pm

Post by 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
New poster
Posts: 12
Joined: Sat Apr 03, 2004 11:01 pm

Post by 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._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Ouch!.

Post by _.B._ »

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

Post by Examiner »

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

Post by 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
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post by 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
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

Re: problem 130 WA need some sample

Post by 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.
Solving for fun..

bdm
New poster
Posts: 1
Joined: Wed Oct 21, 2009 2:28 pm

130 faster method

Post by bdm »

hi all

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

Could anyone share a better method for this problem?

:D ~~~

Joarder
New poster
Posts: 3
Joined: Mon Nov 28, 2011 11:26 pm

130 - Roman Roulette getting WA!!!!

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

Post Reply

Return to “Volume 1 (100-199)”