4373 - 금융 쓰나미

• Submit
• Status
• Discuss
• Summary

Description

전 세계 은행들은 서로 돈을 빌려주고 받아 왔습니다. 그러다 경제적으로 힘든 시기에는 은행이라도 파산할 수 있는데, 파산한 은행에 대출된 금액은 누구도 돌려 받을 수 없습니다. 은행의 총 자산은 현재 자산 + 다른 은행에 대출해준 자산으로 계산합니다(이 때 자은행에 대출한 것도 포함합니다). 아래 그림에는 문제의 다섯 은행이 보입니다. 이들 은행의 현재 자산은 25, 125, 175, 75, 181백만$ 입니다. 그림에서 보여지는 노드1에서 노드2로의 직선은, 은행1이 은행2에게 40백만$를 대출해 주었음을 나타냅니다.  

Banks lend money to each other. In tough economic times, if a bank goes bankrupt, it may not be able to pay back the loan. A bank’s total assets are its current balance plus its loans to other banks. The diagram in Figure 8.8 shows five banks. The banks’ current balances are 25, 125, 175, 75, and 181 million dollars, respectively. The directed edge from node 1 to node 2 indicates that bank 1 lends 40 million dollars to bank 2.

만약 은행의 총 자산이 어떤 제한금액보다 낮아지게 되면, 은행은 불안전해 집니다. 또한 불안전해진 은행에 돈을 대출해준 은행들은 대출해준 금액만큼 총 자산이 낮아지게 됩니다. 결과적으로, 안전했던 은행이라도 연쇄적인 총 자산의 감소로 인해 불안전해 질 수 있습니다. 

여러분은 모든 불안전한 은행을 찾아내는 프로그램을 작성해야 합니다. 프로그램의 입력은 다음과 같습니다. 첫번째 줄은 은행의 수 N과 제한금액 L입니다. 그 다음 N개의 줄에는 각 은행의 자산 정보가 있습니다(은행의 번호는 0부터 N-1까지 입니다) . 각 은행의 자산 정보의 첫번째 항목은 현재 자산입니다. 두번째 항목은 대출해준 은행의 수 B 입니다. 다음 B개의 쌍은 대출 은행과 그 금액입니다.  예를 들어, 위 그림을 입력으로 변환하면 다음과 같습니다. (L은 201로 가정합니다)

If a bank’s total assets are under a certain limit, the bank is unsafe. The money it borrowed cannot be returned to the lender, and the lender cannot count the loan in its total assets. Consequently, the lender may also be unsafe, if its total assets are under the limit. Write a program to find all the unsafe banks. Your program reads the input as follows. It first reads two integers N and limit L, where N indicates the number of banks and L is the minimum total assets for keeping a bank safe. It then reads N lines that describe the information for N banks with IDs from 0 to N-1. The first number in the line is the bank’s balance, the second number indicates the number B of banks that borrowed money from the bank, and the rest are pairs of two numbers. Each pair describes a borrower. The first number in the pair is the borrower’s ID and the second is the amount borrowed. For example, the input for the five banks in Figure 8.8 is as follows (note that the limit is 201): 

5 201
25 2 1 100.5 4 320.5
125 2 2 40 3 85
175 2 0 125 3 75
75 1 0 125
181 1 2 125

은행3의 총자산은 75+125=200 이고 201(=L)보다 작으므로, 불안전한 은행입니다. 은행3이 불안전해 졌으므로, 은행1의 총자산은 125+40=165로 감소되고, 마찬가지로 불안전한 은행이 됩니다. 따라서 프로그램은 불안전한 은행으로 은행3과 은행1을 찾아낼 수 있어야 합니다.

The total assets of bank 3 are (75 + 125), which is under 201, so bank 3 is unsafe. After bank 3 becomes unsafe, the total assets of bank 1 fall below (125 + 40). Thus, bank 1 is also unsafe. The output of the program should be Unsafe banks are 3 1

Input

* Line 1 : 은행의수N 제한금액L (N:1~100범위의 정수)

* Line 2~N+1 : 현재자산 대출해준은행수B {대출은행 대출금액}*B

- 제한금액, 현재자산, 대출금액은 1~1,000 범위의 실수

 

Output

* Line 1 : 불안전한 은행의 번호를 오름차순으로 공백으로 구분해 출력

Sample Input

5 201
25 2 1 100.5 4 320.5
125 2 2 40 3 85
175 2 0 125 3 75
75 1 0 125
181 1 2 125

Sample Output

1 3

Hint

Use a two-dimensional array borrowers to represent loans. borrowers[i][j] indicates the loan that bank i loans to bank j. Once bank j becomes unsafe, borrowers[i][j] should be set to 0.

Source

JAVA2015 PE8.17