コード圧縮
http://d.hatena.ne.jp/nuc/20060624/p2 より。
'1'から'7'までの数字を一回だけ使って作れる、7文字の文字列のすべての組み合わせを出力するプログラムを、「できるだけ短く」書け。 の C 版見て、あーこれまだまだ短くなるなーと思ってやってみました。アルゴリズムいじってないのでもうちょいヒネれば小さくなりそう。
#include<stdio.h>
main(){int i,k,t;for(i=0;++i<1<<23;k?0:printf("%d\n",i))for(t=i,k=254;t;t/=10)
k^=1<<t%10;}えーと 108Byte ですかね。 PKU 式にやると、
i,k;main(t){for(;++i<1<<23;k?0:printf("%d\n",i))for(t=i,k=254;t;t/=10)k^=1<<t%10;}で 82Byte 。 C++ に勝てるゼー。
あー追記。コメントいただいたのとかを総合すると、
i,k;main(t){for(;++i<1e7;k=k?254:printf("%o\n",i))for(t=i;t;t/=8)k^=1<<t%8;}で 76Byte ですかねぇ。出力を逆順にするのはなんか少し抵抗があったのでなんとなくやめておきました。 id:yaneurao さんの k= の方は気付かなかったのはぼんやりだったなぁという感もあるのですが、 id:kurimura:20060626 さんの 1e7 は忘れてましたし何より %o 使って 10 を 8 にしてるのはすげーすげーというか。
あああと main の第二引数に i を持っていくのも一瞬頭をよぎったんですが、まぁそれは終わるんかいなというのと、逆順になっちゃうのに抵抗があったのでした。
というわけで最近 PKU の問題のコード短くするのを時々やってみてるのですが、どれにせよ id:Ozy さんとか id:kurimura さんに全然勝たせてもらえません。
- 1942 105Byte
http://acm.pku.cn/JudgeOnline/problem?id=1942
nCm を求める問題に帰着する問題。
__int64 s,n,m,i;main(){
for(;scanf("%u%u",&n,&m),i=n+m;printf("%u\n",s))
for(s=1;i-m&&i-n;s/=n+m-i)s*=i--;}
- 1519 68Byte
http://acm.pku.cn/JudgeOnline/problem?id=1519
各ケタを足しまくって、1ケタにする問題。 123456 => 21 => 3 などと。
s;main(){for(;s+=getchar()-48;s-=s<0?printf("%d\n",s+38),s:s/10*9);}これは printf => puts に変換できるのに気付きませんでした。答え見てからいくつか別解出てきたけど短くはならず。
- 1690 158Byte
" *1" に変換する問題。
http://acm.pku.cn/JudgeOnline/problem?id=1690
これはまだもうちょっと考えようと思います。
- 1521 231Byte
文字列をハフマン符号化した時の圧縮率を調べる問題。
http://acm.pku.cn/JudgeOnline/problem?id=1521
まだまだ適当。
適当にやってたヤツとかを追記
- 2316
ヘンな足し算。
http://d.hatena.ne.jp/Ozy/20060626#p3
私の 92Byte に対して 62Byte という記録は異様！と思ってたんですが入力依存な解であったとのこと。良かったです。
s[9],*p;main(c){for(p=s;c=getchar(),~c;)p=c>30?*p+++=c-48,p:s;for(;*p;)putchar(*p++%10+48);}
- 2070
Wizardry のなれるクラスをチェックするみたいなヤツ。
http://d.hatena.ne.jp/Ozy/20060626#p6
を見て騙されたと思いました。
float v;main(w,s,b){for(;scanf("%f %d %d",&v,&w,&s),v;puts(v<=5.&&w/4&&s>299&&printf(" Quarterback"+!b)||b?"":"No positions"))w/=50,b=v<4.6&&w/3&&s>199&&printf("Wide Receiver"),b|=v<=6.&&w/6&&s>499&&printf(" Lineman"+!b);}scanf の中にスペースいらない、 && は & に変えられる、というぼんやりしてたミスもひどいのですが、出力は行末に余計なスペースがくっついていいらしい、ということで適当に編集して 208Byte まで。
float v;main(w,s,b){for(;scanf("%f%d%d",&v,&w,&s),v;puts(v<=5.&w>199&s>299&&printf("Quarterback")||b?"":"No positions"))b=v<4.6&w>149&s>199&&printf("Wide Receiver "),b|=v<=6.&w>299&s>499&&printf("Lineman ");}まぁ普通。トップは 194Byte とかになってるのですげーなーと。
*1:A)-( (B))) - (C-(D- E) )" を "A-B-(C-(D-E
