환율 차익 거래
골드 II의견: 0
국제 환전소에 \(N\)종의 통화가 있다. \(M\)개의 단방향 환전 경로가 있고, 각 경로는 통화 \(u\)를 \(\frac{p}{q}\) 배의 환율로 통화 \(v\)로 바꿀 수 있음을 뜻한다. 즉, 통화 \(u\) \(1\)원을 통화 \(v\) \(\frac{p}{q}\)원으로 교환한다.
차익 거래(arbitrage)란 어떤 통화에서 시작하여 여러 번 환전을 거친 뒤 다시 같은 통화로 돌아왔을 때, 돈이 엄격히 늘어나는 경우를 말한다. 즉, 환전 사이클의 환율 곱이 \(1\)보다 크면 차익 거래가 가능하다.
차익 거래가 가능하면 YES, 불가능하면 NO를 출력하여라.
- \(1 \le N \le 50\)
- \(0 \le M \le N(N-1)\)
- \(1 \le u, v \le N\), \(u \ne v\)
- \(1 \le p, q \le 10^4\)
- 동일한 방향의 환전 경로는 최대 한 개이다.
첫째 줄에 통화 수 \(N\)과 환전 경로 수 \(M\)이 주어진다.
다음 \(M\)개의 줄에 환전 경로의 출발 통화 \(u\), 도착 통화 \(v\), 환율의 분자 \(p\)와 분모 \(q\)가 공백으로 구분되어 주어진다.
차익 거래가 가능하면 YES, 불가능하면 NO를 출력한다.
3 3
1 2 6 5
2 3 9 10
3 1 1 1
YES
통화 \(1\to2\to3\to1\)로 교환하면 환율 곱이 \(\frac{6}{5}\times\frac{9}{10}\times\frac{1}{1}=\frac{54}{50}>1\)이므로 차익 거래가 가능하다.
3 3
1 2 2 3
2 3 3 4
3 1 1 1
NO
가능한 모든 사이클에서 환율 곱이 \(1\) 이하이므로 차익 거래가 불가능하다.
riseoj 작성
출처 Original
평가 및 의견
환율 차익 거래
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
환율 차익 거래