Auction

#!/usr/bin/env python
import os, sys

def time_function(func):
    def wrapped_func(*args, **kwargs):
        from time import time
        start = time()
        res = func(*args, **kwargs)
        sys.stderr.write('%s took %.6fs\n' % (func.__name__, time() - start))
        return res
    return wrapped_func

class Auction(object):
    @time_function
    def __init__(self, n, p1, w1, m, k, a, b, c, d):
        self.n = n
        self.p_head, self.p_tail, self.p_lookup = self.gen_func(a, b, p1, m)
        self.w_head, self.w_tail, self.w_lookup = self.gen_func(c, d, w1, k)
        self.p_total = self.p_head + self.p_tail
        self.w_total = self.w_head + self.w_tail
        self._p_head = len(self.p_head)
        self._p_tail = len(self.p_tail)
        self._w_head = len(self.w_head)
        self._w_tail = len(self.w_tail)
        self._gcd = self.gcd(self._p_tail, self._w_tail)
        self._period = (self._p_tail * self._w_tail)/self._gcd
        self.w_total.sort()
        self.p_total.sort()
        self.w_s_lookup = dict((v, i) for i, v in enumerate(self.w_total))
        self.p_s_lookup = dict((v, i) for i, v in enumerate(self.p_total))

    def gen_func(self, a, b, p0, m):
        p = [p0]
        __p  = { p0 : 0 }
        p_pattern = 0
        i = 1
        b = b % m
        a = a % m
        while i < self.n:
            p_n = ((a * p[i-1] + b) % m) + 1
            if p_n in __p:
                p_pattern = __p[p_n]
                break
            p.append(p_n)
            __p[p_n] = i
            i += 1
        return p[:p_pattern], p[p_pattern:], __p


    def gcd(self, a, b):
        b, a = min(a, b), max(a, b)
        if b == 0:
            return a
        return self.gcd(b, a % b)

    @time_function
    def get_deals(self):
        min_p, max_p = 0, len(self.p_total) - 1
        min_w, max_w = 0, len(self.w_total) - 1
        bargains = 0

        while max_p >= min_p and max_w >= min_w:
            if max_p - min_p <= max_w - min_w:
                p = self.p_total[min_p]
                w, c = self.get_w(p, min)
                if self.w_s_lookup[w] <= max_w:
                    bargains += c
                    w_pos = self.w_s_lookup[w]
                    if w_pos == 0:
                        break
                    max_w = w_pos - 1
                min_p += 1
            else:
                w = self.w_total[min_w]
                p, c = self.get_p(w, min)
                if self.p_s_lookup[p] <= max_p:
                    bargains += c
                    p_pos = self.p_s_lookup[p]
                    if p_pos == 0:
                        break
                    max_p = p_pos - 1
                min_w += 1

        min_p, max_p = 0, len(self.p_total) - 1
        min_w, max_w = 0, len(self.w_total) - 1
        terrible = 0

        while max_p >= min_p and max_w >= min_w:
            if max_p - min_p <= max_w - min_w:
                p = self.p_total[max_p]
                w, c = self.get_w(p, max)
                if self.w_s_lookup[w] >= min_w:
                    terrible += c
                    w_pos = self.w_s_lookup[w]
                    min_w = w_pos + 1
                max_p -= 1
            else:
                w = self.w_total[max_w]
                p, c = self.get_p(w, max)
                if self.p_s_lookup[p] >= min_p:
                    terrible += c
                    p_pos = self.p_s_lookup[p]
                    min_p = p_pos + 1
                max_w -= 1
        return terrible,bargains

    def get_w(self, p, func):
        pos_p = self.p_lookup[p]

        if pos_p < self._p_head:
            return self.get_w_for_pos(pos_p), 1
        i = 0
        ws = []
        lp = (self._w_head + self._period)/self._p_tail
        while i < lp:
            if pos_p + i * self._p_tail >= self.n:
                break
            ws.append((self.get_w_for_pos(pos_p + i * self._p_tail), pos_p + i * self._p_tail))
            i += 1
        w, pos = func(ws)
        if pos < self._w_head:
            return w, 1

        c = (self.n - pos)/self._period
        if (self.n - pos) % self._period > 0:
            c += 1
        return w, c

    def get_w_for_pos(self, pos):
        if pos < self._w_head:
            return self.w_head[pos]
        return self.w_tail[(pos - self._w_head) % self._w_tail]

    def get_p(self, w, func):
        pos_w = self.w_lookup[w]

        if pos_w < self._w_head:
            return self.get_p_for_pos(pos_w), 1
        i = 0
        ps = []
        lp = (self._p_head + self._period)/self._w_tail
        while i < lp:
            if pos_w + i * self._w_tail >= self.n:
                break
            ps.append((self.get_p_for_pos(pos_w + i * self._w_tail), pos_w + i * self._w_tail))
            i += 1
        p, pos = func(ps)
        if pos < self._p_head:
            return p, 1

        c = (self.n - pos)/self._period
        if (self.n - pos) % self._period > 0:
            c += 1
        return p, c

    def get_p_for_pos(self, pos):
        if pos < self._p_head:
            return self.p_head[pos]
        return self.p_tail[(pos - self._p_head) % self._p_tail]

def get_solution(q, i, args):
    result = Auction(*args).get_deals()
    q.put((i, result))

@time_function
def main(args):
    input_file = open(os.path.join(os.path.dirname(__file__), args[0]))
    n = int(input_file.readline().strip())
    output_file = open(os.path.join(os.path.dirname(__file__), 'output.txt'), 'w')
    for i in range(1, n + 1):
        data = map(int, input_file.readline().strip().split(' '))
        b, t = Auction(*data).get_deals()
        output_file.write('Case #%d: %d %d\n' % (i,b,t))
    output_file.close()
    input_file.close()

if __name__ == '__main__':
    from doctest import testmod
    print testmod()
    main(sys.argv[1:])