頁面無法載入？點擊這裡可能會修復。
Placeholder

#8095

반복퀘스트 1s 32MB

問題

RPG게임 반복퀘스트는 말그대로 반복퀘스트를 주구장창 깨야하는 게임으로, 최종 승리 목표는 메인퀘스트를 깨는 것이다.

메인퀘스트를 깨기 위해서는 특정 반복퀘스트들을 임의의 개수만큼 깨야하는데, 그런 반복퀘스트를 깨기 위해서는 또 다른 반복퀘스트를 깨야하는 경우도 있다.

예를 들어보자. 메인퀘스트를 깨기 위해서는 1번 반복퀘스트를 3번 깨야하고, 2번 반복퀘스트를 2번 깨야한다.

1번 반복퀘스트는 3번 반복퀘스트를 2번 깨면 된다. 

그리고 2번 반복퀘스트는 3번 반복퀘스트를 1번 깨고, 4번 반복퀘스트를 5번 깨야한다.

마지막으로 3번 반복퀘스트는 4번 반복퀘스트를 1번, 6번 반복퀘스트를 4번 깨면 된다.

이런 경우에 메인퀘스트를 깨기위해 각 반복퀘스트를 1번: 3번, 2번: 2번, 3번: 8번, 4번: 18번, 6번: 32번 깨야한다.

이와 같이 각 퀘스트간의 관계가 주어져 있을 때 메인퀘스트를 깨기 위하여 필요한 반복퀘스트의 번호별 깨야하는 횟수를 계산하는 프로그램을 작성하시오.


輸入

첫 줄에 메인 퀘스트를 깨기 위해 필요한 반복퀘스트의 종류의 수 N(2≤N≤10)이 주어지고, 그 다음 N개의 줄에는 두 정수 Y\ K가 주어진다. 이 뜻은 "메인퀘스트를 깨기 위해 Y번 반복퀘스트를 K번 깨야한다"는 뜻이다. (1 \le Y, K \le 100)

이어서 다음 줄에 정수 M(3≤M≤100)이 주어지고, 그 다음 M개의 줄에는 반복퀘스트 간의 관계가 세 정수 X\ Y\ K로 주어진다. 이 뜻은 "X번 반복퀘스트를 깨기 위해 Y번 반복퀘스트를 K번 깨야한다"는 뜻이다. (1 \le X < Y \le 100; 1 \le K \le 100)


輸出

메인퀘스트를 깨기 위해 필요한 반복퀘스트의 번호별 깨야하는 횟수를 각 반복퀘스트의 번호의 오름차순으로 한 줄에 하나씩 퀘스트의 번호와 횟수를 공백으로 구분하여 출력한다. (반복퀘스트를 수행할 필요가 없는 경우는 출력하지 않는다)


範例 

2
1 3
2 2
5
1 3 2
2 3 1
2 4 5
3 4 1
3 6 4
1 3
2 2
3 8
4 18
6 32

  • 메인퀘스트:

    • 1번 반복퀘스트: 3번

    • 2번 반복퀘스트: 2번

  • 1번 반복퀘스트는 3번 반복퀘스트를 2번 필요로 하므로:

    • 1번: 3번 → 3번: 6번

  • 2번 반복퀘스트는 3번과 4번 반복퀘스트가 필요하며:

    • 2번: 2번 → 3번: 2번 + 4번: 10번 (3번은 1번 필요)

  • 3번 반복퀘스트는 4번과 6번이 필요:

    • 3번: 8번 → 4번: 8번 + 6번: 32번 (1번 필요)

  • 최종적으로, 반복퀘스트 수는:

    • 1번: 3번

    • 2번: 2번

    • 3번: 8번

    • 4번: 18번

    • 6번: 32번



來源

klee
需要登入才能撰寫程式碼。