133 - The Dole Queue

[Maarten]

just replace

[cpp]
fgets(line,10000,stdin);
line[strlen(line)-1]=0;
sscanf(line,"%d %d %d",&n,&k,&m);
[/cpp]

by

[cpp]
scanf( "%d %d %d\n", &n, &k, &m );
[/cpp]

[Betty]

I replaced those lines and still get WA

[Maarten]

try the input and output at http://contest.mff.cuni.cz/archive/nzl1990a/

[Betty]

hey thanks for those great tests, found my problem really quickly

[cpp]

head=remove(head);
// break;
if(head==p)head=head->next; //<--- had to remove this line, thought I had already
[/cpp]

[El-idioto]

Hey Maarten,

Thanks to your brilliant input (and output!) file I found no less than 3 problems with my implementation.

After our implementations agreed on all the inputs, I submitted and got AC!

Thanks a lot!

Sander

[Akhnukh]

[cpp]

following is my code for The Dole Queue i am getting continuosly WA.. i couldnt find ne mistake in my code...if ne 1 find plzzz help me out... thanx

#include <iostream.h>

class PERSON
{
public:
int person;
PERSON *next;
PERSON *last;

PERSON(int p)
{
person = p;
next=NULL;
last=NULL;
}

};


PERSON *remove(PERSON *p)
{
if(p==NULL)

return NULL;


PERSON *ret = p->next;
if(ret==p)

ret=NULL;
p->last->next=p->next;
p->next->last=p->last;

delete p;
p=NULL;

return ret;
}


PERSON *remove2(PERSON *p){
if(p==NULL)
return NULL;
PERSON *ret = p->last;

if(ret==p)
ret=NULL;

p->last->next=p->next;
p->next->last=p->last;

delete p;
p=NULL;
return ret;
}


int main(){

int n=0,m=0,k=0;
int i;
while(1){

cin>>n>>k>>m;
if((n==k) && (k==m) && (m==0))break;
PERSON *head = NULL;
PERSON *p=NULL;
for(i=0;i<n;i++){
PERSON *q = new PERSON(i+1);
if(head==NULL)head=q;
else{
p->next=q;
q->last=p;
}
p=q;

}
p->next=head;
head->last=p;

bool first = true;
while(1){
for(i=0;i<k-1;i++)
head=head->next;

for(i=0;i<m-1;i++)
p=p->last;

if(!first)
cout<<",";
if(p->person==head->person){

cout<<"\t"<<head->person;
}
else{
cout<<" "<<head->person<<" "<<p->person;
}

if(head==p)p=p->last;
else{
p=remove2(p);
if(head==p)p=p->last;
}

head=remove(head);
if(head==p)head=head->next;

if(head==NULL)break;
first=false;
}
cout<<"\n";
}


return 0;
}



[/cpp]

[KoolKris]

If anyone is having problems solving 133 it might be because the problem solution is inconsistent. First of all problem doesn't say in which direction an official's pointer goes once the person selected has been removed. Once can determine by guessing and checking until the example output is reached. It can be found that the first official

[jaracz]

No, you're a bit wrong
If you misunderstood specification abt this pro please DO NOT post such a stupid comments. You'd better read again or try to write down it on paper if necessity to avoid "inconsistents" like this.
I've read once and understood this at the moment,entire specification 133 sample in/out etc are correct, everything is well and clear explained, and 20/200 aren't related to thing you've mentioned.

Peace

[jaracz]

hmm
I didn't read your entire code, but try to use <stdio.h> header, it would be better to format output than using <iostream>, at the first glance you'll get PE, maybe even WA, try to fix it because '/t' is set to 5 spaces (if i remember well), use printf("%3d...",...); instead of this

[Jan]

I think jaracz is right. And KoolKris you should know that almost 50% of the submissions in this problem are accepted.

Actually the problem description is like this:

Code: Select all

Suppose there are 10 people: 
It means N = 10
                                         4     3
                                      5           2
                                     6              1
                                       7          10 
                                          8    9    
    And one official is counting counter-clockwise like 1, 2, 3, 4 ... and he counts k people and the k-th one is out of the queue
    And the otherone is counting clockwise like 10, 9, 8, 7 ... and he counts m people and the according to him the m-th one goes out.
    If they both get the same man he will be out of the que, otherwise two people will be out of the queue. 
      Now suppose k = 4 and m = 5 ...

  1. The 1st officer counts 1, 2, 3, 4 and 2nd officer counts 10, 9, 8 and so the 4th and the 8th both are out, the 1st officer starts counting from 5 where the 2nd officer starts from 7. Lets look at the queue

                                            3
                                      5         2
                                     6            1
                                       7        10 
                                            9
                                       
  2. The 1st officer counts 5, 6, 7, 9 and 2nd officer counts 7, 6, 5 and so the 9th and the 5th both are out, the 1st officer starts counting from 10 where the 2nd officer starts from 3. Lets look at the queue

                                            3
                                       6        2
                                       7        1
                                           10 
                                            
  3. The 1st officer counts 10, 1, 2, 3 and 2nd officer counts 3, 2, 1 and so the 3rd and the 1st both are out, the 1st officer starts counting from 6 where the 2nd officer starts from 10. Lets look at the queue

                                        6   2
                                       7     10 

  4. The 1st officer counts 6, 7, 10, 2 and 2nd officer counts 10, 7, 6 and so the 2nd and the 6th both are out, the 1st officer starts counting from 7 where the 2nd officer starts from 10. Lets look at the queue

                                        7    10
 
  5. The 1st officer counts 7, 10, 7, 10 and 2nd officer counts 10, 7, 10 and so 10th one is out, then both start from 7. And finally 7th one is out.

 6. And finally print them accordingly.

Actually this is the problem. Not so tough, is it?

[lovexinxin]

When solving problem 133, I tried every test case I can think out and the test case in the board.It's OK.But I always get Runtime error in submit.I want to know if there is some way that I can find the exact reason of the RTE,such as array overflaw. Does the judge provide such information?
I submit my code through the web page.

[lovexinxin]

In the sample output of 133,why there is only one space in front of 10?I think there should be two spaces here and my solution make two spaces but got a PE. Is there some one know why.Thank you.
Here is my code
#include <iostream>
#include <vector>
#include <list>

using namespace std;

int main()
{

int n,k,m;
list<int> l;
list<int>::iterator ptrk,ptrm; //used as pointers of k and m

int cn; //count the number of the people left
int tmpk,tmpm; //two victims of every stage
cin>>n>>k>>m;
while( n > 0)
{
l.clear(); //initilize the list of person
l.push_back(-1);
for(int i = 1;i<=n;++i)
{
l.push_back(i);
}
l.push_back(-1); //end of the list
ptrk = l.begin(); //move the two pointers to the right place
ptrk++;
ptrm = l.end();
ptrm--;
ptrm--;

while(n>0)//still person in the list
{
int ck = k;
int cm = m;

while(--ck!=0)
{
ptrk++;
if((*ptrk) == -1) //to the end of the list
{
ptrk = ++l.begin();
}

}
tmpk = (*ptrk); //get the victim
cout<<" "<<tmpk;


while(--cm!=0)
{
ptrm--;
if(*ptrm == -1) //to the begin of the list
{
ptrm = --l.end();
ptrm --;
}

}
tmpm = (*ptrm);
if(tmpk!=tmpm)//two victims
{
cout<<" "<<(*ptrm);
n-=2;
}
else
n-=1;

if(n != 0)
cout<<",";

ptrk++;
if(*ptrk == tmpm)
ptrk++;

ptrm--;
if(*ptrm == tmpk)
ptrm--;
l.remove(tmpk);//remove the two victims
l.remove(tmpm);

if(*ptrk == -1) //to the end
{
ptrk = ++l.begin();
}
if(*ptrm == -1)//to the head
{
ptrm = --l.end();
ptrm--;
}
}
cout<<endl;


cin>>n>>k>>m;
}
return 0;
}

[Dai Ming]

thank you
I got AC

[catro]

I get WA and don't know why?
Here's my code:
#include <iostream>
#include <cstdio>
using namespace std;
#define down -1
#define up 1
int stat[20];
int n=1;

void correct(int *a)
{
if(*a>=n) *a-=n;
if(*a<0) *a+=n;
}

int counter(int start,int interval,int type)
{
int pos=start;
for(int count=0;count<interval-1;count++)
{
pos+=type;
correct(&pos);
while(stat[pos])
{
pos+=type;
correct(&pos);
}
}
return pos;
}


int main()
{
int left,i,k,m,temp1,temp2,pos1,pos2;
while(cin>>n>>k>>m&&(n||k||m))
{
for(i=0;i<20;i++) stat=0;
pos1=0;
pos2=n-1;
left=n;
while(true)
{
temp1=counter(pos1,k,up);
temp2=counter(pos2,m,down);
stat[temp1]=stat[temp2]=1;

if(left!=n) printf(",");
printf("%3d",temp1+1);
if(temp1!=temp2)
{
left--;
printf("%3d",temp2+1);
}

left--;

pos1=temp1+1;
pos2=temp2-1;

if(left<1) break;

while(stat[pos1])
{
pos1++;
correct(&pos1);
}

while(stat[pos2])
{
pos2--;
correct(&pos2);
}
}
cout<<endl;
}
return 0;
}

[catro]

can you give me some samples,i can't open *.tgz