CodeIQ過去問集10：ショートコーディング：きのこ危機一髪
本稿はCodeIQで2015年3月6日～2015年3月27日に出題された「ショートコーディング：きのこ危機一髪」という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。
ショートコーディング：きのこ危機一髪
【きのこ村にて】
きのこ村は今日もいいお天気。
きのこ兄弟たちは仲良く並んで散歩しています。
そんなある日…
暴れん坊ウサギのルイースがやってきました！ ルイースはきのこたちを見つけると、踏みつけてくるのです！！
【問題】
きのこたちは暴れん坊ウサギのルイースに踏みつけられてしまいますが、ルイースは次のようなルールで踏みつけてくるので、一匹だけ生き残るきのこがいます。 ルイースはきのこを見つけると高く飛び上がります。ルイースはあまり頭が良くないので飛距離の調節が上手くできません。
ですので、このように一匹目を飛び越えて二匹目を踏みつけてしまいます。
次も同じように飛ぶので、また一匹飛び越えて踏みつけます。
これを繰り返し、端まで進みきのこが見えなくなると後ろを振り返ります。
今度は反対方向に、一匹飛び越えて踏みつけていきます。
これを繰り返すと、最後に残った一匹だけは生き延びることができます。
きのこたちを先頭から1番目, 2番目, 3番目, ...と数えるとすると、n匹のきのこがいた場合、生き延びることができるのは何番目のきのこになるかを調べるプログラムを『C言語で』『できるだけ短く』書いてください。
【入力】
標準入力から、整数値n（1≦n≦10000）が与えられます。
【出力】
最後まで生き残るきのこの番号を出力してください。改行はあっても無くてもどちらでも良いですが、それ以外（"ans="などの文字列）は出力しないでください。
【入出力サンプル】
Case 1: Input
5
Case 1: Output
1
Case 2: Input
100
Case 2: Output
35
Case 3: Input
10000
Case 3: Output
8715
【評価方法】
コンパイル・実行テストはideone.comで行います。
コンパイルについて
Ideone.comのC(gcc-4.9.2)は32bit環境で、最適化オプション"-O2"でコンパイルされるようですので、処理系依存の強いコードをご提出の際にはご注意ください。
実行テスト
実行テストは複数のテストケースを用いて行いますので、上記のサンプルで正しい出力が得られても正解になるとは限りません。すべてのテストケース（非公開）に対して正しい出力が得られたら、ご提出いただいたテキストファイルのサイズを記録とします。つまり、ご提出いただくファイルにコメントや空白・改行が入っていると、その分の文字数もカウントされます。
【禁止事項】
Ideone.comのセキュリティを突いて不正にデータ通信を行うようなコードは禁止とします。また、system関数を用いて、たとえばPerlのコードを実行するコードのような、実質C以外の言語を用いたコードも今回は禁止とします。
【注意事項】
Ideone.comの使用について
Ideone.comでコードを実行する際、「Public」「Secret」「Private」の、3つのモードがありますが、ユーザ登録している場合はログインして「Private」、ユーザ登録していない場合は「Secret」にしてください。 Publicで実行すると、recent codesというところにコードが表示され、丸見え状態になってしまいます。
【ショートコーディングとは】
ショートコーディングは、ソースコードを一定のルール内で限界まで短くする遊びです。 コードが縮んだ時の達成感には中毒性があり、のめり込み過ぎると頭痛や眩暈・吐き気をもよおす恐れがあります。 また、長時間のショートコーディングは廃人になりますので、考えるのは長くて1時間程度に留めておきましょう。
