1 1.1 yamt {- 2 1.1 yamt /* $NetBSD: opt.hs,v 1.1 2006/10/09 12:32:46 yamt Exp $ */ 3 1.1 yamt 4 1.1 yamt /*- 5 1.1 yamt * Copyright (c)2006 YAMAMOTO Takashi, 6 1.1 yamt * All rights reserved. 7 1.1 yamt * 8 1.1 yamt * Redistribution and use in source and binary forms, with or without 9 1.1 yamt * modification, are permitted provided that the following conditions 10 1.1 yamt * are met: 11 1.1 yamt * 1. Redistributions of source code must retain the above copyright 12 1.1 yamt * notice, this list of conditions and the following disclaimer. 13 1.1 yamt * 2. Redistributions in binary form must reproduce the above copyright 14 1.1 yamt * notice, this list of conditions and the following disclaimer in the 15 1.1 yamt * documentation and/or other materials provided with the distribution. 16 1.1 yamt * 17 1.1 yamt * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18 1.1 yamt * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 1.1 yamt * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 1.1 yamt * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21 1.1 yamt * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 1.1 yamt * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 1.1 yamt * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 1.1 yamt * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 1.1 yamt * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 1.1 yamt * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 1.1 yamt * SUCH DAMAGE. 28 1.1 yamt */ 29 1.1 yamt -} 30 1.1 yamt 31 1.1 yamt import System.Environment 32 1.1 yamt import System.IO 33 1.1 yamt import List 34 1.1 yamt import Maybe 35 1.1 yamt import qualified Data.Set as Set 36 1.1 yamt 37 1.1 yamt ff s [] = head $ Set.elems s 38 1.1 yamt ff s (y:ys) = 39 1.1 yamt if Set.size s == 1 then head $ Set.elems s else 40 1.1 yamt if Set.member y s then 41 1.1 yamt ff (Set.delete y s) ys 42 1.1 yamt else 43 1.1 yamt ff s ys 44 1.1 yamt 45 1.1 yamt do_opt1 npg n q [] = (reverse n, q) 46 1.1 yamt do_opt1 npg n q rs@(r:rs2) = 47 1.1 yamt if Set.member r q then 48 1.1 yamt do_opt1 npg n q rs2 49 1.1 yamt else if Set.size q < npg then 50 1.1 yamt do_opt1 npg (r:n) (Set.insert r q) rs2 51 1.1 yamt else 52 1.1 yamt let 53 1.1 yamt c = ff q rs2 54 1.1 yamt nq = Set.delete c q 55 1.1 yamt in 56 1.1 yamt do_opt1 npg (r:n) (Set.insert r nq) rs2 57 1.1 yamt 58 1.1 yamt do_opt npg rs = fst $ do_opt1 npg [] Set.empty rs 59 1.1 yamt do_opt_dbg npg rs = do_opt1 npg [] Set.empty rs 60 1.1 yamt 61 1.1 yamt main = do 62 1.1 yamt xs <- getContents 63 1.1 yamt args <- getArgs 64 1.1 yamt let 65 1.1 yamt ls = lines xs 66 1.1 yamt npgs::Int 67 1.1 yamt npgs = read $ args !! 0 68 1.1 yamt pgs::[Int] 69 1.1 yamt pgs = map read ls 70 1.1 yamt mapM_ print $ do_opt npgs pgs 71
Indexes created Sun Sep 28 16:09:52 GMT 2025