연습문제
[21년 재직자 대회 예선] 로드 밸런서 트래픽 예측
- 난이도
- Lv. 3
- 제출
- 151 명
- 참가자
- 33 명
- 정답률
- 20.77 %
- 지원 언어
-
CC++JavaPythonJavaScript
로그인 후 문제풀이가 가능합니다.
언어별 시간/메모리
언어 | 시간 | 메모리 |
---|---|---|
JavaScript | 4초 | 1024MB |
C | 2초 | 1024MB |
C++ | 2초 | 1024MB |
Java | 4초 | 1024MB |
Python | 4초 | 1024MB |
자율주행 기술은 현대 컴퓨팅의 여러 최첨단 기술에 의존하지만, 이것이 가능하게 하려면 자동차에서 할 수 없는 복잡한 계산과 실시간 도로 정보 확인 등을 중앙 서버에서 빠르고 신속하게 처리할 수 있어야 한다. 이를 위해서 흔히 사용되는 방법은 요청(request)을 처리하는 많은 워커 노드(worker node)들을 두고, 로드 밸런서(load balancer)가 이들 워커 노드에 트래픽을 적절히 분산시키는 것이다. 즉 쉽게 설명하자면, 요청(request)이 들어오면 로드 밸런서가 워커 노드에 적절히 분배 해준다고 생각하면 된다.
현재 총 N개의 서버가 있다. 로드 밸런서와 워커 노드 모두 서버라 지칭하며, 하나의 서버가 로드 밸런서이면서 동시에 워커 노드일 수는 없다. i (1 ≤ i ≤ N)번째 서버가 로드 밸런서라면 중복을 포함하여 ri개 서버로 트래픽을 분산한다. ri = 0이면 i번째 서버는 워커 노드로, 요청을 직접적으로 처리한다. ri > 0이라면, i번째 서버는 로드 밸런서로, 아래와 같은 라운드-로빈(Round-Robin) 방식으로 트래픽을 분산한다.
각각의 로드 밸런서에는 정수형 변수 xi가 있다. 처음에 xi = 1이다. 로드 밸런서로 요청이 하나 들어오면, pi, xi번 서버로 트래픽을 전달하고, xi의 값을 (xi mod ri)+1로 바꾼다. 1번 서버는 루트 로드 밸런서로, 모든 요청은 루트 로드 밸런서로만 들어온다. 주어진 트래픽 분산 규칙은 효율적인 분산이 가능하도록 아래 두 조건을 만족한다. 트래픽이 같은 로드 밸런서를 여러 번 거치지 않도록, i → pi, j 간선들로 구성된 그래프에서 사이클이 존재하지 않는다. 1번 서버에 무한히 많은 요청을 보낸다면 모든 서버로 요청이 적어도 1개 이상은 전달된다.
총 K개의 요청이 들어왔다고 할 때, 각 서버로 들어오는 요청의 개수가 몇 개인지를 구하는 프로그램을 작성하라.
제약조건
2 ≤ N ≤ 100,000
1 ≤ K ≤ 1018
r1 + r2 + ... + rN ≤ 500,000 이다.
모든 1 ≤ i ≤ N, 1 ≤ j ≤ ri에 대해, 1 ≤ pi, j ≤ N이다.
i → pi, j 간선들로 구성된 그래프에서 사이클이 존재하지 않는다.
1번 서버에 무한히 많은 요청을 보낸다면 모든 서버로 요청이 적어도 1개 이상은 전달된다.
입력형식
첫 번째 줄에 두 정수 N과 K가 공백 하나씩을 사이로 두고 주어진다. 다음 N개의 줄에 ri, pi, 1, pi, 2, ... , pi, rj가 공백 하나씩을 사이로 두고 주어진다.
출력형식
N개의 정수를 공백 하나씩을 사이로 두고 출력한다. i(1 ≤ i ≤ N)번째 정수는, i번 서버가 받는 요청의 개수이다.
입력예제1
8 6 3 2 5 8 0 0 0 3 2 4 3 0 0 2 6 7
출력예제1
6 3 0 1 2 1 1 2
로드밸런서의 구조는 아래와 같다.
6개의 요청이 아래와 같이 전달된다.
입력예제2
8 1005 3 2 5 8 0 0 0 3 2 4 3 0 0 2 6 7
출력예제2
1005 447 111 112 335 168 167 335