133 - The Dole Queue

raygun · Post by **raygun** » Mon Jul 30, 2007 11:10 am

Question about problem 133:
- What effect does "m" have on the solution? A full test search on the problem description doesn't show any information about this variable.

Can't be too cautious with these problems..

mf · Post by mf » Mon Jul 30, 2007 11:22 am

Post in an existing thread on this problem. Don't create a new thread.

As for your question:

... while another official starts from N and moves clockwise, counting m applicants.

kauedg · Post by **kauedg** » Fri Aug 24, 2007 7:09 pm

Code: Select all

#include <stdio.h>

typedef struct QUEUE
{
	int number;
	struct QUEUE *next;
	struct QUEUE *prev;
	
}QUEUE;

QUEUE* CreateQueue(QUEUE *q, int n)
{
	QUEUE *temp, *last;
	int i;
	
	last = q;
	
	for(i=n; i>=1; i--)
	{
        temp = malloc(sizeof(QUEUE));
        
        temp->number = i;
        
        if(q == NULL)
        {
			temp->next = temp;
			temp->prev = temp;
			q = temp;
		}
		else
		{
			temp->prev = last;
			temp->next = last->next;
			last->next = temp;
			q->prev = temp;
		}
		
		last = temp;
	}
	
	return q;

}

int main()
{
	int n,k,m,i;
	
	QUEUE *queue, *officerk, *officerm;
	
	scanf("%d %d %d",&n,&k,&m);
	
	while( n!=0 && k!=0 && m!=0)
	{
        queue = NULL;
        
		queue = CreateQueue(queue, n);

	    officerk = queue;
	    officerm = queue;

		while(officerk->number != 1)
		    officerk = officerk->next;

		while(officerk != NULL)
		{
			for(i=k-1; i>0; i--)
			    officerk = officerk->prev;

			for(i=m-1; i>0; i--)
			    officerm = officerm->next;

			if(officerk->number != officerm->number)
			{
			    printf(" %2d %2d",officerk->number, officerm->number);

			    officerk->prev->next = officerk->next;
			    officerk->next->prev = officerk->prev;
			    officerk = officerk->prev;

			    if(officerk->number == officerm->number)
			        officerk = officerk->prev;

			    officerm->prev->next = officerm->next;
			    officerm->next->prev = officerm->prev;
			    officerm = officerm->next;
			    
			    if(officerk->next->number == officerk->number)
				{
	                officerk = NULL;
				}
			}
			else
			{
	            printf(" %2d",officerk->number);

				if(officerk->next->number == officerk->number)
				{
	                officerk = NULL;
				}
				else
				{
				    officerm = officerm->next;

				    officerk->prev->next = officerk->next;
					officerk->next->prev = officerk->prev;
					officerk = officerk->prev;
				}
			}

	       	if(officerk != NULL)
			    printf(",");
   			else
   			    puts("");

		}

		scanf("%d %d %d",&n,&k,&m);
	}
	
	printf("\n");
	
	return 0;
}

Your C program has solved Ok the problem 133 (The Dole Queue) in 0.002 seconds with low memory spent.
Congratulations!

Warning: Your program would get a Presentation Error in a true contest.
The 24-hours judge interpretes it as an "Accepted" problem.

I have already formatted the output so it always have 3 characters. Help plese? :/

kauedg · Post by **kauedg** » Fri Aug 24, 2007 7:12 pm

I got it, had to remove the last printf("");

Your C program has solved Ok the problem 133 (The Dole Queue) in 0.000 seconds with low memory spent.
Congratulations!

Hope this help somebody.

mirage · Post by **mirage** » Fri Feb 22, 2008 1:31 pm

hey friends,
i can't figure our why i m gettin a presentation error in this....plz help

Code: Select all

//dole_queue
#include<iostream>
using namespace std;
int arr[20];
void print(int);
int main(){
	int n,k,m;
	while(cin>>n>>k>>m){
		if(n+k+m==0) return(0);
		int i=0;
		while(i<n) arr[i++]=0;
		//start simulatin
		int in1=0,in2=n-1;
		int count=0;
		while(count<n){
			//find p1
			int j=0;
			while(j<k){
				if(arr[in1]==0) j++;
				in1=(in1+1)%n;
			}
			j=0;
			while(j<m){
				if(arr[in2]==0) j++;
				in2=(in2+n-1)%n;
			}
			int a=(in1-1+n)%n;
			int b=(in2+1)%n;
			if(a==b) {
				count++;
				if(count<n) cout<<" "<<a+1;
				else cout<<"  "<<a+1;
				arr[a]=1;
			}
			else{
				cout<<"  "<<a+1<<"  "<<b+1;
				arr[a]=1;
				arr[b]=1;
				count=count+2;
			}
			if(count<n) cout<<",";
			//print(n);
		}
		cout<<"\n";
	}
	return(0);
}
void print(int y){
	int p=0;
	cout<<"\n";
	while(p<y) cout<<arr[p++]<<" ";
	cout<<"\n";
	return;
}

tplee923 · Post by **tplee923** » Sat Mar 09, 2013 7:44 pm

Hello I am using pointer to solve the problem, but it always get runtime error, can someone help me see what could cause the error? Thanks!

Code: Select all

//uva 133
#include<cstdio>

typedef struct Node* PTR;
struct Node {
	int val;
	PTR left,right;
};

int main() {
	int N,k,m;
	while(scanf("%d %d %d",&N,&k,&m),N+k+m) {
		int size=N;
		PTR head=NULL,p=NULL,pre=NULL;
		for(int i=0;i<N;i++) {
			if(!head) {
				head = new Node;
				head->val = i+1;
				head->left = head->right = NULL;
				pre = head;
			} else {
				p = new Node;
				p->val = i+1;
				pre->left = p;
				p->right = pre;
				p->left = NULL;
				pre = p;
			}
		}
		p->left=head;
		head->right=p;
		int j=size;
		PTR kstart = head,mstart=head->right;
		PTR kp,mp;
		while(j > 0) {
			kp=kstart;
			mp=mstart;
			for(int i=2;i<=k;i++) {
				kp = kp->left;
			}
			for(int i=2;i<=m;i++) {
				mp = mp->right;
			}
			
			kp->left->right = kp->right;
			kp->right->left = kp->left;
			j--;
			printf("%3d",kp->val);
			
			if(kp==mp) {
				if(j==0)
					printf("\n");
				else
					printf(",");
				kstart=kp->left;
				mstart=mp->right;
				delete kp;
			}
			else {
				mp->left->right = mp->right;
				mp->right->left = mp->left;
				j--;
				printf("%3d",mp->val);
				if(j==0)
					printf("\n");
				else
					printf(",");
				if(kp->left==mp) 
					kstart=mp->left;
				else
					kstart=kp->left;
				if(mp->right==kp)
					mstart= kp->right;
				else
					mstart=mp->right;
				delete kp;
				delete mp;
			}
		}
	}
	return 0;
}

tplee923 · Post by **tplee923** » Sat Mar 09, 2013 8:29 pm

Just found an edge case, when N is 1, this program will seg fault. after solve this case, the program got AC.

hpjhc · Post by **hpjhc** » Mon Jul 22, 2013 5:31 am

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
typedef struct node* link;
typedef struct node
{
int n;
link next;
link prev;
}Node;

int main(void)
{
int i, n, k, m;
Node *N[30];
Node *n1, *n2;
for(i = 1; i <= 30; i++)
{
N = (Node *)malloc(sizeof(Node));
N->n = i;
}
while(scanf("%d%d%d", &n, &k, &m), n||k||m)
{

for(i = 1; i < n; i++)
{
N->next = N[i+1];
N[i+1]->prev = N;
}
N[1]->prev = N[n];
N[n]->next = N[1];
n1 = N[n];
n2 = N[1];
while(1)
{
for(i = 0; i < k; i++)
n1 = n1->next;
for(i = 0; i < m; i++)
n2 = n2->prev;
if(n1->next == n1)
{
printf("%3d\n", n1->n);
break;
}
if(n1 == n2)
{
printf("%3d,", n1->n);
n1->prev->next = n1->next;
n1->next->prev = n1->prev;
n1 = n1->prev;
n2 = n2->next;
}
else
{
printf("%3d%3d,", n1->n, n2->n);
n1->prev->next = n1->next;
n1->next->prev = n1->prev;
n2->prev->next = n2->next;
n2->next->prev = n2->prev;
n1 = n1->prev;
n2 = n2->next;
}
}
}
for(i = 1; i <= 30; i++)
free(N);
return 0;
}

brianfry713 · Post by **brianfry713** » Tue Jul 23, 2013 12:47 am

Try input 8 4 3

goldenge · Post by **goldenge** » Fri May 16, 2014 5:48 am

The following algorithm continues to get WA despite testing and correctly solving every sample case I can find/think of. All help is appreciated.

Here's my input and output:

Input --
8 4 6
10 4 3
10 1 1
10 5 5
20 1 1
20 10 10
0 0 0

Output --
4 3, 8 5, 7 1, 6 2
4 8, 9 5, 3 1, 2 6, 10, 7
1 10, 2 9, 3 8, 4 7, 5 6
5 6, 1 10, 8 3, 9 2, 4 7
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, 9 12, 17 4, 14 7

Code: Select all

#include <cmath>
#include <iostream>
#include <sstream>
#include <vector>
#include <iomanip>
#include <stdio.h>

int main() {
    
    std::string line = "";
    while(std::getline(std::cin, line)) {
        int N,k,m;
        std::istringstream iss(line);
        
        iss >> N >> k >> m;
        
        // END
        if( (0 == N) && (0 == k) && (0 == m) ) {
            break;
        } // END

        m = m-1;
        k = k-1;
        
        // Begin selection and removal
        std::vector<int> people(N);
        for(int i = 1; (i <= N); i++) {
            people[i-1] = i;
        }
        
        //Clockwise   --m--
        //Counter-cw: --k--
        int mIndex = N-1;
        int kIndex = 0;
        while(!people.empty()) {
            
            int size = people.size();
            
            m = m % size; // Eliminate unnecessary loops
            k = k % size;
            
            mIndex = (mIndex - m) % size;
            if(mIndex < 0) {
                mIndex = size + (mIndex % size);
            }
            
            kIndex = (kIndex + k) % size;
            if(kIndex < 0) {
                kIndex = size + (kIndex % size);
            }
            // REMOVAL
            if(mIndex == kIndex) {
                printf(" %2d", people[mIndex]);
                //                std::cout << std::setw(3) << people[mIndex];
                people.erase(people.begin() + mIndex);
                mIndex--; // Vector shift
            } else {
                printf(" %2d %2d",people[kIndex], people[mIndex]);
                //                std::cout << std::setw(3) << people[kIndex] << std::setw(3) << people[mIndex];
                if(mIndex > kIndex) {
                    people.erase(people.begin() + mIndex);
                    people.erase(people.begin() + kIndex);
                    mIndex -= 2; // Vector shift
                } else {
                    people.erase(people.begin() + kIndex);
                    people.erase(people.begin() + mIndex);
                    mIndex--; // Vector shift
                    kIndex--;
                } 
            }
            if(!people.empty()) {
                std::cout << ",";
            }
        }
        std::cout << std::endl;
    }
}

brianfry713 · Post by **brianfry713** » Fri May 16, 2014 9:46 pm

AC output for your input:

Code: Select all

  4  3,  8  5,  7  1,  6  2
  4  8,  9  5,  3  1,  2  6, 10,  7
  1 10,  2  9,  3  8,  4  7,  5  6
  5  6,  1 10,  8  3,  9  2,  4  7
  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

Tanmoy Tapos Datta · Post by **Tanmoy Tapos Datta** » Wed Jan 14, 2015 6:02 pm

Getting WA

. But I can't find the mistakes. Please help me.

Code: Select all

#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 100
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int n,k,m;
    while(cin>>n>>k>>m)
    {
        if(!n && !k && !m)
            break;
        vector<int> v;
        for(int i=1; i<=n; i++)
            v.pb(i);
        int ii=-1,jj=v.size();
        bool test=1;
        while(!v.empty())
        {

            int Sz=SZ(v);
            for(int i=0; i<k; i++)
            {
                ii++;
                if(ii==v.size())
                    ii=0;
            }
            for(int i=0; i<m; i++)
            {
                jj--;
                if(jj==-1)
                    jj=v.size()-1;
            }
            int aa=v[ii],bb=v[jj];
            if(ii!=jj)
            {
                pf("%3d%3d",v[ii],v[jj]);
                if(ii<jj)
                {

                    v.erase(v.begin()+ii);
                    v.erase(v.begin()+jj-1);
                }
                else
                {
                    v.erase(v.begin()+ii);
                    v.erase(v.begin()+jj);
                }
                if(ii<jj)
                {
                    jj--,ii--;
                    if(ii<0)
                        ii=v.size()-1;
                    if(jj<0)
                        jj=v.size()-1;
                }
                else if(ii>jj)
                {
                    ii--;
                    if(ii<0)
                        ii=v.size()-1;
                    ii--;
                    if(ii<0)
                        ii=v.size()-1;
                }
            }
            else
            {
                pf("%3d",v[ii]);
                v.erase(v.begin()+ii);
                ii--;
                if(ii<0)
                    ii=v.size()-1;
                jj++;
                if(jj==v.size()+1)
                    jj=0;

            }
            if(!v.empty())
                pf(",");

        }
        v.clear();
        cout<<endl;
    }
    return 0;
}

brianfry713 · Post by **brianfry713** » Thu Jan 15, 2015 1:26 am

It looks like you figured it out.

OJ Board

133 - The Dole Queue

133 problem description

gettin PE ...plz help

Why 133 - The Dole Queue keeps Runtime Error

Re: Why 133 - The Dole Queue keeps Runtime Error

133 - The Dole Queue WA

Re: 133 - The Dole Queue WA

133 WA despite passing all test cases that I could find

Re: 133 WA despite passing all test cases that I could find

Re: 133 - The Dole Queue

Re: 133 - The Dole Queue