2575 Jolly Jumpers

PKU

id:Ozyさんが解説(id:Ozy:20060731)している問題です。
インチキをしていたことについさっきまで気づきませんでした。
インチキしてないコードの最短は134byteです。
129byte(インチキver)と134byteを両方さらしておきます。
問題の129byteのコード。

a[5000],j,k;
main(n,i){
  for(;~scanf("%d",&j);i=k>n?memset(a,k=puts(*a?"Not jolly":"Jolly"),2e4):j)
    k++<2?n=i:a[abs(i-j)%n]++&&++*a;
}

このコードですと、たとえば、

2 0 3

みたいな入力に対してjolly jumperと判定してしまいます（|3-0| mod 2 = 1 = (2-1)）。
修正版の134byte。

a[5000],j,k;
main(n,i){
  for(;~scanf("%d",&j);i=k>n?memset(a,k=puts(*a?"Not jolly":"Jolly"),2e4):j)
    k++>1?*a|=a[abs(i-=j)%n]++|i/n:(n=i);
}

一晩経って、ちょっと落ち着いたのでコードの説明をば。

  • "a[abs(i-=j)%n]++"という部分は鳩ノ巣原理とやらを使っています。
  • putsの返値は0、mainの二つの引数は0でない正の数であることを仮定（処理系依存）
  • 変数aも正の数であることを仮定（処理系依存）

この仮定があれば、インクリメントに使う変数kと0との比較をせずに変数nに数列の要素数を入れられます。

一応こだわったことは、どんなinputでも通るということ。
上のBlurred Visionではそれを守ってないので、まぁ気分の問題なのですが。

  • 二つの数字の差が0のときはnot jollyに、
  • 差が大きすぎても配列の範囲外をアクセスしないように、
  • mallocはしない（セット数がいくつか判らないので）、
  • 処理系依存使いまくりんぐ

ということで、これで打ち止め。