Emprunt – Épreuve régionale 2014

Énoncé¶

Joseph Marchand a besoin d'argent. Pour cela il va emprunter, le problème, c'est que tout le monde n'est pas prêt à lui donner. De plus, on va lui demander des intérêts, il a vraiment besoin d'argent, certes, mais il voudrait que ça lui coûte le moins cher possible.

Il y a N personnes dans le village de Joseph, par simplicité, nous les numéroterons de 0 à N-1 (Joseph étant le villageois numéro 0.) Chaque personne vous dit à qui elle est prête à donner de l'argent, quelle est la somme maximale qu'elle est prête à investir et quel pourcentage de la somme elle s'attend à recevoir. On vous donne également les sommes initiales dont dispose chaque villageois.

Ce qu'espère Joseph, c'est que bien que Lilith n'est pas prête à lui préter de l'argent, elle voudra bien en préter à Marie avec qui Joseph est en bon terme, il pourra ainsi emprunter plus (au risque de faire monter les intérêts.)

Déterminer la somme maximale que Joseph peut emprunter et pour cette somme, les intérêts minimum qu'il aura à payer.

Entrée¶

• Sur la première ligne, l'entier N, le nombre de personnes habitant le village de Joseph.
• Sur les N lignes suivantes, un entier I_i, la somme initiale que possède la personne i.
• Sur la ligne suivante, l'entier M, le nombre de prêts possibles entre habitants du village.
• Sur les M lignes suivantes, 4 entiers, l'identifiant du prêteur, l'identifiant du receveur, la somme maximale que le prêteur accepte de donner et le taux d'intérêt demandé.

Sortie¶

• Sur la première ligne, la somme empruntable par Joseph.
• Sur la seconde ligne, les intérêts qu'il devra payer.

Contraintes¶

• 1 <= N <= 100
• 0 <= M <= 1000