DouKaku? 3556 raynstard: 水の量を均一にすればよいのだから最小公倍...(水の移し替えパズル)

Comment detail

水の量を均一にすればよいのだから最小公倍数とか使えそうなんだけど
バカにはよくわからないので一つ一つでカウントしていった。
一番多いところ-二番目に多いところの差を
半分ずつわければもうちょっと計算減らせそうだけど。。。

4L,2L,10L ではBがのこって 10回？

#include <stdio.h>
#include <stdint.h>

#define BAKET_SWAP(a,b) { uint32_t *work = *(a); *(a) = *(b); *(b) = work; }

void baket_sort( uint32_t **baket[] )
{
  int is_changed = 1;
  while( is_changed == 1 )
  {
    is_changed = 0;
    if( (*(baket[0])) < (*(baket[2])) ){ BAKET_SWAP(baket[0], baket[2]); is_changed = 1;}
    if( (*(baket[0])) < (*(baket[1])) ){ BAKET_SWAP(baket[0], baket[1]); is_changed = 1;}
    if( (*(baket[1])) < (*(baket[2])) ){ BAKET_SWAP(baket[1], baket[2]); is_changed = 1;}
  }
}

uint64_t play_game(uint32_t A, uint32_t B, uint32_t C)
{
  uint32_t *baket[] = {&A, &B, &C};
  uint64_t count = 0;

  while( 1 )
  {
    /* 水の量が均一になれば終わり */
    if( A == B )
    {
      printf("のこるのは C\n");
      count += A;
      break;
    }
    if( A == C )
    {
      printf("のこるのは B\n");
      count += A;
      break;
    }
    if( B == C )
    {
      printf("のこるのは B\n");
      count += B;
      break;
    }
    /* 昇順にバブルソート */
    baket_sort( &baket );
    (*(baket[0])) --; (*(baket[1])) --;
    (*(baket[2])) += 2;
    count ++;
  }
  return count;
}

int main(int argc, char *argv[])
{
  printf("ans = %lld\n", play_game(4,2,10));
  printf("ans = %lld\n", play_game(3,1,12));
  return 0;
}

ちょこちょことバグかあるので修正
それにしても、よくcoreをはかず動いていたものです^；；

--- doukaku73.c.org    2007-10-29 22:26:48.875000000 +0900
+++ doukaku73_2.c    2007-10-30 20:51:49.375000000 +0900
@@ -9,9 +9,9 @@
   while( is_changed == 1 )
   {
     is_changed = 0;
-    if( (*(baket[0])) < (*(baket[2])) ){ BAKET_SWAP(baket[0], baket[2]); is_changed = 1;}
-    if( (*(baket[0])) < (*(baket[1])) ){ BAKET_SWAP(baket[0], baket[1]); is_changed = 1;}
-    if( (*(baket[1])) < (*(baket[2])) ){ BAKET_SWAP(baket[1], baket[2]); is_changed = 1;}
+    if( *(*(baket[0])) < *(*(baket[2])) ){ BAKET_SWAP(*(baket[0]), *(baket[2])); is_changed = 1;}
+    if( *(*(baket[0])) < *(*(baket[1])) ){ BAKET_SWAP(*(baket[0]), *(baket[1])); is_changed = 1;}
+    if( *(*(baket[1])) < *(*(baket[2])) ){ BAKET_SWAP(*(baket[1]), *(baket[2])); is_changed = 1;}
   }
 }
 
@@ -37,7 +37,7 @@
     }
     if( B == C )
     {
-      printf("のこるのは B\n");
+      printf("のこるのは A\n");
       count += B;
       break;
     }

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq