水の移し替えパズル in C DouKaku?

A, B, Cの容器があり，それぞれ水が4L, 2L, 10L入っている．ここで次の操作を繰り返す．

(*)「A, B, Cのどれか二つの容器から水を1Lずつくみ上げ，残りの容器に移す．」

たとえばA, Bから1Lずつくみ上げて移せばA=3L, B=1L, C=12Lとなる．くみ上げる前の容器には必ず水が入っているとする．

(*)を繰り返してどれか一つの容器にのみ水がはいっている状態にする最小手数を求めよ．

可能ならA=827392L，B=65536L，C=122880Lのときも求めよ．

このお題は光成さんの投稿を元に作成しました。ご協力ありがとうございます。

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

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;
}

一箇所に水が集まるということは、その前の段階では残り二箇所は同じ数字になっている。
ならば、どうやって同じ数字にするか、と考えると2箇所から1を引いて残り一箇所に2を足すと考えると、3ずつしか差分は動かない。
よって差が３の倍数である組に注目する。
手順としてはその組の大きい数字を0にする作業となるので差が3の倍数である組の最大値が回答になる。
差が3の倍数の組が二つある場合は小さいほうの組でよい。

ってことで、こうなりました。

#include <stdio.h>
#include <stdlib.h>

long water_move(long a,long b,long c){
    long ret=-1;
    
    if((a-b)%3==0)
        ret=max(a,b);
    if((a-c)%3==0)
        if(ret==-1) ret=max(a,c);
        else ret=min(ret,max(a,c));
    if((b-c)%3==0)
        if(ret==-1) ret=max(b,c);
        else ret=min(ret,max(b,c));
    
    return ret;
}

void put_water_move(long a,long b, long c){
    int ret;
    
    ret=water_move(a,b,c);
    printf("A=%ld B=%ld C=%ld : ");
    if (ret==-1)
        printf("出来ません\n");
    else
        printf("%ld\n",ret);
}

int main(){
    put_water_move(4,2,10);
    put_water_move(827392,65536,122880);
    put_water_move(4,2,6);
    put_water_move(4,1,10);
    
    return 0;
}

DouKaku?

水の移し替えパズル

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq