백준 11070 - 피타고라스 기댓값

문제

유명한 피타고라스의 정리와 유사한 형태의 피타고라스 기댓값 (Pythagorean Expectation)이 야구와 같은 스포츠 경기에 자주 사용된다. 피타고라스 기댓값은 빌 제임스(Bill James)에 의해 정의되었으며, 이 값은 특정 야구팀이 한 시즌 동안 얼마나 잘 했는지를 평가하는 지표 중 하나로 사용된다. 한 야구팀의 피타고라스 기댓값 𝑊\(W\)는 아래 식과 같이 정의된다.

 𝑊=𝑆2𝑆2+𝐴2\(W = \dfrac{S^2}{S^2 + A^2}\),

여기서 𝑆\(S\)는 해당 팀의 총 득점 수를, 𝐴\(A\)는 해당 팀의 총 실점 수를 나타낸다.

이 기댓값을 실제 승률과 비교하여, 해당 팀이 한 시즌을 얼마나 잘 보냈는지 평가할 수 있다. 예를 들어, 한화 이글스는 2014 시즌에 619 득점과 889 실점을 했다. 즉, 𝑆\(S\) = 619, 𝐴\(A\) = 889이 되어, 한화 팀의 피타고라스 기댓값은 𝑊\(W\) = 6192/(6192 + 8892) = 0.326이 된다. KBO 규정에 따르면, 한 시즌당 한 팀은 128번의 경기를 해야 하므로, 한화는 0.326 ×128 = 41.728 경기에서는 승리했어야 한다. 실제 한화는 49경기에서 승리했기 때문에, 2014 시즌을 그리 나쁘지 않게 보냈음을 알 수 있다. 반면에 롯데 자이언츠는 𝑆\(S\) = 715이고, 𝐴\(A\) = 719이 되어, 𝑊\(W\) = 0.497이 된다. 따라서 0.497 ×128 = 63.616경기 이상을 이길 것으로 기대되었지만, 실제론 58경기만 승리했다. 결국, 롯데에게 2014년은 기대에 많이 못 미친 시즌이었음을 알 수 있다.

 𝑛\(n\)개의 팀에 대한 기록이 주어지면, 이 기록으로부터 팀 별 피타고라스 기댓값을 계산한 후, 그 중 최대 기댓값과 최소 기댓값을 출력하는 프로그램을 작성하시오.

입력

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 줄에는 두 양의 정수 𝑛\(n\) (2 ≤ 𝑛\(n\) ≤ 1,000)과 𝑚\(m\) (2 ≤ 𝑚\(m\) ≤ 1,000)이 주어진다. 여기서, 𝑛\(n\)은 팀 개수이며, 𝑚\(m\)은 전체 경기 수이다. 다음의 𝑚\(m\)개의 줄에는 각 경기에 대한 정보가 주어진다. 하나의 경기는 네 개의 정수 𝑎\(a\), 𝑏\(b\), 𝑝\(p\), 𝑞\(q\)로 주어지는데, 팀 a와 팀 b가 경기를 했고, 팀 a는 p득점을 팀 b는 q득점을 했다는 의미이다. 여기서, 1 ≤ 𝑎\(a\) ≠ 𝑏\(b\) ≤ 𝑛\(n\)이며, 𝑝\(p\)와 𝑞\(q\)는 모두 음이 아닌 20 이하의 정수이다. 하나의 테스트 데이터에서 팀 당 경기수가 반드시 같을 필요는 없다. 만약, 어떤 팀의 총 득점과 총 실점이 모두 0이라면, 그 팀의 기댓값은 0으로 정의한다.

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 두 정수 값을 한 줄에 하나씩 출력해야 한다. 첫 번째 줄에는 최대 피타고라스 기댓값에 1,000을 곱한 값의 정수부분을 출력하고, 두 번째 줄에는 최소 피타고라스 기댓값에 1,000을 곱한 값의 정수부분을 출력한다.

예제 입력 1 복사

2
3 5
1 2 3 5
1 3 10 1
1 2 0 7
2 3 9 3
3 2 4 5
4 6
1 2 0 11
1 3 17 13
1 4 17 1
2 3 7 12
2 4 19 17
3 4 17 0

예제 출력 1 복사

871
100
753
103

 

#백준/브1/피타고라스 기댓값


for _ in range(int(input())):
    n,m = map(int,input().split())
    
    expectation_positive = [0 for _ in range(n+1)]
    expectation_negative = [0 for _ in range(n+1)]
    expectation_all = [0 for _ in range(n+1)]
    
    for i in range(m):
        a,b,p,q = map(int, input().split())
        
        expectation_positive[a] += p
        expectation_negative[a] += q
        
        expectation_positive[b] += q
        expectation_negative[b] += p

    for j in range(1,n+1):
        if expectation_negative[j] == 0 and expectation_positive[j] == 0:
            expectation_all[j] = 0
        else:
            expectation_all[j] = expectation_positive[j]**2 / (expectation_positive[j]**2 + expectation_negative[j]**2)
    
    print(int(max(expectation_all[1:]) * 1000))
    print(int(min(expectation_all[1:]) * 1000))

 

 

reference

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