Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ВСЕРОССИЙСКАЯ ОЛИМПИАДА ШКОЛЬНИКОВ 2013-2014 гг.
ШКОЛЬНЫЙ ЭТАП
ИНФОРМАТИКА
9-11 КЛАСС
Задача 1«Тролли и физика».
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 64 мегабайта
ввод: stdin
вывод: stdout
— А что это за звуки, вон там? – спросила Алиса, кивнув на весьма укромные заросли какой-то симпатичной растительности на краю сада.
— А это чудеса, – равнодушно пояснил Чеширский Кот.
— И.. И что же они там делают? – поинтересовалась девочка, неминуемо краснея.
— Как и положено, – Кот зевнул. – Случаются…
Льюис Кэрролл
Однажды юный физик Кеша, гуляя по лесу, заметил двух злобных лесных троллей, которые были заняты высокоинтеллектуальной деятельностью. Они раскручивали свои топоры по окружности так, чтобы они вращались с определенными частотами и, за счет стробоскопического эффекта, получали таким образом послания из космоса. Кеше не составило труда заметить, что топоры движутся по окружностям радиусов r1 и r2 с угловыми скоростями ω1и ω2 соответственно. Как настоящий физик, Кеша решил провести наблюдения и выяснить, чей топор преодолеет больший путь за время получения одного блока информации. Но на tfail секунде наблюдений тролли заметили Кешу, и эксперимент прервался по техническим причинам. Так как Кеше сейчас не до расчета путей и он не сообщил нам время получения блока информации, мы просим вас просто выяснить, чей топор преодолел большее расстояние за время Кешиных наблюдений.
Входные данные
В первой строке задано 2 целых числа r1 и ω1 — радиус окружности, по которой движется топор первого тролля и его угловая скорость (в миллиметрах и градусах в секунду соответственно). Во второй строке задано 2 целых числа r2 и ω2 — аналогичные данные для второго тролля. (1 ≤ r1, r2, ω1, ω2 ≤ 109)
В третьей строке содержится одно целое число tfail (tfail ≤ 105) — секунда, на которой тролли заметили Кешу.
Выходные данные
Выведите "1" (без кавычек), если большее расстояние преодолел топор первого тролля, "2" — второго, или "0", если их топоры преодолели равные расстояния.
Примеры
|
Вход |
Выход |
|
4 8 |
2 |
|
5 5 |
1 |
|
5 8 |
0 |
Примечание
Для тех, кто прогуливал уроки физики в школе, напоминаем, что угловая скорость — физическая величина, характеризующая скорость вращения топора вокруг центра вращения. Величина угловой скорости численно равна углу поворота топора вокруг центра вращения в единицу времени.
Если ω1 = 8, значит за секунду первый топор поворачивается на относительно первого тролля.
Задача 2 «Олимпиады и монетка».
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 64 мегабайта
ввод: stdin
вывод: stdout
— Ну, тут уж ничего не поделаешь, – сказал Кот, – мы все здесь сумасшедшие. Я сумасшедший. Ты сумасшедшая.
— С чего вы взяли, что я сумасшедшая? – спросила Алиса.
— Это должно быть так, – сказал Кот, – иначе ты бы сюда не попала.
Льюис Кэрролл
Пафнутий безумно (да он слегка безумен (как и большинство наших знакомых (да, мы любим вложенные комментарии))) любит участвовать в разных олимпиадах по программированию и быдлобыстрому написанию кода. Как вы, скорее всего, догадываетесь, данные мероприятия очень сложно организовать. Ведь организаторам нужно придумывать уйму интересных задач, потом проверять ваш быдлокод, ну и в конце всего награждать победителей и призеров различного рода ништячками... И вот, во время одной из таких олимпиад, в которой участвовало аж m человек (не спрашивайте почему не n, просто m больше), организаторы так замотались и устали, что случайно удалили результаты олимпиады! Причем после олимпиады, а не перед ней! Однако у организаторов был большой опыт в проведении таких олимпиад, и с такой ситуацией они уже не раз сталкивались, поэтому они знали, как можно легко восстановить результаты олимпиады. Для этого им нужна была старая добрая счастливая (ну а для некоторых и не очень) монетка. Восстановление выглядит так: судьи берут новенький чистый лист и лист с именами всех m участников, потом они идут по списку участников сверху вниз, и для каждого участника бросают монетку и, если выпадает орел, то данного участника добавляют в начало списка с результатами (он становится первым, а остальные участники сдвигаются на позицию вниз), а если решка, то в конец списка (он становится последним, позиции остальных участников не меняются). Безумный Пафнутий пробрался в штаб судей, чтобы узнать результаты олимпиады ещё до награждения. Однако он хочет знать, какова вероятность того, что он займет первое место (для интриги), а для этого ему нужно знать количество возможных результатов олимпиады. Так как он не может посчитать это количество сам, то просит это сделать вас.
Входные данные
В единственной строке файла записано натуральное число: n (1 ≤ n ≤ 104)
Выходные данные
Выведите количество различных возможных списков с результатами олимпиады.
Примеры
|
Вход |
Выход |
|
4 |
8 |
Примечание
Тесты к этой задаче состоят из четырех групп:
Задача 3 «λ и олимпиады».
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 64 мегабайта
ввод: stdin
вывод: stdout
— Скажите, пожалуйста, куда мне отсюда идти?
— А куда ты хочешь попасть? – ответил Кот.
— Мне все равно... – сказала Алиса.
— Тогда все равно, куда и идти, – заметил Кот.
— ...только бы попасть куда-нибудь, – пояснила Алиса
— Куда-нибудь ты обязательно попадешь, – сказал Кот. – Нужно только достаточно долго идти.
Льюис Кэрролл
Одна девочка, которую для определенности мы будем называть λ (Лямбда), очень любит разные олимпиады, потому что там можно пообщаться со знакомыми и во время олимпиад можно не ходить в школу. Особенно она любит олимпиады в других городах, куда нужно ехать через полстраны, так как они позволяют прогулять больше уроков в школе. Но, чтобы попасть на такие олимпиады, нужно сначала пройти несколько отборочных туров, а к этим отборочным турам нужно подготовиться. Однако λ не готовится к ним по вполне логичной причине: если она пройдет на заключительный этап олимпиады, то не сможет мечтать о том, как было бы круто туда попасть, а жизнь без мечтаний становится серой и унылой.
Тем не менее, вечером каждого дня она размышляет о том, как было бы здорово за этот день решить много задач и получить еще больше опыта. Но однажды она зашла еще дальше и задумалась, а какое максимальное количество опыта можно было бы получить за этот день?
Процесс решения задач λ представляет себе так: она садится, берет набор из n задач, засекает время и начинает решать задачи. Чтобы решить i-ую задачу, ей нужно потратить duri времени, и, если она решит её через t минут после начала процесса решения задач, она получит expi - peni·t единиц опыта, где expi — эталонный опыт за решение этой задачи, peni·t — потери опыта, связанные с тем, что λ устает во время решения задач. λ может решать задачи в любом порядке, однако не может решать больше одной задачи одновременно и должна решить все задачи, так как не хочет упустить что-то важное. Значения expi, duri и peni сложным образом зависят от трудоемкости задачи, настроения, погоды на улице, фазы Луны и количества печенек на кухне, однако можно считать, что во время процесса решения задач эти величины остаются неизменными.
Однако, чтобы посчитать количество опыта, λ требуется exprequired единиц опыта, а у нее пока только expλ и expλ < exprequired, поэтому она не может дать ответить на свой вопрос и просит это сделать вас. А она пока еще помечтает.
Входные данные
В первой строке содержится натуральное число n (2 ≤ n ≤ 104) — количество задач, которое хотела бы решить λ.
Далее идет n строк с описанием этих задач, где каждая задача описывается тремя натуральными числами expi, duri и peni (1 ≤ expi ≤ 105;1 ≤ duri, peni ≤ 103)
Выходные данные
Пока λ мечтает, выведите максимальное количество опыта, которое она могла бы получить, решив эти задачи.
Примеры
|
Вход |
Выход |
|
3 |
174 |
Примечание
Комментарий к первому тесту:
Сначала λ решает вторую задачу. Она решает её на 30-ой минуте и получает за неё 200 - 30·5 = 50 единиц опыта.
Затем λ решает третью задачу, на её решение она тратит 24 минуты и решает её на 54-ой минуте решения задач. За эту задачу она получает 300 - 54·3 = 138единиц опыта.
И наконец, она начинает решать первую задачу, решит её она на 64-ой минуте и получит 50 - 64·1 = - 14 единиц опыта. Заметьте, что λ получает за эту задачу отрицательный опыт, но при этом, она все равно должна решить её.
В итоге она получит 50 + 138 + ( - 14) = 174 единиц опыта.
Тесты к этой задаче состоят из четырех групп:
Задача 4 «Печальная ванилька».
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 64 мегабайта
ввод: stdin
вывод: stdout
Был холодный... осенний вечер... Моросил плачущий дождик... В лужах отражалась бренность бытия... Лишь одна вещь... во всем мире... могла утешить Её... любимый пирожок с вишней... верный... ни разу не предававший... друг... единственный... кто Её понимал...
Е. Щ.
Одна печальная ванилька очень любит ходить в кафешки с бесплатным wi-fi, где она пьет кофе, ест пирожки с вишней и по-ванильному твитит ванильные твиты в свой ванильный твиттер про свою ванильную жизнь. Причем делает она это следующим образом:
Сколько твитов напишет ванилька в свой твиттер, если в кафешке проходит акция, и каждый spie пирожок и scoffee кофе она получает бесплатно?
Входные данные
В первой строке находится целое число X (1 ≤ X ≤ 1015) — количество денег у ванильки вначале.
Во второй строке находится два целых числа: cfork и cknife (1 ≤ cfork, cknife ≤ 106)
В третьей строке находится два целых числа: cpie и ccoffee (1 ≤ cpie, ccoffee ≤ 106)
В четвертой строке находится два целых числа: spie и scoffee (2 ≤ spie, scoffee ≤ 103)
Выходные данные
Выведите количество твитов, которое твитнет ванилька.
Примеры
|
Вход |
Выход |
|
200 25 35 17 20 2 3 |
7 |
|
50 40 20 15 10 4 6 |
0 |
|
150 70 80 5 12 3 4 |
1 |
Примечание
Комментарий к первому тесту:
Тесты к этой задаче состоят из трех групп:
Задача 5 «character.name и owl.name».
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 64 мегабайта
ввод: stdin
вывод: stdout
Вокруг стеклянного плафона под потолком обессиленно мотались три мухи – должно быть, первые мухи в этом году. Время от времени они вдруг принимались остервенело кидаться из стороны в сторону, и спросонок мне пришла в голову гениальная идея, что мухи, наверное, стараются выскочить из плоскости, через них проходящей, и я посочувствовал этому безнадежному занятию.
А. и Б. Стругацкие
Главный герой задачи (так авторам было лень придумывать ему имя, будем звать его character.name) учится в физико-математическом классе. А, как вам, наверное, известно, ученики физ-мат классов около половины времени в школе тратят впустую на разных гуманитарных уроках, где им объясняют, почему этот предмет гораздо важней физики или математики и почему именно на него нужно тратить большую часть своего времени. Обычно character.name не теряет зря времени на таких уроках, а размышляет о чем-нибудь важном, например: о королях и капусте, рисует что-нибудь, решает задачи, придумывает задачи или занимается еще чем-нибудь полезным. Так и было одним солнечным днем (или дождливым. Увы, некоторые подробности сей истории не дошли до наших времен). Над character.name нависла угроза бездарно потратить 4 часа времени впустую, и он, решив не сдаваться, начал рисовать. Так как он иногда страдает излишним перфекционизмом, то на первом уроке он нарисовал координатные оси Ox и Oy и лес. На следующем уроке он нарисовал в этом лесу три обелиска Малых Печенек и алтарь Великой Печеньки. Все из-за того же перфкционизма, первый обелиск стоит в точке с координатами (0;0), второй – в точке (a;0), третий – (0;b), а алтарь находится внутри треугольника, образованного этими тремя точками. На третьем уроке он нарисовал спящих ежиков, которые расположены с плотностью ρhedgehog ежика на см2. На четвертом уроке он нарисовал совушку, но, так как ему было лень придумывать ей имя, он зовет ее owl.name (что, в принципе, логично: персонажи всегда чем-то похожи на своих создателей). Затем угроза минула, и следующие два урока character.name занимался физикой. Тем временем owl.name стало скучно, и она стала летать внутри треугольника, образованного тремя обелисками Малых Печенек, и считать всех ежиков, которых увидела. В итоге она насчитала Nhedgehog ежиков. Мы знаем, что если owl.name летит над точкой с координатами (x;y), то видит все, что находится на земле внутри круга с центром в точке (x;y) и радиусом r. Так же мы знаем, что она умеет хорошо считать. Но нам интересно, умеете ли вы считать ежиков так же хорошо, как совушка, поэтому просим вас назвать Nhedgehog.
Входные данные
В единственной строке файла записано четыре натуральных числа: a, b, r и ρhedgehog (1 ≤ a, b, r, ρhedgehog ≤ 103)
Выходные данные
Выведите количество ёжиков, которое насчитала owl.name.
Примеры
|
Вход |
Выход |
|
3 4 1 2 |
42.283185 |
Примечание
Можно считать, что совушка побывала над каждой точкой треугольника.
Заметим, что owl.name может насчитать нецелое количество ёжиков, например4.5, что является нормальным. Например, такой ответ может получиться, если4 ёжика попали целиком в поле обзора совушки, и ещё один ёжик попал в поле обзор только наполовину.
Можно считать, что π = 3.1415926535