BOJ - 9873 - Cow Baseball

Updated:

import sys

def binarySearch(arr, V, N):
    low = 0
    high = N

    while low < high:
        mid = (low + high) // 2
        if (arr[mid] < V): low = mid + 1
        else: high = mid
    return low

def numInRange(arr, a, b, N):
    return binarySearch(arr, b + 1, N) - binarySearch(arr, a, N)

def solution():
    answer = 0
    N = int(sys.stdin.readline())
    arr = [0] * (N+1)
    for i in range(N):
        arr[i] = int(sys.stdin.readline())

    arr[N] = 1e9
    arr.sort()

    for i in range(N):
        for j in range(i+1, N):
            diff = arr[j] - arr[i]
            answer += numInRange(arr, arr[j] + diff, arr[j] + 2 * diff, N)

    print(answer)

solution()

https://www.acmicpc.net/problem/9873

Categories:

Updated:

Leave a comment