ЛШТН. 1 день

/ 461 комментарий

Привет всем! Сегодня мой пост будет посвящен олимпиадному программированию. Сегодня открылась 13 летняя школа точных наук (ЛШТН), организатором которой является Владикавказский центр непрерывного математического образования (ВЦНМО). [Официальный сайт] Школа будет проходит с 17 июля по 26 июля. Расписание школы можно посмотреть здесь. Участники школы могут выбрать одно из трех направлений:

  1. Робототехника и начало программирования. Как правило сюда приходят самые младшие участники нашей школы, то есть те, кто никогда не сталкивался с программированием. Самый младший участник закончил 4 класс. Обучаются дети на конструкторе Lego Mindstorms EV3.
  2. Промышленное программирование. Здесь в основном обучаются школьники, у которых есть базовые знания по программированию и хотят узнать, какие направления существуют в информатике. Здесь обучают верстке сайтов на HTML, CSS, обучают 3D моделированию и разбираются создавать простейшие игры на Unity.
  3. Олимпиадное программирование. В эту группу попадают ученики, которые уже имеют опыт программирования и обучаются новым алгоритмам и структурам данных. Здесь каждый день бывает 3-х часовой контест (олимпиада), после чего бывает разбор задач, а потом уже собственно дорешивание не решенных задач.

Я курирую олимпиадное направление. И на протяжении недели буду делиться с вами задачками и разбором этих задач. Надеюсь вам не будет скучно)

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

Далее я буду приводить условия задач. Напомню еще раз, для тех, кто забыл или не знает. Условие задачи делится на 4 части:

  1. Текст задачи – сама формулировка задачи
  2. Входные данные – строгое определение что вводится (сколько чисел/строк? какого вида ? положит/отриц ? насколько они большие ?). Это нужно чтобы оценить, какой алгоритм выбрать для решения той или иной задачи.
  3. Выходные данные – строго объясняется, что надо вывести в качества ответа по тем же критериям, что входные параметры.
  4. Тесты – приводится пример, того что вводится и ответ на него. Все наглядно и просто для лучшего понимания задачи.

Итак начнем!

Задача А. Подсчёт функции. Ограничение по времени 1 сек

Для положительного целого числа n определим функцию f:

f(n) =  - 1 + 2 - 3 + .. + ( - 1)nn

Ваша задача — посчитать f(n) для данного целого числа n.

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

В единственной строке записано положительное целое число n (1 ≤ n ≤ 1015).

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

Выведите f(n) в единственной строке.

 

входные данные
4
выходные данные
2

входные данные
5
выходные данные
-3
 

Разбор:

Заметим, что каждая двойка чисел увеличивают конечную сумму ровно на 1. Из этого следует, что если n четно, тогда ответ равен n / 2, в противном случае ответ будет (n — 1) / 2 — n. Но в конце контеста, один из участников вывел чуть другую формулу, которая следует из данной, а именно, если привести к общему знаменателю дроби, привести подобные слагаемые в числителе и вынести минус, то получится вот такая формула: — (n + 1) / 2.

Возможные ошибки: переполнение типа – используем int64 (long – C#, long long – C++).

Тема: математика.

Асимптотика решения: О(1)

 

Задача В. Счастливое деление. Ограничение по времени 2 сек

Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.

Петя называет число почти счастливым, если оно делится без остатка на какое-либо счастливое число. Помогите ему узнать, является ли заданное число n почти счастливым?

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

В единственной строке задано целое число n (1 ≤ n ≤ 1000) — число, которое нужно проверить.

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

В единственной строке выведите «YES» (без кавычек), если число n почти счастливое, иначе выведите «NO» (без кавычек).

 

входные данные
47
выходные данные
YES

входные данные
16
выходные данные
YES

входные данные
78
выходные данные
NO
Разбор:

Заметим, что счастливых чисел до 1000 (из условия) не такое уж много. Давайте возьмем, и распишем :

4, 7, 44, 47, 74, 77, 444, 447, 474, 477, 744, 747, 774, 777.

Как видно их не так уж и много. Заполним массив этими значениями. Пройдемся циклом по этому массиву и проверим на делимость, если хотя бы один раз поделилось, то выводим “YES”, в противном случае –  ”NO”.

Возможные ошибки: не все счастливые числа нашли.

Тема: перебор, теория чисел.

Асимптотика решения: О(1)

 

Задача С. Т-простые числа. Ограничение по времени 2 сек

Известно, что простыми называются целые положительные числа, у которых ровно два различных положительных делителя. По аналогии назовем целое положительное число t Т -простым, если у t ровно три различных положительных делителя.

Вам дан массив, состоящий из n целых положительных чисел. Для каждого из них определите, является ли оно Т-простым или нет.

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

Первая строка содержит единственное целое число — количество чисел в массиве, n (1 ≤ n ≤ 105). Следующая строка содержит nцелых чисел xi (1 ≤ xi ≤ 1012), разделенных пробелами.

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

Выведите n строк: i-тая строка должна содержать «YES» (без кавычек), если число xi является Т-простым, и «NO» (без кавычек), если не является.

 

Разбор:

Можно показать, что Т-простыми являются только квадраты простых чисел, и их не так и много — столько, сколько есть простых чисел, не больших 106 . Вычислим все эти числа (например, с помощью решета Эратосфена) и  запишем в set или map (Dictionary), тогда на каждый запрос можно отвечать, просто проверяя, есть ли данное число среди заранее вычисленных. Как делать решето Эратосфена много где написано, например здесь.

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

Тема: Математика, теория чисел, Решето Эратосфена.

Асимптотика решения: О(106).

 

Задача D. Оценки жюри. Ограничение по времени 2 сек

Поликарп смотрел шоу, где k членов жюри последовательно оценивали участника, начисляя ему некоторое количество баллов (возможно отрицательное, то есть баллы снимали). Изначально у участника было некоторое количество баллов, и каждая оценка последовательно добавлялась к его количеству баллов. Известно, что i-й член жюри поставил оценку ai.

Поликарп не помнит, сколько баллов было у участника до этих k оценок, но помнит, что среди результатов участника, которые озвучивались после того, как каждый из k жюри поставил оценку, точно были n (n ≤ k) значений b1, b2, …, bn (гарантируется, что все bj различны). Возможно такое, что Поликарп помнит не все озвученные результаты, то есть n < k. Обратите внимание, начальный результат участника не озвучивался.

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

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

В первой строке следуют два целых числа k и n (1 ≤ n ≤ k ≤ 2 000) — количество членов жюри и количество значений, о которых помнит Поликарп.

Во второй строке следуют k целых чисел a1, a2, …, ak ( - 2 000 ≤ ai ≤ 2 000) — оценки жюри в порядке их выставления.

В третьей строке следуют n различных целых чисел b1, b2, …, bn ( - 4 000 000 ≤ bj ≤ 4 000 000) — значения баллов, про которые помнит Поликарп. Заметьте, что эти величины не обязательно даны в хронологическом порядке.

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

Выведите количество вариантов того, сколько баллов мог иметь участник до оценок жюри. Если Поликарп что-то напутал и не существует ни одного подходящего варианта, выведите «0» (без кавычек).

входные данные
4 1
-5 5 0 20
10
выходные данные
3

входные данные
2 2
-2000 -2000
3998000 4000000
выходные данные
1
Разбор:

Изначально насчитаем массив sum, где sum[i] равно сумме первых i оценок жюри.

Рассмотрим значение баллов b1, которое запомнил Поликарп. Пусть изначальное количество баллов было равно x. Переберём m от 1 до k — сколько оценок было поставлено до момента, когда Поликарп запомнил b1. Тогда x = b1 - sum[m]. Сложим все изначальные количества баллов в set. Таким образом, мы получили все возможные изначальные количества баллов, которые могли быть у участника. После этого осталось для каждого из них проверить их корректность.

Пусть очередной кандидат на изначальное количество баллов равен d. Тогда положим в множество points все величины d + sum[i], где i перебираем от 1 до k. После этого нужно проверить, что все элементы b есть в points. Если это верно, то участник изначально мог иметь d баллов, поэтому нужно увеличить ответ на единицу.

Тема: Перебор

Асимптотика решения: О(n*(n+k)).

 

Задача Е. Треугольник. Ограничение по времени 1 сек

Есть прямоугольный треугольник с катетами длины a и b. Требуется расположить его на плоскости так, что ни одна из его сторон не параллельна осям координат, а вершины находятся в точках с целочисленными координатами, либо определить, что это невозможно.

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

В первой и единственной строке находятся два целых числа a, b (1 ≤ a, b ≤ 1000), разделенные одним пробелом.

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

В первой строке выведите «YES» или «NO» (без кавычек) в зависимости от того, существует ли искомое расположение. Если оно существует, то в трех следующих строках выведите три пары целых чисел — координаты вершин треугольника, по одной паре в строке. Координаты должны быть целыми числами, не превышающими 109 по модулю.

 

входные данные
1 1
выходные данные
NO

входные данные
5 5
выходные данные
YES
2 1
5 5
-2 4

входные данные
5 10
выходные данные
YES
-10 4
-2 -2
1 2

 

Разбор:

Предыстория:

Поставим наши катеты на осях координат. И начнем вращать. Посчитаем новые координаты точки В’. Так как треугольники B’OX2 И A’OX1 И угол альфа один и тот же, возьмем  и распишем синус этих углов в обоих треугольниках. То есть Sin(alph) = x2/b , С другой Sin(alph) = у1/а. Возьмем и приравняем эти равенства. И выразим x2 = — y1b/a. То же самое поступим и с косинусами и выйдет такая формула y2 = x1b/a/.

В задаче требовалось расположить прямоугольный треугольник с катетами a, b на плоскости с вершинами в целых точках.
Если искомое расположение существует, то катет a всегда можно представить как вектор с целыми координатами A{x;y}, при чем a2 = x2 + y2. Переберем все возможные x (1 ≤ x ≤ a - 1), проверим, что y получается целым числом. Вектор, перпендикулярный найденной уже можем вычислять (смотри предыстория). Нужно лишь не забыть проверку на то, что гипотенуза не параллельна осям координат.

Тема: геометрия, математика
Сложность решения : O(n).

 

Задача F. Теннисный Чемпионат. Ограничение по времени 1 сек

Бразильский город Рио-де-Жанейро принимает крупный теннисный турнир, и Остап Бендер не намерен пропускать это событие. В турнире примут участие n теннисистов, причём с первого же матча будет идти игра на выбывание — проигравший сразу покидает турнир.

Организаторы ещё не составили сетку чемпионата, но известно, что два игрока могут играть друг с другом, если и только если количество игр, уже проведённых одним из них, отличается от количества игр, проведённых другим, не более чем на одну игру (в любую сторону). Разумеется, оба игрока должны были выиграть все свои встречи, чтобы всё ещё участвовать в турнире.

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

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

В единственной строке входных данных записано целое число n (2 ≤ n ≤ 1018) — количество участников турнира.

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

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

 

входные данные
2
выходные данные
1

входные данные
3
выходные данные
2

входные данные
4
выходные данные
2

входные данные
10
выходные данные
4
Разбор:

Давайте решать обратную задачу: сколько участников как минимум должны участвовать, если чемпион проведет ровно n матчей. Сделаем сетку так, чтобы тот, кто победил в последнем матче до этого играл n матчей, а тот кто проиграл — сыграл (n-1) матчей, это будет оптимальная игра. Тогда очевидно такая рекуррентая связь: f(n+1) = f(n) + f(n-1). Значит, задача сводится к тому, чтобы найти индекс наибольшего числа Фибоначчи, не превосходящую число, данное в вводе.

 

Ну вот и все, все задачи разобраны. Все вопросы можете задавать в комментариях.

Ну и в конце фотки 🙂

461 комментарий

  2. ZacharyDed

    Производство матрацев. Реализация текстильной продукции

    https://goo.gl/5WYADp — производство матрацев

    — любые объемы,
    — матрасы высочайшего качества,
    — самые выгодные цены

    http://bit.do/eHZLQ — матрац на кровать купить

    Ответить

  4. ZacharyDed

    Производство матрацев. Реализация текстильной продукции

    https://goo.gl/5WYADp — хороший матрас

    — любые объемы,
    — матрасы высочайшего качества,
    — самые выгодные цены

    https://goo.gl/5WYADp — где купить подушки оптом

    Ответить

  5. Виртуальный набор разработанный именно для усмотрения всяческих важных альтернатив у бизнесе, те что соединенные с наборами в рубеж, также этот вопрос возможно настроить к посредством телефоннную сеть. Наша предприятие sip номер в оаэ предлагает под потребителей всяческие выбор придуманного номера: открытые устой, виртуальные АТС, номер 800, SIP- наборы, соединенные номера, SMS также подобные версии, какие станут вмиг формировать указанные вами наборы под клиентами к тому же дельнымии партнерами. Увидьте все ценностью заменимого номера компьютера собственно для бизнеса сами затем набирайте у Российскую Федерацию, украинцами, США, Канаду, Европой, казахами, германцами, еще также иные места без усилий и быстро, в удобное пору. Телефония с придуманных установкой допустит для Вас реализовать поступающие также изливающий вызовы у системе, тонко ставить соединение с городами, государством и контактами из любой точки территории целкиом без оплаты. Пользователи могут работать на SIP- страницу на ресурс, смартфоне, программах и электронных носителях.
    Данная фирма предоставляет регулировка всяческих версии изменений по резервом делать достаточно вызовов, бесплатные связь также диалоги, получение звонков в компьютер, соединять вместе с собой масштабную снабжение, организовать телефонный-отдел, регистрация вызовов, плюс еще направлять регистрацию осуществленных звонков к тому же контактов. Предприятие работаем по выше 7 лет к тому же сотрудничает с семьдесят три державы также 3000 столиц. Компания https://tel-number.ru известна к тому же авторитетна, поэтому хотим Вам обеспечиваем прыткое присоединение и более чем сто% гарантию атрибута. Пишите, включайте звонки к тому же осуществляйте личным производством совместно со современными потенциалом телефонии на всей планете.

    Ответить

  6. Обеспечить электро концепцию на доме, холле или на производственном учреждении наша команда считаем с помощью верного исполнителя — система теплый пол электрический цена , что сразу предоставит для Вам фирменную результат по подсветке также обогревающим источником здания различного плана. Наша компания справляется по бирже из две тысячи четвертого периода, и мы отменно делаем общение со персональными клинетами, обеспечивая Вам хороший сотрудничество по обслуживанию, подачи по указанный город также наличие требуемого число товара. Всегда у магазине потребители смогут купить светодиодное LED — приборы, светильники, шнуры также электропровода, автоматику, щитковое снаряжение, уравнители напряженности и регулировка теплого проводного пола.

    Звоните, затем наша команда на линии 30 минут поставим именно для Вас точное заключение личного просьбы на любой личного изделия и угождение. Обращайтесь тогда наглядно просмотрите лично у тому, что же нашей компании полагаются постоянные потребители, заказчики поручают положительные мнение, к тому же Prom. Ua вручил https://vip-techno.com.ua/ удостоверение свойство.

    Ответить

  7. ZacharyDed

    Производство матрацев. Реализация текстильной продукции

    http://bit.ly/2I5Rw9W — матрас подушка одеяло

    — любые объемы,
    — матрасы высочайшего качества,
    — самые выгодные цены

    https://goo.gl/5WYADp — купить матрац оптом

    Ответить

  8. Устроить отличные исправительные, монтажные к тому же демонтировочные работы лишь на поверхностным или же скрытой крае здания логично изящное занятие, та что дает право тщательно также бережно проделать только настуральные профи ремонтных работ. Строительная фирма Промышленный альпинизм по всяким наружным работам домов предоставляет под своих клиентов всяческие услуги именно по монтировке, ремонте, герметизации, выкраске, чистке также демонтировании жилища всякого варината.

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

    Строительная команда реализует заказ всякой комбинации сообразно прописанным вызову данным стандартам касательно приема современных манере, что превратят вид дома безопасным и привлекательным вона период воссоздания либо фундаментальных https://www.kirpichi-msk.ru/ строительных работ. Созвониться из нами возможно в любое годное для личное час по контактный номер либо почтовому ссылке.

    Ответить

  435. Please let me know if you’re looking for a article author for
    your site. You have some really great articles
    and I think I would be a good asset. If you ever want to take some
    of the load off, I’d love to write some articles
    for your blog in exchange for a link back to mine. Please send me an e-mail if interested.
    Thank you!

    Ответить

  439. Howdy, i read your blog occasionally and i own a similar one and i was just curious if
    you get a lot of spam feedback? If so how do you protect against it, any
    plugin or anything you can suggest? I get so much lately it’s driving me mad so any help
    is very much appreciated.

    Ответить

  445. I believe everything posted was actually very logical. But, what about this?

    suppose you added a little content? I ain’t suggesting your content isn’t good., but suppose
    you added something that grabbed a person’s attention? I
    mean ЛШТН. 1 день — Иосиф Дзеранов is a little boring.
    You should glance at Yahoo’s front page and note how they create post headlines to grab people interested.
    You might add a video or a related picture or two to get readers interested about everything’ve got to
    say. Just my opinion, it might make your blog a little bit more interesting.

    Ответить

  446. You’re so awesome! I do not suppose I’ve truly read anything like that before.
    So great to find someone with a few genuine thoughts
    on this subject matter. Seriously.. many thanks for starting this up.
    This website is one thing that is needed on the internet,
    someone with a little originality!

    Ответить

  448. Hi there! I know this is somewhat off topic but I was wondering if you knew where
    I could locate a captcha plugin for my comment form?
    I’m using the same blog platform as yours and I’m having difficulty finding one?
    Thanks a lot!

    Ответить

  450. What i don’t realize is in truth how you’re no longer actually a
    lot more well-preferred than you might be now. You’re very intelligent.
    You know therefore considerably in relation to this matter,
    produced me for my part imagine it from numerous numerous
    angles. Its like women and men are not fascinated unless it is one
    thing to accomplish with Lady gaga! Your own stuffs outstanding.
    Always care for it up!

    Ответить

  451. It’s perfect time to make some plans for the future and it is time to be happy.
    I have read this post and if I could I desire to suggest you
    few interesting things or tips. Perhaps you can write next articles referring to this article.

    I wish to read more things about it!

    Ответить

  452. We’re a group of volunteers and opening a new scheme in our community.
    Your website offered us with valuable information to work on. You’ve done
    an impressive job and our whole community will be thankful to
    you.

    Ответить

  453. Hey there would you mind sharing which blog platform
    you’re working with? I’m looking to start my own blog soon but I’m having a
    hard time choosing between BlogEngine/Wordpress/B2evolution and
    Drupal. The reason I ask is because your layout seems different then most blogs and I’m looking for something completely unique.
    P.S Apologies for being off-topic but I had to ask!

    Ответить

  454. I’m really enjoying the design and layout of your blog.
    It’s a very easy on the eyes which makes it much more pleasant for
    me to come here and visit more often. Did you hire out a developer
    to create your theme? Superb work!

    Ответить

  455. Its like you read my mind! You appear to know a lot about this, like
    you wrote the book in it or something. I think that you could do with some pics
    to drive the message home a bit, but instead of that,
    this is great blog. A great read. I’ll certainly be back.

    Ответить

  459. You actually make it seem so easy with your presentation but I find this
    topic to be really something that I think I would never understand.
    It seems too complicated and extremely broad for me.
    I’m looking forward for your next post, I will try to get the hang of it!

    Ответить

  461. I simply could not leave your website before suggesting that I really enjoyed the
    standard info a person provide in your visitors?
    Is going to be again ceaselessly to inspect new posts

    Ответить

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *