Friday, September 17, 2010

ACM: 133 – The Dole Queue

simulation,類似Josephus problem,照著規則模擬。

CODE

#include <iostream>

#define MAX 20

int main(){
  int n, k, m;
  bool a[MAX];
  
  while( scanf("%d%d%d", &n, &k, &m) != EOF ){
    if( n==0 && k==0 && m==0 )
      break;
    
    for(int i=0; i<n; ++i)
      a[i] = 1;
    
    bool printed = 0;
    int i = -1, j = n, left = n;
    int cnt_k, cnt_m;
    while( left > 0 ){
      cnt_k = cnt_m = 0;
      while( cnt_k != k ){
        i = (i+1)%n;
        if( a[i] )
          ++cnt_k;
      }
      while( cnt_m != m ){
        j = (j+n-1)%n;
        if( a[j] )
          ++cnt_m;
      }
      
      if( printed )
        printf(",");
      else
        printed = 1;
        
      if( i == j ){
        a[i] = 0;
        --left;
        printf("%3d", i+1);
      }
      else{
        a[i] = a[j] = 0;
        left -= 2;
        printf("%3d%3d", i+1, j+1);
      }
    }//killing
    printf("\n");
  }//while
  return 0;
}

No comments:

Post a Comment