タイトルは99%関係ないんですがね。こういうパズル大好きなんですよ。
1025 学名ナナシ :2008年07月15日 21:46
今までこれ系で一番難しかったのは、
13枚のコインがあって、1枚だけ偽者があります。
偽者は重いのか軽いのかはわかりません。
天秤を3回だけ使ってどのコインが偽者か当てなさい。
どうしても解けない...
googleの面接 : アルファルファモザイク
↓10分くらいで考えた回答
とりあえず、(1)から(13)まで番号を振る
(1)(2)(3)(4)と(5)(6)(7)(8)を天秤に乗せる
傾いたら
残りの(9)-(13)は本物
(1)(2)(3)(5)(6)と(9)(10)(11)(12)(13)を天秤に載せる
傾いたら
ここで偽者が重いか軽いかが判明
かつ、一回目の結果を考えると、(1)(2)(3) OR (5)(6) のいずれに偽者が含まれるかも判明
(1)(2)(3)に偽者が含まれるなら
(1)と(2)を比較。
(5)(6)に偽者が含まれる
(5)と(6)を比較
傾かなかったら
(4)(7)と(12)(13)を比較
傾いたら
偽者が重いか軽いかが分かる。
かつ、一回目の結果を考えれば、(4)と(7)のどちらが重いか分かるので、判定可能
傾かなかったら
(8)が偽者(重いか軽いかは分からず)
傾かなかったら
残りの(9)-(13)に偽者が含まれる。(1)から(8)は本物
(1)(2)(3)と(9)(10)(11)を天秤に
傾いたら
偽者が重いか軽いかが分かる
(9)と(10)を天秤に
傾かなかったら
(12)(13)のいずれかが偽者
(1)と(12)を天秤に
で、perlで書いてみた。
#!/usr/bin/perl
use strict;
sub which_is_heavy {
my ($left, $right) = @_;
#この辺は本来ならブラックボックス
my ($left_mass, $right_mass);
map { $left_mass += $_ } @$left;
map { $right_mass += $_ } @$right;
return $left_mass > $right_mass ? 'left'
: $left_mass < $right_mass ? 'right'
: 'balanced';
}
sub get_fake_from_three {
#偽者が重いか軽いか分かってれば3つのコインから一発で偽者を割り出せるよ関数
my ($fake, @coins) = @_;
if ($coins[0] > $coins[1] ) {
return $fake eq 'heavy' ? 0 : 1;
}
elsif ( $coins[0] < $coins[1] ) {
return $fake eq 'heavy' ? 1 : 0;
}
else {
return 2;
}
}
sub get_fake {
my @c = @_;
my $first_result = which_is_heavy( [ @c[0..3] ] ,[ @c[4..7] ] );
if ($first_result eq 'balanced' ) {
#0-7は本物
my $second_result = which_is_heavy( [@c[0..2]], [@c[8..10]] );
if ($second_result eq 'balanced' ) {
#11,12が偽者
my $third_result = which_is_heavy( [ $c[0] ], [ $c[11] ]);
return $third_result eq 'balanced' ? 12 : 11;
}
else {
#8-10に偽者かつ重いか軽いかが判明
my $fake = $second_result eq 'left' ? 'light' : 'heavy';
return 8 + get_fake_from_three($fake, @c[8..10]);
}
}
else {
#8-12は本物
my $second_result = which_is_heavy( [$c[0],$c[1],$c[2],$c[4],$c[5]],[@c[8..12]] );
if ($second_result eq 'balanced' ) {
my $third_result = which_is_heavy( [$c[3], $c[6]], [@c[8..9]] );
if ( $third_result eq 'left') {
return $first_result eq 'left' ? 3 : 6;
}
elsif ( $third_result eq 'right' ) {
return $first_result eq 'left' ? 6 : 3;
}
else {
return 7;
}
}
else {
my $fake = $second_result eq 'left' ? 'heavy' : 'light';
if ( ( $fake eq 'heavy' && $first_result eq 'left' )
|| ( $fake ne 'heavy' && $first_result ne 'left' ) ) {
return get_fake_from_three( $fake, @c[0..2] );
}
else {
if ( $fake eq 'heavy' ) {
return $c[4] > $c[5] ? 4 : 5;
}
else {
return $c[4] > $c[5] ? 5 : 4;
}
}
}
}
}
print get_fake( 3,2,2,2,2,2,2,2,2,2,2,2,2 ) . " will be 0\n";
print get_fake( 2,3,2,2,2,2,2,2,2,2,2,2,2 ) . " will be 1\n";
print get_fake( 2,2,3,2,2,2,2,2,2,2,2,2,2 ) . " will be 2\n";
print get_fake( 2,2,2,3,2,2,2,2,2,2,2,2,2 ) . " will be 3\n";
print get_fake( 2,2,2,2,3,2,2,2,2,2,2,2,2 ) . " will be 4\n";
print get_fake( 2,2,2,2,2,3,2,2,2,2,2,2,2 ) . " will be 5\n";
print get_fake( 2,2,2,2,2,2,3,2,2,2,2,2,2 ) . " will be 6\n";
print get_fake( 2,2,2,2,2,2,2,3,2,2,2,2,2 ) . " will be 7\n";
print get_fake( 2,2,2,2,2,2,2,2,3,2,2,2,2 ) . " will be 8\n";
print get_fake( 2,2,2,2,2,2,2,2,2,3,2,2,2 ) . " will be 9\n";
print get_fake( 2,2,2,2,2,2,2,2,2,2,3,2,2 ) . " will be 10\n";
print get_fake( 2,2,2,2,2,2,2,2,2,2,2,3,2 ) . " will be 11\n";
print get_fake( 2,2,2,2,2,2,2,2,2,2,2,2,3 ) . " will be 12\n";
print get_fake( 1,2,2,2,2,2,2,2,2,2,2,2,2 ) . " will be 0\n";
print get_fake( 2,1,2,2,2,2,2,2,2,2,2,2,2 ) . " will be 1\n";
print get_fake( 2,2,1,2,2,2,2,2,2,2,2,2,2 ) . " will be 2\n";
print get_fake( 2,2,2,1,2,2,2,2,2,2,2,2,2 ) . " will be 3\n";
print get_fake( 2,2,2,2,1,2,2,2,2,2,2,2,2 ) . " will be 4\n";
print get_fake( 2,2,2,2,2,1,2,2,2,2,2,2,2 ) . " will be 5\n";
print get_fake( 2,2,2,2,2,2,1,2,2,2,2,2,2 ) . " will be 6\n";
print get_fake( 2,2,2,2,2,2,2,1,2,2,2,2,2 ) . " will be 7\n";
print get_fake( 2,2,2,2,2,2,2,2,1,2,2,2,2 ) . " will be 8\n";
print get_fake( 2,2,2,2,2,2,2,2,2,1,2,2,2 ) . " will be 9\n";
print get_fake( 2,2,2,2,2,2,2,2,2,2,1,2,2 ) . " will be 10\n";
print get_fake( 2,2,2,2,2,2,2,2,2,2,2,1,2 ) . " will be 11\n";
print get_fake( 2,2,2,2,2,2,2,2,2,2,2,2,1 ) . " will be 12\n";