結果

問題 No.1644 Eight Digits
コンテスト
ユーザー satou_a_man
提出日時 2021-08-13 22:03:20
言語 Haskell
(9.10.1)
結果
AC  
実行時間 14 ms / 1,000 ms
コード長 1,177 bytes
コンパイル時間 6,903 ms
コンパイル使用メモリ 171,648 KB
実行使用メモリ 8,704 KB
最終ジャッジ日時 2024-10-03 19:00:18
合計ジャッジ時間 8,577 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

-- permutation
prefixes :: [a] -> [[a]]
prefixes [] = [[]]
prefixes (x : xs) = [] : [ x : ys | ys <- prefixes xs]

suffixes :: [a] -> [[a]]
suffixes [] = [[]]
suffixes xs@(_ : xs') = xs : suffixes xs'

interleave :: a -> [a] -> [[a]]
interleave x ys = [pre ++ [x] ++ suf | (pre,suf) <- zip (prefixes ys) (suffixes ys)]

permutation :: [a] -> [[a]]
permutation [] = [[]]
permutation (x : xs) = [zs | ys <- permutation xs, zs <- interleave x ys]

digits :: Int -> [Int]
digits n
  | n < 10 = [n]
  | otherwise = (n `mod` 10) : digits (n `div` 10)

-- >>> digits 12345678
-- [8,7,6,5,4,3,2,1]
-- >>> permutation $ digits 123
-- [[3,2,1],[2,3,1],[2,1,3],[3,1,2],[1,3,2],[1,2,3]]
-- >>> length $ permutation $ digits 12345678
-- 40320
--

g :: [Int] -> Int
g [] = undefined
g [n] = n
g (n : ns) = n + 10 * g ns

digits2Int :: [Int] -> Int
digits2Int ns = g ns

-- >>> digits2Int $ digits 1234
-- 1234

f :: Int -> Int
f k = length [n | ds <- permutation $ digits 12345678, let n = digits2Int ds, n `mod` k == 0]

-- >>> f 69921
-- [78451362,31254687,82716543,42861573,85723146,72438156,38526471,54328617]
--


main :: IO ()
main = do
  k <- readLn :: IO Int
  putStrLn $ show $ f k
0