«Московская олимпиада школьников по информатике для 6-9 классов, 2017 год Россия, Москва, 24 февраля Задача A. Игра в напёрстки Имя входного файла: стандартный ввод Имя выходного файла: ...»
Московская олимпиада школьников по информатике для 6-9 классов, 2017 год
Задача A. Игра в напёрстки
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 0.5 секунд
Ограничение по памяти: 256 мегабайт
В свободное время Бомбослав любит наблюдать из окна как ребята во дворе играют “на интерес” в известную игру в напёрстки. Для игры требуется два человека, ведущий и игрок. Ведущий
берёт три одинаковых непрозрачных напёрстка и прячет под один из них шарик. Затем он несколько раз меняет некоторые пары напёрстков местами, после чего игрок должен угадать, под каким напёрстком сейчас находится шарик.
Бомбослав заметил, что ребята во дворе не очень изобретательны в своих действиях, и ведущий всегда меняет местами левый напёрсток со средним на нечётных действиях (то есть на первом, третьем, пятом и так далее) и средний с правым на чётных действиях (то есть на втором, четвёртом и так далее).
Пронумеруем напёрстки от 0 до 2 слева направо. То есть левый напёрстком имеет номер 0, средний номер 1, а правый номер 2. Бомбослав не успел увидеть начало игры, но посчитал, что ведущий совершил n действий и в итоге шарик оказался под напёрстком x. Под каким напёрстком находился шарик в самом начале?
Формат входных данных В первой строке входных данных записано одно цело число n (1 n 2 · 109) - количество действий, совершённых ведущим.
Во второй строке записано одно целое число x (0 x 2) - номер напёрстка, под которым оказался шарик через n действий.
Формат выходных данных Выведите одно целое число от 0 до 2, означающее номер напёрстка, под которым находился шарик в самом начале.
Примеры стандартный ввод стандартный вывод Замечание В первом примере шарик изначально лежал под средним напёрстком и ведущий совершил четыре действия.
1. Первым действием ведущий поменял местами левый и средний напёрстки. В результате шарик оказался под левым напёрстком.
2. Вторым действием ведущий поменял местами средний и правый напёрстки. Шарик остался под левым напёрстком.
3. Третьим действием ведущий снова поменял местами левый и средний напёрстки. В результате шарик снова оказался посередине.
4. Последним четвёртым действием ведущий опять поменял местами средний и правый напёрстки и шарик оказался под правым напёрстком.
Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, верно работающие при n 100 000 будут набирать не менее 50 баллов.
Страница 1 из 8 Московская олимпиада школьников по информатике для 6-9 классов, 2017 год Россия, Москва, 24 февраля Задача B. Игра «Банковские карты»
Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт После четвёртого сезона Шерлок и Мориарти осознали бессмысленность баталии, развернувшейся между ними, и решили дальше соревноваться в мирную игру «Банковские карты».
Правила у этой игры предельно просты: каждый игрок приносит свою любимую банковскую карту с n-значным номером. Далее оба игрока по очереди называют последовательные цифры из банковской карты. Если цифры не совпадают, то участник, цифра которого оказывается меньше, получает щелбан от другого игрока. Например, если n = 3 и у Шерлока номер карты 123, а у Мориарти 321, то сначала Шерлок называет число 1, а Мориарти называет число 3 и Шерлок получает щелбан. Затем и Шерлок и Мориарти называют число 2, и щелбан не получает никто.
Наконец на третьем шаге, Шерлок называет 3, а Мориарти называет 1 и получает щелбан.
Шерлок, конечно, будет играть честно, но Мориарти, как настоящий злодей, подсмотрел номер карты Шерлока и теперь хочет называть цифры своей банковской карты не последовательно, а в некотором другом порядке (однако количество каждой из цифр он не изменяет). Например в случае выше, Мориарти мог бы назвать цифры в последовательности 1, 2, 3 и не получил бы щелбанов вообще, а мог назвать 2, 3 и 1 и выдать Шерлоку целых два щелбана.
Вам поручено вычислить, какое минимальное количество щелбанов Мориарти точно получит и какое максимальное число Мориарти может дать Шерлоку. Обратите внимание, что это две разные цели, и они могут достигаться при использовании разных порядков.
Формат входных данных В первой строке находится одно целое число n (1 n 1000) - количество цифр в банковских картах Шерлока и Мориарти.
Во второй строке записана последовательность из n цифр - номер кредитной карточки Шерлока.
В третьей строке записана последовательность из n цифр - номер кредитной карточки Мориарти.
Формат выходных данных В первой строке выведите одно число - минимальное число щелбанов, которое обязательно получит Мориарти.
Во второй строке выведите так же одно число - максимальное число щелбанов, которое Мориарти может дать Шерлоку.
Примеры стандартный ввод стандартный вывод Замечание Первый пример совпадает с примером, разобранным в условии задачи. Во втором примере Мориарти никак не сможет избежать двух щелбанов.
– – –
Система оценки В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла.
Решения, корректно работающие при 1 n 3, наберёт не менее 10 баллов.
Решения, корректно работающие при 1 n 8, наберет не менее 30 баллов.
– – –
Замечание Слово a1, a2,..., am длины m лексикографически не превосходит слова b1, b2,...
, bk длины k, если выполняется одно из двух:
Либо в первой позиции i, такой что ai = bi, символ ai идёт раньше по алфавиту, чем символ bi, то есть в первой различающейся позиции символ слова a меньше символа слова b;
– – –
Либо (если такой позиции нет) m k, то есть второе слово начинается с первого либо совпадает с ним Про последовательность слов говорят, что они идут в лексикографическом порядке, если каждое слово в нём (кроме последнего) лексикографически не превосходит следующего за ним.
Для слов, состоящих из маленьких латинских букв, лексикографический порядок совпадает с алфавитным порядком расположения слов в словаре.
Хештег, состоящий только из символа ‘#’, лексикографически не больше любого другого хештега.
Поэтому в третьем примере мы не можем оставить два первых слова и сократить два вторых.
Система оценки В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла.
Результаты работы ваших решений на первых 35 тестах будут доступны во время соревнования.
Результаты работы на остальных 15 будут доступны после окончания соревнования.
Решения, корректно работающие при 1 n, L 15, наберут не менее 20 баллов.
Решения, корректно работающие при 1 n, L 1 000, наберут не менее 50 баллов.
Решения, корректно работающие при 1 n, L 100 000, наберут не менее 70 баллов.
– – –
Замечание В приведенном примере таблица не отсортирована ни по одному столбцу, но, например, строки 1–3 отсортированы по столбцу 1, а строки 4–5 по столбцу 3.
– – –
Система оценки В данной задаче 100 тестов, помимо тестов из условия, каждый из них оценивается в 1 балл.
Результаты работы ваших решений на первых 60 тестах будут доступны во время соревнования.
Результаты работы на остальных 40 будут доступны после окончания соревнования.
Решения, корректно работающие при 1 n, k 100 и m = 1, наберут не менее 10 баллов.
Решения, корректно работающие при 1 n, m, k 100, наберут не менее 40 баллов.
Страница 7 из 8 Московская олимпиада школьников по информатике для 6-9 классов, 2017 год Россия, Москва, 24 февраля Задача E. Ханойская фабрика Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт Наверняка вы слышали об известной задаче про Ханойские башни, но мало кто знает, что существует целая фабрика, производящая кольца для этой замечательной игры. Однажды на эту фабрику пришел срочный заказ от властителя Египта - Солнцеликого. Солнцеликий требует немедленно прислать ему для игры как можно более высокую башню. Работники фабрики не были готовы к такому необычному заказу, поэтому им придётся собрать какую-то башню из уже произведённых колец.
На складах фабрики находятся n колец, i-е кольцо имеет внутренний радиус ai, внешний радиус bi и высоту hi.
Требуется выбрать некоторые из этих колец и упорядочить их таким образом, чтобы выполнялись следующие условия:
Внешние радиусы колец образовывали невозрастающую последовательность, то есть кольцо j можно поставить на кольцо i только если bj bi.
Кольца не должны проваливаться друг в друга, то есть кольцо j можно поставить на кольцо i только если bj ai.
Суммарная высота всех использованных колец должна быть максимальна.
Формат входных данных В первой строке входных данных записано целое число n (1 n 100 000) - количество колец на складах фабрики.
В i-й из последующих n строк записаны три числа ai, bi и hi (1 ai, bi, hi 109, bi ai) - внутренний радиус, внешний радиус и высота i-го кольца соответственно.
Формат выходных данных Выведите максимальную высоту башни, которую смогут получить работники фабрики.
Примеры стандартный ввод стандартный вывод Замечание В первом примере выгодно поставить друг на друга все имеющиеся кольца в порядке 3, 2, 1.
Во втором примере можно либо поставить кольцо 3 на кольцо 4 и получить башню высоты 3, либо поставить кольцо 1 на кольцо 2 и получить башню высоты 4.
Система оценки В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла.
Результаты работы ваших решений на первых 30 тестах будут доступны во время соревнования.
Результаты работы на остальных 20 будут доступны после окончания соревнования.
Решения, корректно работающие при 1 n 9, наберут не менее 10 баллов.
Решения, корректно работающие при 1 n 15, наберут не менее 20 баллов.
Решения, корректно работающие при 1 n 1000, наберут не менее 60 баллов.
– – –
Похожие работы:
«DOI: 10.18698/0236-3933-2016-2-53-66 УДК 517.925:519.71 ПЛАНИРОВАНИЕ ПРОСТРАНСТВЕННОГО МАРШРУТА ПОЛЕТА БЕСПИЛОТНОГО ЛЕТАТЕЛЬНОГО АППАРАТА С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЧАСТИЧНО ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Тань Лиго, А.В. Фомич в е МГТУ им. Н.Э. Ба...»
«Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13) Раздел II. Автоматизация проектирования УДК 681.51.01 О.Р. Норкин, С.С. Парфенова РОЛЬ ФАКТОРА НЕОПРЕДЕЛЕННОСТИ В СИСТЕМНОМ АНАЛИЗЕ И ЕГО ВЛИЯНИ...»
«Образовательная среда Andrey Igorevich Shalabay,post-graduate student, institute of mathematics and fundamental informatics, Syberian federal university We consider the overall situation in the field of conducting distance learning. To improve the efficiency of this process is proposed to...»
«Марина Соколова ЭЛЕКТРОННОЕ ПРАВИТЕЛЬСТВО В БЕЛАРУСИ: преодолеть инерцию информатизации аналитический документ Минск, 2011 г.СОДЕРЖАНИЕ 1. РЕЗЮМЕ 2. ВВЕДЕНИЕ 3. ЭЛЕКТРОННОЕ ПРАВИТЕЛЬСТВО: МОДЕЛИ И КОНЦЕПЦИ 4. БЕЛОРУССКИЙ ПРОФИЛЬ ЭЛЕКТРОННОГО ПРАВИТЕЛЬСТВА 5. ПОДПРОГРАММА "ЭЛЕКТРОННОЕ ПРАВИТЕЛЬСТВ...»
Подготовка к олимпиаде по программированию.
Программирование очень важно в современном мире. Когда вы покупаете билет в кино или бутылку газировки в супермаркете, летите в самолете или говорите по телефону, слушаете музыку или делаете фотоснимок, вам приходится, возможно, даже не замечая этого, пользоваться программами. И первое участие в олимпиаде по информатике может быть станет для кого-то первым шагом к будущей профессии программиста.
Только начинаете свой олимпиадный путь, или уже хорошо знакомы с его форматом? Мы будем рады помочь в подготовке каждому. Для новичков всегда открыт «Кружок от чемпионов» Ассоциации победителей олимпиад, а опытные участники могут попасть в состав сборной Москвы по информатике.
Какой он, школьный этап?
Для учеников 5-6 классов проводится только первый этап всероссийской олимпиады. Все задания являются теоретическими и выполняются на бумаге (без компьютера).
Школьникам 7-8 классов, желающим участвовать в олимпиаде по информатике, тоже не обязательно уметь программировать. Ребята решают смешанный вариант, содержащий как теоретические задания, так и задачи по программированию. Для получения полного балла достаточно верно выполнить только теоретические задания.
А вот соревнование для школьников 9-11 классов является олимпиадой по программированию. Ребята пишут несколько программ на одном из языков программирования. Проверка заданий на олимпиаде проводится автоматически специальной тестирующей системой, без участия жюри. Тестирующая система строга и непредвзята, и баллы можно получить только за решение, которое строго соответствует требованиям условия задачи.
Попрактиковаться в решении задач окружного этапа олимпиады и в работе с тестирующей системой можно на сайте informatics.mccme.ru в разделе Личные олимпиады - Олимпиады для начинающих.
Ежегодно к муниципальному этапу запускаются онлайн-курсы для школьников. По всем 24 предметам олимпиады публикуются материалы для подготовки, организационная информация и советы специалистов. Участники могут задавать вопросы жюри и подавать апелляции. Зарегистрироваться на курсы можно с помощью приглашения, которое выдается в школе вместе с листком участника.
Понравилось - занимайся
Попасть в поле зрения тренера не сложно, достаточно хорошо выступить на этапах всероссийской олимпиады, московской олимпиаде школьников, открытой олимпиаде по программированию или командной олимпиаде. Ребят, показавших себя, тренеры приглашают на специализированные занятия по подготовке.
Можно и просто прийти на занятие (предварительно лучше написать на e-mail). Успешное очное и дистанционное выступления позволяют получить приглашения на занятия более высокого уровня и войти в состав кандидатов в команду Москвы на всероссийской олимпиаде.
Занятия для кандидатов
Проходят для разных групп и уровней школьников - как от не очень сильной (в рамках подготовки ко 2 этапу), так и уровня подготовки к заключительному этапу и международным олимпиадам. В октябре ребята участвуют в отборе на всероссийскую командную олимпиаду по программированию, сама она проходит в конце ноября - начале декабря.
Сборы для кандидатов в команду проводятся в ноябре. Кроме того в рамках подготовки ребята участвуют в международных соревнованиях (Жаутыковская олимпиада в Казахстане, Международный турнир в Болгарии и Romanian master of informatics).
После определения точного состава команды в период с февраля по март, каждый год проходят сборы уже непосредственно для ее членов.
Это одна из немногих олимпиад по информатике, которая проводит отдельные туры для 10-11 классов и для школьников 6-9 классов, которые только начинают изучать программирование...
Для младшей группы отборочный и заключительные этапы состоят из одного тура. 10-11 классы могут пройти в финал с помощью двух заочных туров, каждый из которых проводится независимо. Если участник олимпиады не набрал необходимого количества баллов для выхода в очный этап на первом отборочном туре, то он может принять участие во втором. Баллы не суммируются.
Что нового
Как участвовать
- Зарегистрируйтесь на олимпиаду в системе регистрации Московской олимпиады школьников. Ученикам 6-9 классов для прохождения отборочного этапа также необходимо завести аккаунт на сайте informatics.msk.ru, учащимся 10-11 понадобится логин на Яндексе.
- Выполните задания дистанционного этапа. Для 10-11 классов проходят два независимых тура, для 6-9 только один.
- Дождитесь результатов и списков приглашенных в финал.
- Зарегистрируйтесь на участие в заключительном этапе олимпиады, указав предпочитаемую вами площадку проведения. Список площадок и ссылку на регистрацию организаторы опубликуют на сайте олимпиады.
- Приходите на очный этап.
- Узнайте свой результат в день проведения олимпиады, в случае несогласия с оценкой - участвуйте в апелляции.
- Дождитесь объявления границ определения победителей и призеров.
- Участники 6-9 классов получают бумажный диплом на площадке проведения или в Центре педагогического мастерства. Для 10-11 классов предусмотрены только электронные дипломы от организаторов и образца РСОШ.
Что особенного
Как готовиться
Решайте задания прошлых лет Разберите сложные места с учителем. Задавайте вопросы. Школа заинтересована в вашем успехе – это повышает ее престиж. Задания и решения →
