GoogleCodeJamJapan2011 予選 問題C.ビット数

GoogleCodeJamJapan2011problemClarge.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from problemC import process as correct

def file_open(filename):
    T = 0
    caseList = []
    with open(filename) as f:
        T = int(f.readline().strip())
        for i in range(T):
            line = f.readline().strip()
            caseList.append(int(line))
    return caseList

def count1in2bit(num):
    """
    >>> count1in2bit(100)
    3
    >>> count1in2bit(4)
    1
    >>> count1in2bit(1)
    1
    >>> count1in2bit(3000)
    7
    """
    count = 0
    while(num):
        count += (num & 1)
        num >>= 1
    return count

def _test():
    import doctest
    doctest.testmod()

def process(num):
    """
    >>> process(1125899906842624)
    51
    >>> process(255)
    8
    >>> process(8467)
    16
    >>> process(8847)
    16
    >>> process(8411)
    18
    >>> process(8370)
    18
    >>> process(9081)
    20
    """
    numInBin = bin(num)[2:]
    carry = False
    bitcount = 0
    for i in xrange(len(numInBin) -1, -1, -1):
        if numInBin[i] == '0':
            if carry:
                bitcount += 1
                carry = True
            else:
                bitcount += 2
                carry = True
        else:
            if carry:
                if not i == 0:
                    bitcount += 2
                    carry = True
            else:
                bitcount += 1
    return bitcount

def main():
    FILENAME = "./C-large.in"
    TestList = file_open(FILENAME)
    f = open("outputClarge.txt", "w")
    count = 0
    for i in TestList:
        count += 1
        result = process(i)
        f.write("Case #" + str(count) + ": " + str(result) + "\n")
    f.close()

if __name__ == "__main__":
    #_test()
    main()

GoogleCodeJapan2011problemCsmall.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def file_open(filename):
    T = 0
    caseList = []
    with open(filename) as f:
        T = int(f.readline().strip())
        for i in range(T):
            line = f.readline().strip()
            caseList.append(int(line))
    return caseList

def count1in2bit(num):
    """
    >>> count1in2bit(100)
    3
    >>> count1in2bit(4)
    1
    >>> count1in2bit(1)
    1
    >>> count1in2bit(3000)
    7
    """
    count = 0
    while(num):
        count += (num & 1)
        num >>= 1
    return count

def _test():
    import doctest
    doctest.testmod()

def process(num):
    """
    >>> process(1)
    1
    >>> process(4)
    3
    >>> process(31)
    5
    """
    output = 0
    for i in xrange(1, num/ 2 + 2):
        result = count1in2bit(i) + count1in2bit(num - i)
        if result > output:
            output = result
            print str(output) + " pair of " + str(i) + " & " + str(num - i)
    return output

def main():
    FILENAME = "./C-small-attempt0.in"
    TestList = file_open(FILENAME)
    f = open("outputC.txt", "w")
    count = 0
    for i in TestList:
        count += 1
        result = process(i)
        f.write("Case #" + str(count) + ": " + str(result) + "\n")
    f.close()

if __name__ == "__main__":
    #_test()
    main()