133 - The Dole Queue

[paulhryu]

I don't get it! I am doing 133, Dole Queue, and I get it to work and all with the test case, but what's wrong with the code? It doesn't get accepted. (WA)

// @BEGIN_OF_SOURCE_CODE

/* @JUDGE_ID: 17243NT 133 C++ "Brute Force" */

// Send to judge@uva.es

#include <stdio.h>

int eeny[110];
int napplic, ntotal;
int ccw, cw;
int ncw, nccw;
int xcw, xccw;

#define swap(i,j) {int t = i; i = j; j = t;}

bool matchend();
void getnext();

int main() {
int i, j;
bool first;

while(3 == scanf("%d %d %d", &ntotal, &ccw, &cw)) {
if(ntotal == 0 || cw == 0 || ccw == 0) break;

napplic = ntotal;
for(i = 0; i < napplic; i++)
eeny = i + 1;

xccw = 1;
xcw = napplic;
first = true;

while(napplic > 0) {
getnext();

if(!first) printf(",");
else first = false;

printf("%3d", eeny[nccw]);
if(nccw != ncw) {
printf(",%3d", eeny[ncw]);
}

for(i = 0, j = 0; i < napplic; i++) {
if(i != nccw && i != ncw) eeny[j++] = eeny;
}

napplic = j;
}

printf("n");
}

return 0;
}

void getnext() {
int a, b;

for(a = 0; a < napplic; a++)
if(eeny[a] == xccw) break;

for(b = 0; b < napplic; b++)
if(eeny == xcw) break;

nccw = (a + ccw - 1) % napplic;
xccw = eeny[(a + ccw) % napplic];
ncw = (cw * napplic + b - cw + 1) % napplic;
xcw = eeny[(cw * napplic + b - cw) % napplic];
}


// @END_OF_SOURCE_CODE

[Lawrence]

Man, look again on the output specification, you aren't asked to put a "," between the two numbers.

[paulhryu]

It still doesn't work

// @BEGIN_OF_SOURCE_CODE

/* @JUDGE_ID: 17243NT 133 C++ "Brute Force" */

// Send to judge@uva.es

#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>

#ifdef ONLINE_JUDGE
#define ins cin
#define outs cout
#else
#define ins fin
#define outs fout
ifstream fin("myprog.in");
ofstream fout("myprog.out");
#endif

int eeny[110];
int napplic, ntotal;
int ccw, cw;
int ncw, nccw;
int xcw, xccw;

#define swap(i,j) {int t = i; i = j; j = t;}

bool matchend();
void getnext();

int main() {
int i, j;
bool first;

while(ins >> ntotal >> ccw >> cw) {
if(ntotal == 0 || cw == 0 || ccw == 0) break;

napplic = ntotal;
for(i = 0; i < napplic; i++)
eeny = i + 1;

xccw = 1;
xcw = napplic;
first = true;

while(napplic > 0) {
getnext();

if(!first) cout << ",";
else first = false;

cout << setw(3) << eeny[nccw];
if(nccw != ncw)
cout << setw(3) << eeny[ncw];

for(i = 0, j = 0; i < napplic; i++) {
if(i != nccw && i != ncw) eeny[j++] = eeny;
}

napplic = j;
}

cout << endl;
}

return 0;
}

void getnext() {
int a, b;

for(a = 0; a < napplic; a++)
if(eeny[a] == xccw) break;

for(b = 0; b < napplic; b++)
if(eeny == xcw) break;

nccw = (a + ccw - 1) % napplic;
xccw = eeny[(a + ccw) % napplic];
ncw = (cw * napplic + b - cw + 1) % napplic;
xcw = eeny[(cw * napplic + b - cw) % napplic];
}

// @END_OF_SOURCE_CODE

[paulhryu]

Never mind, all I needed was just two more if statements!

[DemonCris]

I got WA >"< ... The following is my source code .. can someone help me.

---

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>


typedef struct node pnode;

struct node {
int mark;
pnode *left;
pnode *right;
};

int cclock, clck, num;
pnode *lft, *rht;


pnode *install(int num)
{
pnode *p = (pnode *)malloc(sizeof(pnode));

p->mark = num;
p->left = p->right = NULL;

return p;
}

int initial()
{
int i;
pnode *p;


lft = install(1);

for (i=2, p=lft; i<=num-1; i++) {
p->left = install(i);
p->left->right = p;
p = p->left;
}

p->left = install(i);
p->left->right = p;
p->left->left = lft;
lft->right = p->left;
rht = lft->right;
}

int delete(pnode *p)
{
p->right->left = p->left;
p->left->right = p->right;

free(p);
}

void operation()
{
pnode *p, *q, *prep, *preq;
int i;


prep = lft; preq = rht;

while (num>0) {

for (i=1, p=prep; i<cclock; i++)
p = p->left;
prep = p->left;

for (i=1, q=preq; i<clck; i++)
q = q->right;
preq = q->right;


if (prep==q) prep = prep->left;
if (preq==p) preq = preq->right;

if (p!=q) {
num -= 2;
if (num!=0)
printf("%3d%3d,", p->mark, q->mark);
else
printf("%3d%3dn", p->mark, q->mark);
delete(p);delete(q);
}
else {
num--;
if (num!=0)
printf("%3d,", p->mark);
else
printf("%3dn", p->mark);
delete(p);
}
}
}

int main()
{
#ifndef ONLINE_JUDGE
close (0); open ("in", O_RDONLY);
close (1); open ("out", O_WRONLY | O_CREAT, 0600);
#endif

while (scanf("%d %d %d", &num, &cclock, &clck) && num!=0) {

initial();
operation();
}
}

---

and the following is my input and output


input:
5 15 999
5 9 89
5 3 3
5 9 9
5 78 992
0 0 0

output:
5 2, 4 3, 1
4 2, 3 5, 1
3, 1 5, 2 4
4 2, 3, 5 1
3 4, 2 1, 5

[Lawrence]

Well that's easy, just try to input
1 1 1
and find it out yourself.

[cutes_romeo]

what's wrong..????

Code: Select all

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include<io.h>

void main()
{
#ifndef ONLINE_JUDGE
	close(0);
	open("data.txt",O_RDONLY);
	close(1);open("jwb.txt",O_WRONLY|O_CREAT, 0600);
	#endif
int a,b,c,beres=0;
int poin1=1,poin2=1;
int conter1=1,conter2=0;
int hit=0;
while((a!=0)&&(b!=0)&&(c!=0))
{

scanf("%d %d %d",&a,&b,&c);
beres=0;
poin1=1;poin2=1;conter1=1;conter2=0;hit=0;int baris[20]={0};
if((a!=0)&&(b!=0)&&(c!=0))
{
while(beres==0)
{
	beres=1;
	hit++;
	while(conter1!=b)
	{
		if(poin1==a)
			poin1=1;
		else
			poin1++;
		if(baris[poin1]==0)
			conter1++;
	}
	 while(conter2!=c)
	{
		if(poin2==1)
			poin2=a;
		else
			poin2--;
		if((baris[poin2]==0))
			conter2++;
	}

	baris[poin1]=1;conter1=0;
	baris[poin2]=1;conter2=0;
	if(poin1>=10)
		printf(" %d",poin1);
	else
		printf("  %d",poin1);
	if(poin2!=poin1)
	{
		if(poin2>=10)
			printf(" %d",poin2);
		else
			printf("  %d",poin2);
	}
	for(int d=1;d<a;d++)
		if(baris[d]==0)
			beres=0;
	if(beres==0)
		printf(",");
}printf("\n");
}
}
} 

[cyfra]

Hi!

Could you first debug your program -- it gets Compile Error...

Then try to test it on these test cases:

5 5 1

answer

5, 1 4, 2 3

and

2 1 1

answer

1 2

2 2 2

answer

2 1

If your program will still have WA then send it to me..

Good Luck

[Rav]

i solved this problem but i allways get PE, i tried three times change output but allways with same reasult
please (for those whose get AC) send proper output for this tests :
5 5 1
2 1 1
2 2 2
10 4 3
0 0 0
Best Regards

[UFP2161]

OUTPUT:

5, 1 4, 2 3
1 2
2 1
4 8, 9 5, 3 1, 2 6, 10, 7

There's a newline immediately after end of all the lines including last one. (I've found some problems give you PE when one has a newline at the end when it is not wanted, and vice versa for other problems. Quite annoying.)

[Betty]

Ok I seem to be getting WA for 133 and I really dont know why. I get the few examples posted on the forum correct, however I did try compare my code to another persons and noticed some differences, but there program seemed to be giving some unusual results

for
10 4 3
4 8, 9 5, 3 1, 2 6, 10, 7
5 1 1
1 5, 2 4, 3
10 1 1
1 10, 2 9, 3 8, 4 7, 5 6
20 1 1
1 20, 2 19, 3 18, 4 17, 5 16, 6 15, 7 14, 8 13, 9 12, 10 11
20 10 10
10 11, 1 20, 13 8, 5 16, 2 19, 18 3, 6 15, 14 7, 4 17, 12 9

however the other persons code (which you can find by searching for problem 133 in this forum, its the only other post about it) returns

10 1 1
1 10, 2 9, 3 8, 4 7, 5 6
20 1 1
1 19, 2 18, 3 17, 4 16, 5 15, 6 14, 7 13, 8 12, 9 11, 10

10 5 5
5 6, 1 10, 8 3, 9 2, 4 7
20 10 10
10, 1 19, 12 8, 5 15, 2 18, 17 3, 6 14, 13 7, 4 16, 11 9


which are different, however he seems to be inconsistant.

Am I missing something?

Thanks




anyway heres my code.

[cpp]
#include <stdio.h>

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

int person;
PERSON *next;
PERSON *last;
};


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(){
char line[10000];
int n=0,m=0,k=0;
while(1){
fgets(line,10000,stdin);
line[strlen(line)-1]=0;
sscanf(line,"%d %d %d",&n,&k,&m);
if(n==k&&k==m&&m==0)break;
PERSON *head = NULL,*p=NULL;
for(int 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(int i=0;i<k-1;i++)
head=head->next;

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

if(!first)printf(",");
if(p->person==head->person){
printf("%3d",head->person);
}
else{
printf("%3d%3d",head->person,p->person);
}

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

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

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


return 0;
}
[/cpp]

[Maarten]

the output you gave above is correct; however when i try to compile your program I get the following error message:

Code: Select all

temp.cpp: In function `int main()':
temp.cpp:49: error: `strlen' undeclared (first use this function)
temp.cpp:49: error: (Each undeclared identifier is reported only once for each
   function it appears in.)

after including string.h, your program gives the following output:

Code: Select all

  4  8,  9  5,  3  1,  2  6, 10,  7
  1  5,  2  4,  3
  1 10,  2  9,  3  8,  4  7,  5  6
  1 20,  2 19,  3 18,  4 17,  5 16,  6 15,  7 14,  8 13,  9 12, 10 11
 10 11,  1 20, 13  8,  5 16,  2 19, 18  3,  6 15, 14  7,  4 17, 12  9
  0
  0
  0
  0
....

which is obviously not correct (the zeros should not be there)

[Maarten]

i found out your program does not handle correctly the case when there is a \n after the last line...

[Betty]

thanks for you answer, however isn't the program meant to end on input of 0 0 0, therefore it shouldn't be processing lines after that (although I will have to check my program still for that)

[UFP2161]

Yes, that is correct .. however if the last line is like this:

0 0 0

versus

0 0 0\n

then fgets returns "0 0 0" for the first input and "0 0 0\n" for the second, and then you try to truncate the newline, and thus the first line becomes "0 0 " and the second becomes "0 0 0" .. and thus the sscanf fails on the first input, resulting in an infinite loop.