Introduction

ブログ内検索

  • このサイトの記事を検索 by Google

おすすめの一冊!

無料ブログはココログ

« Opera と AltIME | トップページ | Evernote API の門を叩く »

2011-01-25

算数オリンピック


はてなのエンジニアが「算数オリンピック」に挑戦してみた、
という記事が面白そうだったので、Seaoak も挑戦してみました。


    ⇒ はてな若手エンジニアが「算数オリンピック」の問題を解いてみた算数オリンピック


とりあえず、最初の問題(問題6)は直感で解けました。

2問目(問題1)は、倍数を全部書き出して、出現する数字の数を数えて、正解。

3問目(問題3)は、高校時代に勉強した「整数問題」みたいな印象(なつかしい)。
とりあえず方程式を立てて、各変数が 1~9 の整数であるという条件で
とりうる値を絞り込み、最後は5個くらいのケースを場合分けでしらみつぶし。
かなり時間がかかりましたが、とりあえず全部の値を見つけられました。
# 5個以外の解が無いことも確認できました。

4問目(問題7)は、直感で解いたのですが、不正解。



くやしいので、C言語で解いてみました。

◎ 2問目(問題1)
#include <stdio.h> int populate(int div, int count[]) { int total = 0; int i; for (i=1; i<=9; i++) { int j; for (j=1; j<=9; j++) { if (i==j) continue; { const int x = 10*i+j; if (x % div) continue; count[i]++; count[j]++; total++; } } } return total; } int main(int argc, char *argv[]) { int table2[10] = {0}; int table4[10] = {0}; int table7[10] = {0}; const int total2 = populate(2, table2); const int total4 = populate(4, table4); const int total7 = populate(7, table7); { int i; for (i=1; i<=9; i++) { if (table2[i] != total2 - 21) continue; if (table4[i] != total4 - 12) continue; if (table7[i] != total7 - 8) continue; printf("%d\n", i); } } return 0; }
◎ 3問目(問題3)
#include <stdio.h> int main(int argc, char *argv[]) { int i; for (i=100; i<=999; i++) { if (i % 10 == 0) continue; { const int x = i / 10 + i % 10; if (i % x) continue; } { const int y = i / 100 + i % 100; if (i % y) continue; } printf("%d\n", i); } return 0; }
◎ 4問目(問題7)
#include <stdio.h> int populate(int x) { int count = 0; while (x) { if (x & 0x1) count++; x >>= 1; } return count; } int main(int argc, char *argv[]) { int count = 0; int x; for (x=0; x<(1<<25); x++) { const int mask_column = ((0x1 << (5*4)) | (0x1 << (5*3)) | (0x1 << (5*2)) | (0x1 << (5*1)) | (0x1 << (5*0))); if (populate(x) != 6) continue; if (! ((x >> (5*4)) & 0x1f)) continue; if (! ((x >> (5*3)) & 0x1f)) continue; if (! ((x >> (5*2)) & 0x1f)) continue; if (! ((x >> (5*1)) & 0x1f)) continue; if (! ((x >> (5*0)) & 0x1f)) continue; if (! ((x >> 4) & mask_column)) continue; if (! ((x >> 3) & mask_column)) continue; if (! ((x >> 2) & mask_column)) continue; if (! ((x >> 1) & mask_column)) continue; if (! ((x >> 0) & mask_column)) continue; count++; } printf("%d\n", count); return 0; }
いずれもちゃんと正解が得られました。 ちゃちゃっとビット演算を使うときはC言語でも悪くないですねー

« Opera と AltIME | トップページ | Evernote API の門を叩く »