Информатика и IT
Разбор задач муниципального этапа Всероссийской олимпиады школьников по информатике
Задача: Игра со строкой
Имя входного файла: abc.in
Имя выходного файла: abc.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Маленькая Элизабет любит играть со строками. У нее есть строка длины n, полностью состоящая из букв «а». Она делает со строкой следующие действия:
- Если первая буква «а», то она дописывает в конец строки «bc», после чего удаляет из строки первые 2 буквы.
- Если первая буква «b», то она дописывает в конец строки «a», после чего удаляет из строки первые 2 буквы.
- Если первая буква «c», то она дописывает в конец строки «aaa», после чего удаляет из строки первые 2 буквы.
Элизабет останавливается после того, как у нее получится строка, состоящая из одной буквы «а». Например при n=4 потребуется 6 шагов
aaaa→aabc → bcbc→ bca→ aa→bc →a
Сколько потребуется шагов для любого n (2≤n≤100)?
Задача: Генератор кроссвордов
Имя входного файла: crossword.in
Имя выходного файла: crossword.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Ипполит, полиглот и эрудит, хочет составить самый большой в мире кроссворд из пятибуквенных слов. По следующему алгоритму:
Ипполит составил сжатое описание сетки кроссворда - таблицу n*m, состоящее из черных и белых клеток. В полной версии каждая белая клетка сжатого описания должна быть заменена на 4 пятибуквенных слова. В конце все квадраты у которых есть общее ребро, должны быть соединены дополнительным пятибуквенным словом.
Задача: Хитрая перестановка
Имя входного файла: tricky.in
Имя выходного файла: tricky.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Перестановкой длины n называется последовательность из n чисел каждая из которых встречается ровно 1 раз
Назовём перестановку хитрой, если для любых двух соседних чисел в перестановке разница межу ними больше или равна минимальному из них
Например перестановка:
(3,1,2,4)
Является хитрой, поскольку:
|3-1|≥min(3,1), | 1-2 | ≥min(1,2) и | 2-4| ≥min(2,4)
Дано число n. Найти хитрую перестановку длины n.
Задача: Двухъядерный процессор
Имя входного файла: coreduo.in
Имя выходного файла: coreduo.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Петя получил стипендию и на радостях купил для своего компьютера новый процессор. Да не простой, а двухъядерный! «Теперь все программы будут работать в 2 раза быстрее», - подумал Петя. Но не тут то было!
Как оказалось, программы быстрее выполняться не стали, зато появилась возможность запустить две программы одновременно. Поэтому, например, две программы, которые на обычном процессоре выполняются 10 и 20 секунд соответственно – на новом двухъядерном процессоре выполнить за 20 секунд. Процессор устроен таким образом, что запущенную на одном ядре программу нельзя прерывать (и возобновлять выполнение через некоторое время) или переносить вычисления на другое ядро. То есть, программа выполняется на ядре все свое время выполнения работы одним отрезком времени, а следующую программу на данном ядре можно запустить только после окончания выполнения предыдущей.
У Пети есть n программ, для каждой из них известно время выполнения ti. Петя хочет распределить программы между ядрами процессора так, чтобы все программы были выполнены как можно быстрее. Программы можно выполнять в любом порядке.
Например, программы с временами выполнения 5, 3, 7, 9, 12 можно выполнять за 19 секунд, если на первом ядре выполнять первую, вторую и четвертую программы, а на втором – остальные две. При этом нет способа распределить программы так, чтобы успеть их выполнить за 18 секунд.
Помогите Пете решить его проблему!
Рейтинг: Самые высокооплачиваемые ИТ-специальности в России
При подсчёте самых высокооплачиваемых должностей учитывалась не только средняя зарплата по рынку, но и конкуренция в профессии (отношение количества специалистов к количеству вакансий), средняя зарплата в предыдущих месяцах и собственный зарплатный индекс, разработанный Superjob. +Подробнее
Готовимся к ГИА вместе
Демоверсия, спецификация, кодификаторы ОГЭ 2020 год (скачать)
Демоверсия ЕГЭ 2020 года по информатике (скачать)
Демоверсия, спецификация, кодификаторы ЕГЭ 2020 год (скачать)
РАСПИСАНИЕ ЗАНЯТИЙ ОГЭ
31 ЯНВ
15:00 — Логика. Логические высказывания
24 ЯНВ
15:00 — Информация. Информационный объем сообщения
15:00 — Проведение пробного ОГЭ по информатике
07 ФЕВ
Демоверсия ОГЭ 2020 года по информатике (скачать)
10 ФЕВ
3 ФЕВ
27 ЯНВ
15:00 — Графы. Поиск количества путей
РАСПИСАНИЕ ЗАНЯТИЙ ЕГЭ
15:00 — Кодирование чисел. Системы счисления
15:00 — проведение пробного ЕГЭ по информатике