m00nlight

import sys
import itertools

def sieve(n):
    is_prime = [True] * (n + 1)
    prime_list = []
    
    is_prime[0] = is_prime[1] = False
    prime_list.append(2)
    

m00nlight

import sys
from heapq import heappush, heappop

class UFSet:
    def __init__(self, n):
        self.fa = [i for i in range(n)]
        
    def find(self, v):
        if v != self.fa[v]:
            self.fa[v] = self.find(self.fa[v])

m00nlight

def lower_bound(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) / 2
        if nums[mid] >= target:
            r = mid - 1
        else:
            l = mid + 1
    return l
    

m00nlight

from Queue import Queue
from threading import Thread
from random import randrange

queue = Queue(10)

class Consumer(Thread):
    def __init__(self, queue):
        Thread.__init__(self)
        self.queue = queue

m00nlight

def count_sort(A, K):
    """ A is positive integer array each element is in range [0, K]"""
    count = [0] * (K + 1)
    for a in A:
        count[a] += 1
    
    for i in range(1, K + 1):
        count[i] = count[i - 1] + count[i]
        
    B = [None] * len(A)

m00nlight

def knuth_shuffle(items):
    """
    Fisher-Yates shuffle or Knuth shuffle which name is more famous.
    See <http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle> for detail
    Type : [a] -> None (shuffle inplace)
    Post constrain: Should be list 
    Post constrain: return array of the same length of input
    """

    for i in range(len(items)):

m00nlight

from random import randrange

def reservoir_sampling(items, k):
    """ 
    Reservoir sampling algorithm for large sample space or unknow end list
    See <http://en.wikipedia.org/wiki/Reservoir_sampling> for detail>
    Type: ([a] * Int) -> [a]
    Prev constrain: k is positive and items at least of k items
    Post constrain: the length of return array is k
    """

m00nlight

def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    else:
        less = filter(lambda x: x <= nums[0], nums[1:])
        large = filter(lambda x: x > nums[0], nums[1:])
        return quick_sort(less) + [nums[0]] + quick_sort(large)

m00nlight

;                    Quick miniKanren-like code 
;
; written at the meeting of a Functional Programming Group
; (Toukyou/Shibuya, Apr 29, 2006), as a quick illustration of logic
; programming.  The code is really quite trivial and unsophisticated:
; it was written without any preparation whatsoever. The present file
; adds comments and makes minor adjustments.
;
; $Id: sokuza-kanren.scm,v 1.1 2006/05/10 23:12:41 oleg Exp oleg $

m00nlight

class RadixSort:
    def radix_sort(self, nums):
        """
        Input an number list and return an sortd list
        Type: [Int] -> [Int]
        """
        max_len = max(map(lambda x: len(str(x)), nums))
        
        tmp, base = 1, 10
        for i in range(max_len):