Page 2 of 3
Posted: Wed Oct 08, 2003 11:14 am
by 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]
Posted: Wed Oct 08, 2003 2:25 pm
by Betty
I replaced those lines and still get WA
Posted: Wed Oct 08, 2003 8:38 pm
by Maarten
Posted: Sat Oct 11, 2003 6:56 am
by 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]
Posted: Thu Jan 22, 2004 2:12 am
by 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
133 - The Dole Queue
Posted: Fri Sep 24, 2004 5:44 am
by 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]
133 Dole Queen - Inconsistent!
Posted: Mon Nov 01, 2004 8:20 am
by 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
Posted: Tue Jun 28, 2005 8:41 pm
by 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
Posted: Tue Jun 28, 2005 9:00 pm
by 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
Posted: Mon Jul 04, 2005 2:21 am
by 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?
Help on Runtime Error
Posted: Thu Mar 30, 2006 5:00 pm
by 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.
133 why PE?
Posted: Tue Apr 04, 2006 7:14 am
by 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;
}
Posted: Thu Jun 08, 2006 5:11 am
by Dai Ming
thank you
I got AC
Help~133 The Dole Queue WA
Posted: Fri Sep 29, 2006 2:41 pm
by 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;
}
Posted: Mon Oct 02, 2006 12:32 pm
by catro
can you give me some samples,i can't open *.tgz