Олимпиады для начинающих 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.


Умный обогреватель

Квартира Максима не имеет автономного отопления, поэтому температура в ней сильно зависит от температуры на улице. Для поддержания комфортной температуры он купил обогреватель и установил систему «Умный дом». В соответствующую программу Максим заложил два целых числа tmin ≤ tmax и следующий алгоритм использования обогревателя:

  1. Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был выключен, и в каждый из этих дней температура на улице была строго меньше tmin, то надо включить обогреватель в этот день и считать, что он был включен весь день. Обогреватель остается включенным и в последующие дни до тех пор, пока программа его не выключит.
  2. Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был включен, и в каждый из этих дней температура на улице была строго больше tmax, то надо выключить обогреватель в этот день и считать, что он был выключен весь день. Обогреватель остается выключенным и в последующие дни до тех пор, пока программа его не включит.

Из-за кратковременного отключения электроэнергии программу необходимо настроить заново. Сами значения tmin и tmax Максим забыл, зато у него остались записи программы о температуре и состоянии обогревателя в каждые из n дней использования системы.

Максим помнит, что tmin и tmax были целыми числами, по модулю не превосходящими 109 и tmin ≤ tmax, также он помнит, что программа не учитывала дни до первого дня использования системы и не включала обогреватель в течение первых четырех дней. Наконец, Максим помнит, что он выбирал tmin и tmax как можно более близкими друг к другу.

Помогите найти два подходящих значения tmin и tmax, не превосходящих 109 по абсолютной величине, таких, что выполняются правила использования обогревателя в каждые из n дней, tmin не превосходит tmax и величина tmax — tmin минимальна.

Гарантируется, что записи программы правильные, и такие два числа существуют.

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

В первой строке задано целое число n (5 ≤ n ≤ 105) — количество дней, в течение которых работала система.

Во второй строке входных данных задаются n целых чисел t1, …, tn (- 109 ≤ ti ≤ 109) — температуры на улице в каждый из n дней.

В третьей строке входных данных задается строка из n символов, состоящая из 0 и 1 — если в i-й позиции данной строки записан 0, то это значит, что в i-й день обогреватель был выключен, а если 1, — то включен.

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

В единственной строке выведите два целых числа tmin и tmax (tmin ≤ tmax), по модулю не превосходящих 109 — значения температур, при вставке которых в программу обогреватель будет включен и выключен в те же дни, в которые он был включен и выключен при исходных значениях, а значение tmax — tmin минимально.

Если подходящих пар значений несколько, выведите любую из них.

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

input.txt output.txt
5
1 2 3 4 5
00001
7 7
11
2 1 -1 -1 1 1 6 7 8 8 6
00000111111
2 6

Примечание

В первом тестовом примере первые пять дней температура строго меньше 7 градусов, при этом до пятого дня обогреватель был в каждый из четырех дней выключен, следовательно в пятый день программа его включила. На данный тест корректен любой ответ удовлетворяющий условию 6 ≤ tmin = tmax ≤ 109.


Оптимизация акции

В сети магазинов «Мир» при оплате карточкой Weeza действует акция. При оплате покупки, состоящей не менее чем из 10 товаров, плата за самый дешевый товар не берется. Если товаров не меньше 20, то не оплачиваются уже два самых дешевых товара и т.д.

Например, при одновременной покупке 17 товаров, покупатель потратит сумму денег равную стоимости только 16 самых дорогих из них, а при покупке 20 и 37 товаров придется заплатить только за 18 и 34 самых дорогих товара, соответственно.

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

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

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

В первой строке находится одно число n (1 ≤ n ≤ 100 000) — количество дисков на ленте.

Следующая строка содержит n чисел a i (1 ≤ ai ≤ 109) — стоимости дисков в порядке расположения на ленте.

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

Выведите наименьшую возможную стоимость покупки всех дисков с учетом акции при оптимальном разбиении дисков на группы.

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

input.txt output.txt
3
1 2 3
6
12
1 1 10 10 10 10 10 10 9 10 10 10
92

Примечание

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

Во втором тестовом примере оптимально во время первой покупки оплатить первые два диска, а за остальные диски заплатить во время второй покупки. Тогда не придется заплатить за диск стоимостью 9.



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

  • 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

  • Avatar

    Никита

    |

    // Наша Таня громко плачет
    uses crt;
    var k,A,B,n,x:integer;
    begin
    x:=0;
    writeln('write N');
    readln(n);
    writeln('write K');
    readln(k);
    writeln('write A');
    readln(A);
    writeln('write B');
    readln(B);
     while n > 1 do begin
     if (n mod k = 0) then n:=n div k
     else n:=n-1;
     if (n mod k = 0) then x:=x+B
     else x:=x+A;
     if B>A then x:=(x+A)*A;
     end;
    writeln(x);
    readkey();
    end.
    

    Reply

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