130 - Roman Roulette

[dawynn]

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

[dawynn]

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]

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

[little joey]

Dit you reproduce the sample?
My AC program gives

Code: Select all

40
16
21
45
1
1

on your input.

Good luck.

[de]

I need some test input/output

thanks a lot!!!

[saiqbal]

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]

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]

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]

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

[aakash_mandhar]

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]

[PMNOX]

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]

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]

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

[Morning]

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

[UFP2161]

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