시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 16 MB | 553 | 227 | 47 | 24.103% |
0 부터 N - 1 까지 번호가 부여된 N 개의 정점을 가진 완전그래프가 있다.
각 정점 i 는 어떤 값 Xi 를 가지고 있다.
번호의 크기 관계가 i < j 를 만족하는 두 정점 i 와 j 사이를 연결하는 양방향 간선의 가중치 dist(i, j) 는 다음과 같이 계산된다.
dist(i, j) = ((Xi × A + Xj × B) % C) ^ D
여기서 A, B, C, D 는 상수이고, % 는 나눗셈의 나머지 연산, ^ 는 bitwise XOR 연산을 의미한다.
주어진 그래프의 최소 신장 트리 (MST) 의 가중치를 구해보자.
첫 번째 줄에는 정점의 개수 N 이 주어진다.
두 번째 줄에는 4 개의 정수 A, B, C, D 가 차례대로 주어진다.
세 번째 줄에는 N 개의 정수가 주어진다. 이는 Xi 가 0 번 정점부터 시작해서 N-1 번까지 순서대로 주어진 것이다.
입력으로 주어지는 모든 수는 제약사항의 범위를 만족하는 정수이며, 각 수는 공백으로 구분된다.
최소 신장 트리의 가중치를 출력한다.
5 76 98 73 42 3 2 13 16 7
18
7 687616258876 548342706698 598924357642 479342226273 474585935261 621191507020 781184643570 736346504107 987108549969 385099936705 997944222071
779662173222
시간 / 메모리 제한으로 인해 C/C++ 와 Java11, 그리고 PyPy3 이외의 언어로는 정해로도 정답을 받을 수 있는 것이 보장되지 않는다.