Counting Haybales

USACO 2016 December Contest, Silver¶

Problem 1. Counting Haybales¶

http://www.usaco.org/index.php?page=viewproblem2&cpid=666

In [1]:

# """
# ID: karihee1
# LANG: PYTHON3
# TASK: haybales
# """

In [2]:

# return index of the first value in Alist that is >= v

def binSearch(Alist, v):
    if Alist[0] >= v:
        return 0
    # Alist[low] < v
    low = 0                   
    high = len(Alist)-1
    if Alist[high] <= v:      
        return high+1
    # Alist[high] > v

    while low<high:
        mid = (low+high)//2   # floor division
        if Alist[mid] <= v:
            low=mid+1
        else:
            high = mid

    return low

In [3]:

# fin = open ('haybales.in','r')
# fout = open('haybales.out','w')

# N,Q = map(int, fin.readline().split())
# hayList=list(map(int,fin.readline().split()))

N,Q = 4,6
hayList = [3, 2, 7, 5]
hayList.sort()

InputData = [(2,3),(2,4),(2,5),(2,7),(4,6),(8,10)]

for a,b in InputData:
    print(binSearch(hayList,b)-binSearch(hayList,a-1))
    

# for i in range(Q):
#     a,b = map(int,fin.readline().split())
#     fout.write(str(binSearch(hayList,b)-binSearch(hayList,a-1))+'\n')
#      
# fout.close()

2
2
3
4
1
0