|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．えと，今回は第624回ですね。
最初問題を読んだとき，「どの奇数番目や偶数番目のカードを１枚取り除いても同じになるはずないよなぁ。」とか思いましたが， 「すべて」のカードを取り除くのですね。 題意が分かってしまえば，最悪書き出しても何とかなりそうですが，一応，次のように考えました。 (解法1) ○を正の整数として，最初のアで，2 * ○ が残ります。 次のイでは，この○自体が 2 * ○ - 1 と書けるものが残ります。つまり，4 * ○ - 2 が残ります。 次のアでは，この○自体が 2 * ○ と書けるものが残ります。つまり，8 * ○ - 2 が残ります。 次のイでは，この○自体が 2 * ○ - 1 と書けるものが残ります。つまり，16 * ○ - 10 が残ります。 以下同様にして，残るのは，順次，32 * ○ - 10，64 * ○ - 42，128 * ○ - 42，256 * ○ - 170，512 * ○ - 170 となっていきます。 カードは 512 枚しかないので，結局最後に残るのは，512 * 1 - 170 = 342 になります。 (解法2) 2 進法を使います。実は，最初に思いついたのですが，ナイーブにやると若干注意が必要で，頭の中だけではこんがらがってしまいました (^^; 1 〜 512 を 2 進法に直します。これは，0000000001 〜 1000000000 です。すると， 最初のアでは，最初が 0000000001 なので，XXXXXXXXX1 が取り除かれ，XXXXXXXXX0 が残ります。 次のイでは，最初が 0000000010 なので，XXXXXXXX00 が取り除かれ，XXXXXXXX10 が残ります。 次のアでは，最初が 0000000010 なので，XXXXXXX010 が取り除かれ，XXXXXXX110 が残ります。 次のイでは，最初が 0000000110 なので，XXXXXX1110 が取り除かれ，XXXXXX0110 が残ります。 次のアでは，最初が 0000000110 なので，XXXXX00110 が取り除かれ，XXXXX10110 が残ります。 次のイでは，最初が 0000010110 なので，XXXX110110 が取り除かれ，XXXX010110 が残ります。 次のアでは，最初が 0000010110 なので，XXX0010110 が取り除かれ，XXX1010110 が残ります。 次のイでは，最初が 0001010110 なので，XX11010110 が取り除かれ，XX01010110 が残ります。 次のアでは，最初が 0001010110 なので，X001010110 が取り除かれ，X101010110 が残ります。 ここで，X101010110 < 1000000000 なので，X = 0 で，残っているのは 101010110 です。 これを 10 進法に直すと，101010110 = 2^8 + 2^6 + 2^4 + 2^2 + 2^1 = 256 + 64 + 16 + 4 + 2 = 342 になります。 (解法3) (解法2)では，最初のところだけが 1 から始まるので，若干注意が必要になりました。 そこで，1 〜 512 ではなく 1 ずらして 0 〜 511 で考え，最後に +1 して元に戻すとします。すると，000000000 〜 111111111 において， 最初のアでは，最初が 000000000 なので，XXXXXXXX0 が取り除かれ，XXXXXXXX1 が残ります。 次のイでは，最初が 000000001 なので，XXXXXXX11 が取り除かれ，XXXXXXX01 が残ります。 次のアでは，最初が 000000001 なので，XXXXXX001 が取り除かれ，XXXXXX101 が残ります。 次のイでは，最初が 000000101 なので，XXXXX1101 が取り除かれ，XXXXX0101 が残ります。 次のアでは，最初が 000000101 なので，XXXX00101 が取り除かれ，XXXX10101 が残ります。 ．．．以下同様で，XXX010101，XX1010101，X01010101，101010101 が残ります。 これを 10 進法に直すと，101010101 = 2^8 + 2^6 + 2^4 + 2^2 + 1 = 256 + 64 + 16 + 4 + 1 = 341 で， +1 して元に戻すと 341 + 1 = 342 になります。 |
|
ネコの住む家
11月27日（木） 11:26:33
MAIL:uchi@sco.bekkoame.ne.jp 33362 |