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

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

130: WA

Post by dawynn » Fri Aug 16, 2002 4:25 pm

OK, I briefly gave a description of how this might be solved in the combined 130 / 131 list but since that topic is mostly dominated by 131, I'm creating the new topic.

First, let me say that the example data should have been reserved as some of the tricky data. I would have failed with my original attempt on this data, but since there is only one person in each test case, it's a no-brainer as to where the counting needs to start.

Here's a few other test cases I came up with, two of them inspired by the text. Feel free to work these out with pen and paper to see if my data is correct:

Input:
7 3
5 2
41 3

Output:
1
3
3

Now, here's my code, see if you can spot any issues. If possible, supply examples that can "break" my code:
// this part edited out //
Last edited by dawynn on Sat Aug 17, 2002 4:39 am, edited 1 time in total.

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

Post by dawynn » Sat Aug 17, 2002 4:39 am

Never mind. Got it figured out. Basically, I need to make sure not to count the guy that got killed when I'm looking for his replacement.

David

kurnia w
New poster
Posts: 18
Joined: Fri Dec 06, 2002 3:53 pm
Location: Indonesia
Contact:

130 - Roman Roulette

Post by kurnia w » Fri Mar 14, 2003 5:26 am

can someone give me critical input for this problem ??
i'm can't figure out what's wrong with my code...
my code give I/O like this:
input:
100 5
50 1
70 4
50 9
7 3
1 0
0 0

output:
47
50
6
48
4
1
please correct me if wrong...thank's...

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Mar 14, 2003 8:48 am

Dit you reproduce the sample?
My AC program gives

Code: Select all

40
16
21
45
1
1
on your input.

Good luck.

de
New poster
Posts: 11
Joined: Sat Mar 08, 2003 3:46 pm

130

Post by de » Sun Mar 16, 2003 6:28 pm

I need some test input/output

thanks a lot!!!

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Mon Mar 17, 2003 8:56 pm

try the following i/o

Code: Select all

input:

1 1
1 5
5 2
100 53
100 2
5 4
11 93

output:
1
1
3
13
83
5
2
hope this helps :)

-sohel

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

130 - Roman Roulette (WA)

Post by ec3_limz » Wed Mar 26, 2003 5:24 pm

I don't know what's wrong with this code. Please help.

[cpp]#include <stdio.h>
#include <string.h>

bool occ[100];
int nguy, die;

void sim() {
bool bury;
int count, left, last, i;

bury = false, count = 0, left = nguy;
for (i = 0; left > 1; i = (i + 1) % nguy) {
if (occ)
count++;
if (count >= die) {
occ = false;
if (bury)
occ[last] = true;
else
last = i, left--;
i = (i + nguy - 1) % nguy;
bury = !bury;
}
}
}

void output() {
int i;

for (i = 0; i < nguy; i++)
if (occ) {
printf("%d\n", i + 1);
break;
}
}

int main() {
#ifndef ONLINE_JUDGE
freopen("input.dat", "r", stdin);
freopen("output.dat", "w", stdout);
#endif

while (true) {
scanf("%d%d", &nguy, &die);
if (nguy + die == 0)
break;

memset(occ, -1, sizeof(occ));
sim();
output();
}

return 0;
}
[/cpp]

afonsocsc
New poster
Posts: 34
Joined: Mon Mar 24, 2003 1:15 am
Location: Portugal, Lisbon

Post by afonsocsc » Tue Apr 01, 2003 12:52 pm

In the problem, they give an example, where when n = 5 and k = 2, the output should be 3, but your code gives 1.
The guy that goes to bury, returns right away to the position of the victim, and you should find the best start position so that the first guy in the circle survives, I don't think you are doing that.

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

Post by ec3_limz » Tue Apr 08, 2003 12:07 pm

Thanks, I got Accepted with your help. Apparently I misunderstood the problem.

aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

130: Why WA Need Help plzzzzzz....

Post by aakash_mandhar » Sun Dec 28, 2003 9:02 pm

Why WA... i have used linked list

[cpp]
/* @JUDGE_ID: 40270EF 130 C++ "No special algo:)" */

# include<iostream.h>

struct person
{
struct person *l;
struct person *r;
int n;
}*first=NULL,*temp=NULL;

void insertfront(int n)
{
struct person *a=new person;
a->n=n;
a->l=NULL;
a->r=NULL;
if(first==NULL) {
first=a;
a->l=a;
a->r=a;
}
else
{
a->l=first->l;
first->l->r=a;
first->l=a;
a->r=first;
}

}


int main()
{
int n,i,k,count;
while(1)
{
cin>>n;
cin>>k;
if(n==0 && k==0) break;
for(i=1;i<=n;i++)
{
insertfront(i);
}
first=first->r;
while(first->r!=first)
{
count=k;
while(--count) {first=first->r;}
temp=first;
first=first->r;
temp->l->r=first;
first->l=temp->l;
delete temp;
}
cout<<first->n<<"\n";
delete first;
first=NULL;
}
return 1;
}

//@end_of_source_code

[/cpp]
...I was born to code...

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

problem 130

Post by PMNOX » Thu Jan 29, 2004 12:21 am

i completly don't understand this problem.
In case n = 5 k = 2 i =1
Why the order is 2,5,3,1?
Should it be 2,4,1,5 ?

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Thu Jan 29, 2004 1:31 am

We then proceed to count a further k people in a clockwise direction, starting with the person immediately to the left of the victim. The person number k so selected has the job of burying the victim, and then returning to the position in the circle that the victim had previously occupied.

4 is the one who buries 2.. not who is killed.[/quote]

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

Post by PMNOX » Thu Jan 29, 2004 10:26 am

thx, i now i understand it after a few months of trying :)

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

130 Roman Roulet:I don't understand the problem

Post by Morning » Fri Feb 06, 2004 3:44 pm

when n = 5, and k = 2, and i = 1,
2 died<-3 take the position
5 died<-1 take the position
4 died<-1 take the position(but the article says that it should be 3 who died,why??)
3 died
"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

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri Feb 06, 2004 11:08 pm

1 2 3 4 5 [2 is selected, then count 2 more, 3 and 4.. 4 buries, replaces]
1 4 3 5 [start from 3.. 3 and 5.. 5 is selected, 1, 4.. 4 buries, replaces]
1 3 4 [start from 1.. 1 and 3.. 3 is selected, 4, 1.. 1 buries, replaces]
1 4 [start from 4.. 4 and 1, 1 is selected, 4, 4.. 4 buries, replaces]
4

Post Reply

Return to “Volume 1 (100-199)”