Олимпиады для начинающих 03

Подборка из нескольких задач для подготовки к олимпиаде по информатике.


Содержание



Экономическая грамотность

Многие банки при оплате покупок их банковскими картами предлагают систему возврата части потраченных средств, называемую cashback.

Мама Алёны имеет три подобные карты с разными условиями возврата части потраченной суммы. На карту банка RR возвращается 5 рублей из каждых полных 100 рублей стоимости одной покупки. Например, 5 рублей возвращается и за покупку стоимостью 100 рублей, и 199 рублей. Банк BB возвращает 2 рубля с каждых 50 рублей покупки, и за покупку стоимостью 199 рублей он вернет уже 6 рублей. А банк ММ возвращает 3% с полной стоимости любой покупки (заметим, что при цене в целом числе рублей, 3% всегда будут составлять целое число копеек), поэтому за покупку в 199 рублей вернется 5 руб. 97 коп.

Алёна любит ходить вместе с мамой за покупками. Мама предложила Алёне определять, какую покупку какой картой оплачивать, чтобы сумма возврата была максимально возможной. Считайте, что оплата любой покупки возможна любой картой. Если какие-то две или все три карты дают лучшую сумму возврата с точностью до копеек, то Алёна выбирает ту из карт, которая ей больше нравится по оформлению. Больше всего Алёна любит карту банка MM, затем идёт карта банка BB, а меньше всего Алёне нравится карта банка RR.

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

Вводится одно целое число S (1 ⩽ S ⩽ 10 000) — стоимость покупки в рублях.

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

Выведите название банка RR, BB или MM в зависимости от того, картой какого банка выгоднее оплатить эту покупку. А при равенстве суммы возврата — название банка, определенного в условии задачи.

Пример входных и выходных данных

input.txt output.txt
10 MM
199 BB
101 RR

Замечание

В первом примере только банк MM вернет часть суммы покупки. Второй пример разобран в условии задачи.


Наша Таня громко плачет

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

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

Таня работает в операционной системе Microhard, в которой есть две команды, позволяющие удалять файлы. Первая команда удаляет один произвольный файл с компьютера. На выполнение этой команды Миша тратит A секунд. Вторая команда рассчитана как раз на случай, подобный Таниному, и позволяет уменьшить количество копий файла в k раз. В силу технический особенностей Microhard эта команда работает, только если количество файлов в папке делится на k без остатка. На выполнение этой команды Миша тратит B секунд.

Для решения Таниной проблемы Миша решил по очереди использовать эти команды таким образом, чтобы в конце в папке остался ровно один документ.

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

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

В первой строке содержится целое число n (1 ≤ n ≤ 2·10 9) — количество копий документа в папке у Тани.

Во второй строке содержится целое число k (1 ≤ k ≤ 2·10 9) — количество раз, в которое уменьшает количество файлов вторая команда.

В третьей строке содержится целое число A (1 ≤ A ≤ 2·10 9) — количество секунд, которое Миша тратит на выполнение первой команды.

В четвертой строке содержится целое число B (1 ≤ B ≤ 2·10 9) — количество секунд, которое Миша тратит на выполнение второй команды.

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

Выведите единственное число — минимальное количество секунд, которое придется потратить Мише на решение проблемы.

Пример входных и выходных данных

input.txt output.txt
9
2
3
1
6
5
5
2
20
8
19
3
4
2
12

Примечание

В первом тестовом примере оптимальная стратегия Миши такова:

  • За 3 секудны удалить один файл, в результате чего в папке останется 8 файлов. Обратите внимание, что Миша не мог использовать вторую команду, потому что 9 не делится на 2.
  • За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 4 файла.
  • За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 2 файла.
  • За 1 секунду уменьшить число файлов в 2 раза. После этого в папке останется 1 файл и цель Миши будет выполнена.

На выполнение этих четырех операций Миша потратит 6 секунд. Можно показать, что Миша не сможет удалить лишние файлы меньше, чем за 6 секунд.

Во втором тестовом примере Мише выгодно 4 раза удалить один файл. Так как на одно удаление Миша тратит 2 секунды, на выполнение всего задания Миша потратит 4·2 = 8 секунд. Кроме того, Миша мог бы удалить лишние файлы, один раз воспользовавшись второй командой, но, так как ее выполнение занимает 20 секунд, Мише это не выгодно.


Новое — это хорошо забытое старое

Новодружанские библиотеки имеют электронный сервис, с помощью которого можно бесплатно получить издание, несколько лет не востребованное читателями. Андрея заинтересовала красочная энциклопедия, правда изданная в прошлом веке на неизвестном ему языке.

Получив желаемое издание, он стал его изучать, открывая в произвольных местах. На одной из открытых страниц было всего две статьи, название первой из них можно было легко прочитать, так как оно было записано английскими буквами, а буквы в названии второй из них оказались практически затертыми. Легко определить было только что остались следы от k букв. Очевидно также, что второе название стоит в алфавитном порядке позже, чем первое. Это означает, что либо первая не совпадающая в написании двух слов буква в первом слове стоит в алфавите раньше, чем соответствующая буква второго слова, либо начало второго слова полностью совпадает с первым словом, но при этом второе слово длиннее первого (содержит еще какие то буквы).

Андрей не знает язык, на котором написана энциклопедия, поэтому он предположил, что второе слово состоит из тех же букв, что и первое. Чтобы проверить свое предположение, он собирается искать предполагаемое слово в интернете.

Помогите Андрею найти первое следующее в алфавитном порядке слово, состоящее из тех же букв, что и заданное слово, и состоящее ровно из k букв. Гарантируется, что такое слово существует.

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

В первой строке задано целое число n (1 ≤ n ≤ 100 000) — количество букв в первом слове.

Во второй строке задано слово, состоящее из n строчных букв английского алфавита.

В третьей строке задано целое число k (1 ≤ k ≤ 100 000) — количество букв в искомом слове.

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

Выведите искомое слово, состоящее из k букв, входящих в первое слово.

Пример входных и выходных данных

input.txt output.txt
3
abc
3
aca
3
abc
2
ac
3
ayy
3
yaa
2
ba
3
baa

Примечание

В первом тестовом примере требуемое слово должно состоять из букв a, b и c. Следующим после abc в алфавитном порядке будет слово abca, но оно состоит из 4 букв, а не из 3. Следующим после abc в алфавитном порядке состоящим из букв a, b и c и имеющим длину 3 будет слово aca.



Комментарии (2)

  • Avatar

    Никита

    |

    // Экономическая грамотность
    uses crt;
    var RR, BB, MM, x: real;
    begin 
    readln(x);
     RR:= x/100;
     RR:= Trunc(RR);  
     RR := RR*5;
     BB := x/50;
     BB := Trunc(BB);
     BB:= BB*2;
     MM := x*0.03;
     if (RR>BB)and (RR>MM)
      then
       writeln('RR');
        if (BB>RR) and (BB>MM)
         then
           writeln('BB');
           if (MM>RR) and (MM>BB)
            then
              writeln('MM');
    readkey();
    end.
    

    Reply

  • Avatar

    Дмитрий Карпухин

    |

    # экономическая грамотность
    import math
    x = int(input('Введите сумму: '))
    RR = math.trunc(x/100)*5
    BB = math.trunc(x/50)*2
    MM = x*0.03
    if RR > BB and RR > MM:
        print('RR')
    elif BB > RR and BB > MM:
        print('BB')
    else:
        print('MM')
    

    Reply

Оставить комментарий