Темы
    Информатика(2609 задач)
---> 10 задач <---
Источники --> Личные олимпиады --> Золотая середина (Новосибирск)
    2012(5 задач)
    2013(5 задач)
Страница: 1 2 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

После очередного успеха на олимпиаде Никита и Кирилл решили открыть собственный бизнес. Бизнес не простой, а золотой — продажа яблок сорта Golden.

Миллионер Семён решил порадовать любимую мамочку — купить ей вкусных яблок. Он пришёл на импровизированный рынок НиК, где работали Никита и Кирилл. Семён решил купить все яблоки, благо денег у него хватает.

Продав все яблоки, Никита и Кирилл стали считать прибыль. Известно, что Никита продал A яблок по M тугриков, а Кирилл продал B яблок по N тугриков. К сожалению, с математикой у ребят плохо, поэтому они хотят узнать у вас, кто же получил бОльшую прибыль.

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

В единственной строке введены 4 целых числа A, B, M, N, разделённых пробелом.

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

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

Примеры тестов

Входные данные
8 2 2 3
Выходные данные
16

Примечание

Тесты в этой задаче состоят из четырёх групп:

  1. 0. Тест 1. Тест из условия. Оценивается в 0 баллов.
  2. 1. Тесты 2 - 8. Тесты с ограничением 1 ≤ A, B, M, N ≤ 100. Группа тестов оценивается в 30 баллов, при этом баллы ставятся только за прохождение всех тестов группы.
  3. 2. Тесты 9 - 15. Тесты с ограничением 1 ≤ A, B, M, N ≤ 10000. Группа тестов оценивается в 30 баллов, при этом баллы ставятся только за прохождение всех тестов 1 и 2 группы.
  4. 3. Тесты 16 - 22. Тесты с ограничением 1 ≤ A, B, M, N ≤ 109. Группа тестов оценивается в 40 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2 и 3 группы.

ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
4 megabytes

В социальной сети Footprint грянули перемены — её основатель Иван Умнов объявил цифры вне закона! Теперь любой пользователь, использующий цифры в своих сообщениях, получает пожизненный бан в сети.

Для Вовы Footprint — это не просто очередная социальная сеть. Здесь он общается со своей подругой Ариной.

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

Как истинный программист, Вова придумал выход из этой очень непростой ситуации: он решил заменить все цифры на соответствующие им названия на английском языке:

  • 0 — zero
  • 1 — one
  • 2 — two
  • 3 — three
  • 4 — four
  • 5 — five
  • 6 — six
  • 7 — seven
  • 8 — eight
  • 9 — nine

При этом Вова не нарушает никаких правил Footprint и не изменяет смысл сообщения для Арины.

Вова не очень хорошо знает английский, поэтому просит вас помочь ему заменить все цифры в сообщении на их названия на английском языке.

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

В единственной строке введена строка S — сообщение Вовы для Арины. В строке могут встречаться любые символы с ASCII-кодами от 32 до 126.

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

Выведите измененное сообщение Вовы, в котором каждая цифра заменена на её название на английском языке.

Примеры тестов

Входные данные
Arishka, I love you!!! <3
Выходные данные
Arishka, I love you!!! <three

Примечание

Тесты в этой задаче состоят из пяти групп:

  1. 0. Тест 1. Тест из условия. Оценивается в 0 баллов.
  2. 1. Тесты 2 - 11. Тесты с ограничением 1 ≤ |S| ≤ 100. Группа тестов оценивается в 20 баллов, при этом баллы ставятся только за прохождение всех тестов группы.
  3. 2. Тесты 12 - 19. Тесты с ограничением 1 ≤ |S| ≤ 5000. Группа тестов оценивается в 20 баллов, при этом баллы ставятся только за прохождение всех тестов 1 и 2 группы.
  4. 3. Тесты 20 - 26. Тесты с ограничением 1 ≤ |S| ≤ 105. Группа тестов оценивается в 20 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2 и 3 группы.
  5. 4. Тесты 27 - 33. Тесты с ограничением 1 ≤ |S| ≤ 4 × 106. Группа тестов оценивается в 40 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2, 3 и 4 группы.

ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Ученики физико-математического класса любят шутить. Ярик начал коллекционировать юмор своих одноклассников. После нескольких дней кропотливой работы шуток оказалось слишком много, поэтому находчивый Ярик решил систематизировать свою коллекцию.

Каждую из N шуток Ярик оценил по K различным параметрам, таким как «оригинальность», «остроумность», «классность» и др. Ярик хочет отсортировать шутки от самой лучшей к самой плохой.

Шутка X хуже шутки Y, если первый параметр шутки X меньше первого параметра шутки Y. Если эти параметры равны, то Ярик сравнивает вторые параметры, и т. д. Таким образом, при равенстве i-ых параметров нужно сравнивать (i + 1)-ые параметры, и т. д.

Так как Ярик слишком увлечён игрой в DotA, сортировать его шутки придётся вам.

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

В первой строке введены два целых числа N и K (1 ≤ K ≤ 13), разделённых пробелом — количество шуток в коллекции Ярика и количество параметров, по которым Ярик оценил каждую шутку.

В следующих N строках описываются шутки. В i-ой строке введено K целых чисел Aij, разделённых пробелом — параметры i-ой шутки.

Гарантируется, что никакие две шутки Ярик не оценил одинаково.

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

Выведите N целых чисел через пробел — номера шуток, отсортированных по выше указанным правилам.

Примеры тестов

Входные данные
3 2
117 105
31 239
117 228
Выходные данные
3 1 2 

Примечание

Тесты в этой задаче состоят из четырёх групп:

  1. 0. Тест 1. Тест из условия. Оценивается в 0 баллов.
  2. 1. Тесты 2 - 27. Тесты с ограничением 1 ≤ N ≤ 1000;N· K ≤ 1000. Группа тестов оценивается в 40 баллов, при этом баллы ставятся только за прохождение всех тестов 1 группы.
  3. 2. Тесты 28 - 47. Тесты с ограничением 1 ≤ N ≤ 105;N· K ≤ 105. Группа тестов оценивается в 40 баллов, при этом баллы ставятся только за прохождение всех тестов 1 и 2 группы.
  4. 3. Тесты 48 - 50. Тесты с ограничением 1 ≤ N ≤ 105;K = 1. Группа тестов оценивается в 20 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2 и 3 группы.

ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

Сканворд — разновидность кроссворда. Полем сканворда является прямоугольная таблица, состоящая из M строк и N столбцов, внутри которой расположены вопросы, на которые нужно дать ответ, изображения и клетки для записи ответа.

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

Артём хочет, чтобы записанное слово было как можно красивее. Слово S1 считается красивее слова S2, если S1 лексикографически меньше S2.

Помогите Артёму найти самое красивое слово из всех, которые он может получить.

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

Первая строка содержит целые числа N и M, разделённые пробелом. В следующих M строках записано по N символов, описывающих клетки сканворда. Если в клетке стоит пробел, значит бабушка не смогла отгадать слово, к которому относится данная клетка. Символ '#' означает, что эта клетка является частью изображения. Символ '?' означает, что в этой клетке находится вопрос. В противном случае в клетке записан один из символов ['A'..'Z', 'a'..'z'], означающих, что бабушка отгадала слово, к которому относится эта клетка. Регистр буквы значения не имеет.

Гарантируется, что в каждом столбце есть хотя бы одна буква.

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

Выведите самое красивое слово из тех, которые может получить Артём.

Примеры тестов

Входные данные
4 4
Aguc
?ful
ag#l
word
Выходные данные
agul

Примечание

Тесты в этой задаче состоят из пяти групп:

  1. 0. Тест 1. Тест из условия. Оценивается в 0 баллов.
  2. 1. Тесты 2 - 12. Тесты с ограничением 1 ≤ N, M ≤ 50, в сканворде встречаются только прописные буквы. Группа тестов оценивается в 10 баллов, при этом баллы ставятся только за прохождение всех тестов группы.
  3. 2. Тесты 13 - 25. Тесты с ограничением 1 ≤ N, M ≤ 50, в сканворде встречаются только буквы. Группа тестов оценивается в 10 баллов, при этом баллы ставятся только за прохождение всех тестов 1 и 2 группы.
  4. 3. Тесты 26 - 34. Тесты с ограничением 1 ≤ N, M ≤ 50. Группа тестов оценивается в 20 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2 и 3 группы.
  5. 4. Тесты 35 - 50. Тесты с ограничением 1 ≤ N, M ≤ 1000. Группа тестов оценивается в 60 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2, 3 и 4 группы.

ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Гуляя по лесу, Настя встретила белочку и решила устроить ей настоящее испытание. Однако, всё осложнилось тем, что белочка ещё маленькая и не умеет прыгать по воздуху между ветками — она может ходить только по соседним веткам.

Точками на дубе назовём концы веток и разветвления (места, где одна ветка разветвляется на несколько других).

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

К сожалению, Настя не может самостоятельно справиться с этой задачей. Помогите ей в этом.

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

В первой строке введено целое число N — количество точек на дубе.

В следующих N - 1 строках описываются ветки дуба. Каждая ветка характеризуется тремя целыми числами: Ai, Bi, Li(1 ≤ Ai, Bi ≤ N;1 ≤ Li ≤ 104), разделёнными пробелом, где Ai, Bi — номера точек на дубе, соединяемых веткой i, а Li — длина ветки i.

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

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

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

Если возможных ответов несколько, выведите любой из них.

Примеры тестов

Входные данные
3
1 2 1
1 3 1
Выходные данные
2 2 3

Примечание

Тесты в этой задаче состоят из четырёх групп:

  1. 0. Тест 1. Тест из условия. Оценивается в 0 баллов.
  2. 1. Тесты 2 - 18. Тесты с ограничением 2 ≤ N ≤ 100. Группа тестов оценивается в 40 баллов, при этом баллы ставятся только за прохождение всех тестов группы.
  3. 2. Тесты 19 - 31. Тесты с ограничением 2 ≤ N ≤ 5000. Группа тестов оценивается в 30 баллов, при этом баллы ставятся только за прохождение всех тестов 1 и 2 группы.
  4. 3. Тесты 32 - 50. Тесты с ограничением 2 ≤ N ≤ 105. Группа тестов оценивается в 30 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2 и 3 группы.


Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест