Settle Group Trip Expenses

Problem: Settle Group Trip Expenses A group of friends went on a trip together. You are given a list of transactions. Each transaction contains: payer: the person who paid the money; amount: the amount paid, in cents, as an integer; payees: the list of people who should share this expense. The payer may also appear in this list. For each transaction, the amount is split equally among all people in payees. Your task is to output a list of money transfers that settles all balances. In other words: If someone paid more than their fair share, they should receive money; If someone paid less than their fair share, they should pay money; Output transfers in the form: who pays whom and how much. The order of transfers does not matter. You do not need to minimize the number of transfers. Any valid settlement is acceptable. Input Format The first line contains an integer n, the number of transactions. Each of the next n lines has the following format: payer amount k payee1 payee2 ... payeeK where: payer is the person who paid; amount is the amount paid, in cents; k is the number of people sharing this expense; the next k strings are the names of those people. It is guaranteed that amount is divisible by k for every transaction. Output Format Print an integer m, the number of settlement transfers. Then print m lines, each in the format: debtor creditor amount meaning debtor should pay creditor the given amount. If everything is already settled, print: 0 Constraints 1 <= n <= 10^5 For each transaction, 1 <= k <= 100 1 <= amount <= 10^9 Names contain only English letters and have length at most 30 Each amount is divisible by the corresponding k The total number of payees across all transactions is at most 2 * 10^5 Example 1 Input: 2 Alice 4000 4 Bob Alice Charlie Daisy Charlie 2000 2 Alice Charlie One valid output: 2 Daisy Alice 1000 Bob Charlie 1000 Explanation: In the first transaction, Alice paid 4000, shared by Bob, Alice, Charlie, and Daisy. Each person owes 1000. In the second transaction, Charlie paid 2000, shared by Alice and Charlie. Each person owes 1000. Final balances: Alice is owed 2000; Charlie is owed 1000; Bob owes 1000; Daisy owes 1000. Therefore Bob and Daisy each need to pay 1000 to settle the expenses. Example Input 2 Alice 4000 4 Bob Alice Charlie Daisy Charlie 2000 2 Alice Charlie Output 2 Bob Alice 1000 Daisy Alice 1000