<?php

header('Content-Type: text/plain; charset=UTF-8');

$amount = 1900;

$bills = array(
    5000    => 0,
    2000    => 0,
    1000    => 1,
    500     => 100,
    200     => 4,
    100     => 0
);

/* Считаем количество денег в банкомате */
function getBillSum($bills)
{
    $BillSum = '';

    foreach ($bills as $billValue => $billAmount) {
        $BillSum += $billValue * $billAmount;
    }

    return $BillSum;
}

/* Проверяем возможность выдачи */
function checkPaymentPossibility($amount, $bills)
{
    $error = '';

    $billSum = getBillSum($bills);

    if ($billSum < $amount) {
        $error = "в банкомате недостаточно купюр";
    }

    if ($amount <= 0) {
        $error = "сумма должна быть больше нуля";
    }

    if (($amount % 100) != 0) {
        $error = "сумма должна быть кратна ста";
    }

    if (!empty($error)) {
        return "Выдача невозможна: $error";
    }

    return TRUE;
}

function giveCash($amount, $bills, $billUsed=NULL, &$tempResult=NULL)
{
    $result = '';
    $k = 0;
    $billKeys = array();
    
    foreach ($bills as $billValue => $billAmount) {
        if ($billValue > $amount || $billAmount == 0 || !empty($billUsed[$billValue])) {
            continue;
        }

        $billPaymentAmount = floor($amount / $billValue);

        if ($billPaymentAmount == 0) {
            continue;
        }

        if ($billPaymentAmount > $billAmount) {
            $billPaymentAmount = $billAmount;
        }

        $amount -= $billPaymentAmount * $billValue;

        $billUsed[$billValue] = TRUE;

        $billKeys[] = $billValue;
        $k++;

        $tempResult[$billValue] = $billPaymentAmount;
    }

    if ($amount != 0) {
        $l = $k - 1;
        $tempResult[$billKeys[$l]] -= 1;
        $amount += $billKeys[$l];
        giveCash($amount, $bills, $billUsed, $tempResult);
    }

    foreach ($tempResult as $billValue => $billAmount) {
        if ($billAmount == 0) {
            continue;
        }
        $result .= "{$billAmount}x$billValue ";
    }

    return $result;
}

function processATMRequest ($amount, $bills)
{
    $result = '';

    $errors = checkPaymentPossibility($amount, $bills);

    if ($errors !== TRUE) {
        return $errors;
    }

    $cash = giveCash($amount, $bills);

    $result .= "Сумма: $amount\n";
    $result .= "Выдача возможна, число купюр: $cash\n";

    return $result;

}

echo processATMRequest($amount, $bills);