[백준 21760번-파이썬] 야구 시즌

http://acmicpc.net/problem/21760

{코드}

for _ in range(int(input())):
    n, m, k, d = map(int, input().split())
    b = 2*d//(k*n*m*(m-1) + m*m*n*(n-1))
    if b:
        print(m*(m-1)*n*k*b//2 + m*m*n*(n-1)*b//2)
    else:
        print(-1)

{설명}

A와 B의 관계를 알고, k가 주어지기 때문에 다음과 같은 식이 성립합니다.

A*N*(M*(M-1))/2 + B*(N*(N-1))/2)*M*M <= D

여기서 A가 k*B이므로 위 식은 밑의 식과 같습니다.

N*M((M-1)*K + (N-1)*M)/2 * B <= D

왜 이런 식이 성립하냐면 먼저 지역 리그의 수는 N개 이며 하나의 지역 내에서 M개의 팀 중에서 2개를 고르기에 M*(M-1)이 되어 한 지역 리그 내의 수는 N*M*(M-1)가 됩니다.

다른 지역 리그와의 경기에서는 N개의 리그에서 두 개를 골라(N*(N-1)) 각 리그에서 한 팀을 고르므로 N*(N-1)*M*M이 됩니다.

여기에 각각 A와 B를 곱한 것이 D보다 작아야 하기에 위와 같은 식이 성립하는 것입니다.

그렇기에 B의 값을 한 번에 구할 수 있으며 만약 B가 0이하가 아니라면 구한 B를 통해 위 식을 계산할 값을 출력하면 되고 0 이하라면 -1을 출력하면 됩니다.