Submission #152180

---

Source Code Expand

#!/usr/bin/env python2.7

import sys
from collections import namedtuple, defaultdict

from cStringIO import StringIO
import unittest
import cProfile

def main():
    n, c = (int(x) for x in sys.stdin.readline().split())
    a = list()
    for _ in range(n):
        ai, = (int(x) for x in sys.stdin.readline().split())
        a.append(ai)
    print solve(c, a)

def solve(c, a):
    ao = a[0::2]
    ae = a[1::2]
    do = defaultdict(int)
    de = defaultdict(int)
    for d in ao:
        do[d] += 1
    for d in ae:
        de[d] += 1

    maxo = max(do.values())
    maxoc = set([x for x, s in do.items() if s == maxo])
    maxe = max(de.values())
    maxec = set([x for x, s in de.items() if s == maxe])

    if len(maxoc.symmetric_difference(maxec)) != 0:
        return c * (len(ao) - maxo + len(ae) - maxe)

    maxon = max([s for s in do.values() if s != maxo] + [0])
    maxen = max([s for s in de.values() if s != maxe] + [0])

    r1 = c * (len(ao) - maxon + len(ae) - maxe)
    r2 = c * (len(ao) - maxo + len(ae) - maxen)
    return min([r1, r2])

    
class Test(unittest.TestCase):

    @staticmethod
    def tryone(indata):
        sys.stdin = StringIO(indata)
        out = sys.stdout = StringIO()
        main()
        return out.getvalue()

    def test50(self):
        self.assertEqual(solve(10, [3, 2, 1]), 10)
        self.assertEqual(solve(100, [1,1,1,1]), 200)
        self.assertEqual(solve(1000, list(range(1,11))), 8000)

    def test60(self):
        self.assertEqual(solve(10, [1, 1, 1]), 10)
        self.assertEqual(solve(10, [1, 2, 1]), 0)
        self.assertEqual(solve(10, [1, 1, 1, 1, 1]), 20)

    def test90(self):
        self.assertEqual(self.tryone("""\
3 10
3
2
1
"""), """10\n""")

if __name__ == '__main__':
    if len(sys.argv) > 1:
        print "_/" * 30 + str(sys.argv)
        if sys.argv[1] == '-p':
            sys.argv.pop(1)
            cProfile.run("unittest.main(exit=False, failfast=True)", sort='time')
        else:
            unittest.main()
    else:
        main()

Submission Info

Judge Result