from abc import ABC, abstractmethod
from dataclasses import dataclass
from collections import defaultdict
import heapq
import itertools


@dataclass(frozen=True)
class Money:
    paise: int
    def __str__(self) -> str: return f"Rs {self.paise / 100:.2f}"


class SplitStrategy(ABC):
    """Returns {user: paise}, guaranteed to add up to exactly `total_paise`."""
    @abstractmethod
    def split(self, total_paise: int, participants: list[str], **kwargs) -> dict[str, int]: ...


class EqualSplit(SplitStrategy):
    def split(self, total_paise, participants, **kwargs):
        n = len(participants)
        if n == 0:
            raise ValueError("no participants")
        base, remainder = divmod(total_paise, n)
        # A clear, repeatable rule: the first `remainder` people pay 1 extra paisa each.
        return {u: base + (1 if i < remainder else 0) for i, u in enumerate(participants)}


class ExactSplit(SplitStrategy):
    def split(self, total_paise, participants, *, amounts: dict[str, int], **kwargs):
        if sum(amounts.values()) != total_paise:
            raise ValueError(f"exact shares sum to {sum(amounts.values())}, not {total_paise}")
        if set(amounts) != set(participants):
            raise ValueError("amounts must cover exactly the participants")
        return dict(amounts)


class PercentageSplit(SplitStrategy):
    def split(self, total_paise, participants, *, percentages: dict[str, float], **kwargs):
        if abs(sum(percentages.values()) - 100.0) > 1e-9:
            raise ValueError("percentages must sum to 100")
        shares = {u: int(total_paise * percentages[u] / 100) for u in participants}
        # Rounding down loses a little; give the shortfall to the largest shares, deterministically.
        shortfall = total_paise - sum(shares.values())
        for u in sorted(shares, key=lambda x: (-shares[x], x))[:shortfall]:
            shares[u] += 1
        return shares


@dataclass(frozen=True)
class Expense:                                     # never changes once created
    expense_id: str
    description: str
    total_paise: int
    paid_by: tuple[tuple[str, int], ...]           # ((user, paise), ...) — supports co-payers
    shares: tuple[tuple[str, int], ...]            # ((user, paise), ...)


class ExpenseBook:
    def __init__(self):
        self._expenses: list[Expense] = []
        self._ids = itertools.count(1)

    def add(self, description: str, total_paise: int, paid_by: dict[str, int],
            participants: list[str], strategy: SplitStrategy, **kwargs) -> Expense:
        if sum(paid_by.values()) != total_paise:
            raise ValueError("payments must sum to the expense total")
        shares = strategy.split(total_paise, participants, **kwargs)
        if sum(shares.values()) != total_paise:    # always double-checked, never just assumed
            raise AssertionError("split does not sum to total")
        expense = Expense(f"E{next(self._ids)}", description, total_paise,
                          tuple(paid_by.items()), tuple(shares.items()))
        self._expenses.append(expense)
        return expense

    def settle(self, payer: str, payee: str, paise: int) -> Expense:
        """A settlement is really just an expense the payee owes entirely to the payer."""
        return self.add(f"settlement {payer}->{payee}", paise,
                        paid_by={payer: paise}, participants=[payee], strategy=ExactSplit(),
                        amounts={payee: paise})

    def balances(self) -> dict[str, int]:
        """Each user's net position: positive means owed money, negative means owing it."""
        net: dict[str, int] = defaultdict(int)
        for e in self._expenses:
            for user, paid in e.paid_by:
                net[user] += paid
            for user, share in e.shares:
                net[user] -= share
        return {u: v for u, v in net.items() if v != 0}

    def simplify(self) -> list[tuple[str, str, int]]:
        """Greedy: match the largest creditor with the largest debtor. At most n-1 transfers."""
        net = self.balances()
        # Max-heaps via negated keys; tie-break on name so the output stays predictable.
        creditors = [(-v, u) for u, v in net.items() if v > 0]
        debtors = [(v, u) for u, v in net.items() if v < 0]
        heapq.heapify(creditors)
        heapq.heapify(debtors)

        transfers: list[tuple[str, str, int]] = []
        while creditors and debtors:
            credit, creditor = heapq.heappop(creditors)
            debt, debtor = heapq.heappop(debtors)
            amount = min(-credit, -debt)
            transfers.append((debtor, creditor, amount))       # the debtor pays the creditor
            if -credit - amount > 0:
                heapq.heappush(creditors, (credit + amount, creditor))
            if -debt - amount > 0:
                heapq.heappush(debtors, (debt + amount, debtor))
        return transfers


book = ExpenseBook()

# Dinner: Asha pays Rs 1000, split equally three ways -> 33333/33333/33334 paise
dinner = book.add("dinner", 100_000, {"asha": 100_000},
                  ["asha", "ravi", "meera"], EqualSplit())
assert sum(dict(dinner.shares).values()) == 100_000
assert sorted(dict(dinner.shares).values()) == [33_333, 33_333, 33_334]

# Cab: Ravi and Meera co-pay; exact shares
book.add("cab", 60_000, {"ravi": 40_000, "meera": 20_000},
         ["asha", "ravi", "meera"], ExactSplit(),
         amounts={"asha": 30_000, "ravi": 20_000, "meera": 10_000})

# Groceries: a percentage split
book.add("groceries", 45_000, {"meera": 45_000},
         ["asha", "ravi", "meera"], PercentageSplit(),
         percentages={"asha": 50, "ravi": 25, "meera": 25})

net = book.balances()
assert sum(net.values()) == 0                     # the money always balances out to zero

transfers = book.simplify()
assert len(transfers) <= len(net) - 1             # the n-1 bound
assert sum(amount for _, _, amount in transfers) == sum(v for v in net.values() if v > 0)

for debtor, creditor, amount in transfers:
    book.settle(debtor, creditor, amount)
assert book.balances() == {}                      # everything settles down to zero

print("net before settling:", {u: str(Money(v)) for u, v in net.items()})
print("transfers:", [(d, c, str(Money(a))) for d, c, a in transfers])