The Drunk Jailer(1)
この手の問題は、カシコーなアルゴリズムをひねり出す前に答えがどうなっているのか調べた方が手っ取り早い。インプットの値は、5以上100以下に限定されているので、すべての答えを書き出してしまえばいいのだ。
このコードを実行して、答えを調べると以下のようになる。
i,j,k,n,c,s[101];main(){
for(n=5;c=0,n<=100;n++){
memset(s,0,sizeof(s));
for(i=1;i<=n;i++)
for(j=i;j<=n;j+=i)s[j]=1-s[j];for(i=1;i<=n;i++)if(s[i])c++;
printf("n:%d c=%d\n",n,c);
}
}
(nがインプット、cが答え)
一目瞭然、解は規則的に増えている。ということは、この数の規則性さえつかんでしまえば、簡単な計算で解は見つかる！
n:5 c=2
n:6 c=2
n:7 c=2
n:8 c=2
n:9 c=3
n:10 c=3
n:11 c=3
n:12 c=3
n:13 c=3
n:14 c=3
n:15 c=3
n:16 c=4
n:17 c=4
n:18 c=4
n:19 c=4
n:20 c=4
n:21 c=4
n:22 c=4
n:23 c=4
n:24 c=4
n:25 c=5
n:26 c=5
n:27 c=5
n:28 c=5
n:29 c=5
n:30 c=5
n:31 c=5
n:32 c=5
n:33 c=5
n:34 c=5
n:35 c=5
n:36 c=6
n:37 c=6
n:38 c=6
n:39 c=6
n:40 c=6
n:41 c=6
n:42 c=6
n:43 c=6
n:44 c=6
n:45 c=6
n:46 c=6
n:47 c=6
n:48 c=6
n:49 c=7
n:50 c=7
n:51 c=7
n:52 c=7
n:53 c=7
n:54 c=7
n:55 c=7
n:56 c=7
n:57 c=7
n:58 c=7
n:59 c=7
n:60 c=7
n:61 c=7
n:62 c=7
n:63 c=7
n:64 c=8
n:65 c=8
n:66 c=8
n:67 c=8
n:68 c=8
n:69 c=8
n:70 c=8
n:71 c=8
n:72 c=8
n:73 c=8
n:74 c=8
n:75 c=8
n:76 c=8
n:77 c=8
n:78 c=8
n:79 c=8
n:80 c=8
n:81 c=9
n:82 c=9
n:83 c=9
n:84 c=9
n:85 c=9
n:86 c=9
n:87 c=9
n:88 c=9
n:89 c=9
n:90 c=9
n:91 c=9
n:92 c=9
n:93 c=9
n:94 c=9
n:95 c=9
n:96 c=9
n:97 c=9
n:98 c=9
n:99 c=9
n:100 c=10
