arrays | haxe

Входные данные	Выходные данные
sharm marsh	YES
ananas nnaass	NO

Входные данные

Выходные данные

sharm
marsh

YES

ananas
nnaass

Ссылка на условие задания: e-olymp.

Условие

В банкомате имеются в достаточном количестве купюры номиналом $10$, $20$, $50$, $100$, $200$, $500$. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в $n$ гривен или вывести $-1$, если указанную сумму выдать нельзя.

Входные данные.

Одно число $n$ ([latex]1 \leq n \leq 1000000[/latex]).

Выходные данные.

Наименьшее количество купюр, которыми можно выдать $n$ гривен.

Тесты

Входные данные	Выходные данные
Сумма	Количество купюр
130	3
999	-1
7360	18
440	4
3	-1

Код.

class Test {
    static function f(n : Float) : Float {
        var M = [500,200,100,50,20,10];
        var k=0;//переменная для числа купюр
        if(n%10!=0) return (-1);
        for (i in 0...M.length)
            {
                k+=Math.floor(n/M[i]);
                n=n%M[i];
            }
            return k;
    }
    static function main() {
        var output = Sys.stdout();
        var n:Int = Std.parseFloat(Sys.stdin().readLine()); //необходимая сумма
        var k= f(n);    //переменная для числа купюр      
        output.writeString(k);
    }
}

class Test {

static function f(n : Float) : Float {

var M = [500,200,100,50,20,10];

var k=0;//переменная для числа купюр

if(n%10!=0) return (-1);

for (i in 0...M.length)

{

k+=Math.floor(n/M[i]);

n=n%M[i];

}

return k;

}

static function main() {

var output = Sys.stdout();

var n:Int = Std.parseFloat(Sys.stdin().readLine()); //необходимая сумма

var k= f(n); //переменная для числа купюр

output.writeString(k);

}

Решение.

Для выполнения задания была написана функция, параметром для которой служит сумма, которую должен выдать автомат.
Сама функция является реализацией жадного алгоритма.Он заключается в том, чтобы взять купюру наибольшего достоинства, и найти, сколько раз она входит в данную сумму. То, что мы можем выдать только с помощью этой купюры, отнять от исходной суммы. Затем повторить операцию для оставшегося количества денег и самой большой из купюр меньшего достоинства. Перебрав таким образом все купюры, мы получим наименьшее их количество для получения данной суммы, что от нас, собственно, и требуется.

Такой алгоритм подходит не для всех валютных систем, а только для канонических — таких, в которых каждая купюра большего достоинства превышает меньшую более чем в два раза. В нашем случае это условие соблюдается.

Следует учесть, что сумма может быть и такой, что банкомат не сможет ее выдать. Это будет происходить тогда, когда сумма содержит некоторую часть, меньшую самой меньшей купюры. Для проверки этого условия, до начала выполнения жадного алгоритма, выполняется проверка. Если указанная сумма делится на 10 без остатка, то функция начинает выполнение алгоритма, если же нет, то возвращает $-1$.

Ссылка на решение задачи на сайте Try Haxe!

Алексей Маслеев	Сергей Завада	Анастасия Улановская
Владислав Козачков	Николай Яковлев	Даша Тарабаева
Лена Наумова	Денис Швецов	Артур Тарасов
Евгений Кравчук	Дарья Пиндус	Артём Мисесин
Даша Кивганова	Иоанна Васильева	Алёна Ищук
Кирилл Автомонов	Александр Зайченко	Маша Лукьянова
Игорь Варламов	Геннадий Муржи

haxe

Учебные материалы по программированию

Tag Archives: arrays

e-olymp 2166: Анаграммы

Условие

Входные данные.

Выходные данные.

Тесты

Код.

Решение.

e-olymp 138. Банкомат

Условие

Входные данные.

Выходные данные.

Тесты

Код.

Решение.