[URI Online Judge] – 1105 – Sub-prime

The most recent economic crisis was partly caused by the manner in which banks made loans to people unable to repay them and resold such loans to other banks as debentures. Obviously, when people failed to repay their loans, the whole system collapsed.

The crisis was so deep that it affected countries all over the world, including Nlogonia, where the honored prime minister Man Dashuva ordered the Central Bank chairman to come up with a solution. He came up with a brilliant idea: if all banks could liquidate its debentures only with its own monetary reserves, all banks would survive and the crisis would be averted.

However, with the elevated number of debentures and banks involved, this was an extremely complicated task, so he asked for your help in writing a program that, given the banks and the debentures printed by them, determines if it is possible that all banks pay back their debts using only their monetary reserves and credits.

Input

The input consists of several test cases. The first line of each test case contains two integers B and N, indicating the number of banks (1 ≤ B ≤ 20) and the number of debentures printed by the banks (1 ≤ N ≤ 20). The banks are identified by integers between 1 and B. The second line contains B integers Riseparated by spaces, indicating the monetary reserves of each one of the B banks (0 ≤ Ri ≤ 104, for 1 ≤ i ≤ B). The N following lines contain each one three integers separated by spaces: an integer D, indicating the debtor bank (1 ≤ D ≤ B), an integer C , indicating the creditor bank (1 ≤ C ≤ B e D ≠ C) and an integer V, indicating the debenture value (1 ≤ V ≤ 104).

The end of input is indicated by a line containing only two zeros, separated by spaces.

Output

For each test case, your program should print a single line, containing a single character: ‘S’, if it is possible to liquidate all debentures without a bailout from the Central Bank of Nlogonia, or ‘N’ if a bailout is necessary.

Sample Input Sample Output
3 3

1 1 1
1 2 1
2 3 2
3 1 3
3 3
1 1 1
1 2 1
2 3 2
3 1 4
3 3
1 1 1
1 2 2
2 3 2
3 1 2
0 0

S

N

S

Solution:

#include <iostream>

using namespace std;

struct Bank{
int owe_to;
int owe_value;
int reserve;
};

int main(){
int r, b, n, i, d, c, v;
bool liquidated;

while (cin >> b >> n && b != 0 && n != 0){
Bank banks[b + 1];
liquidated = true;

for (i = 1; i <= b; i++){
cin >> r;

Bank bank;
bank.reserve = r;
banks[i] = bank;
}
while (n–){
cin >> d >> c >> v;
banks[d].owe_to = c;
banks[d].owe_value = v;
banks[c].reserve += v;
banks[d].reserve -= v;
banks[d].owe_value -= v;
}
for (i = 1; i <= b; i++){
if (banks[i].reserve < 0) {
liquidated = false;
break;
}
}
if (liquidated) cout << “S” << endl;
else cout << “N” << endl;
}
return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s