問題A in CPS

問題Aはもともと簡単な問題だけど、
CPSでもっと簡単に解けるようである。
つまり、各シャッフルを置換と考えるわけですね。

とりあえずHaskellで。

solve n ls = n - (foldr inner id ls 0) where
  inner (p,c) f i = f $ if i<=c then i+p-1 else if i 4

入出力つき。

main = getContents >>= mapM_ (print.solve) . slice . map read . words where
  slice (0:0:_) = []
  slice (n:r:xs) = (n,take r $ map (take 2) $ iterate (drop 2) xs):
                   (slice $ drop (r*2) xs)

solve (n,ls) = n - (foldr inner id ls 0) where
  inner [p,c] f i = f $ if i<=c then i+p-1 else if i

ついでに芋っぽい解答。

main = getContents >>= mapM_ (print.solve) . slice . map read . words where
  slice (0:0:_) = []
  slice (n:r:xs) = (n,take r $ map (take 2) $ iterate (drop 2) xs):
                   (slice $ drop (r*2) xs)

solve (n,cut) = head $ foldl proc [n,n-1..1] cut where
  proc ls [p,c] = (take c $ drop (p-1) ls) ++ (take (p-1) ls) ++ (drop (p-1+c) ls)

あんまり長さ変わらないけど。