Відомий всеукраїнський конкурс юних науковців має своїх прихильників і своїх критиків.
Давайте для початку розберемося в тому, як це було до 2020 року.
Якщо учень в 11 класі пробився на всеукраїнській рівень в конкурсі МАН і в фіналі виборов диплом будь-якого ступеня, то йому при вступі до закладу вищої освіти України додавалось 10 балів. Це був величезний бонус, таким чином можна було вступити в університет значно вищого рівня. Крім того, це певні «запасні бали» на випадок, якщо абітурієнт не дуже вдало здав, наприклад, українську.
Додавав позитивізму факт, що протягом останніх двох років фінал МАН проводився в форматі «всі разом». Найрозумніші діти країни майже тиждень спілкувались між собою. Організація була чудова: діти жили в гарних готелях, їх системно харчували. І дуже важливо, що рівень спілкування всередині спільноти МАНівців був дуже високий, що також було серйозним аргументом і додавало приводів взяти участь в МАН. Два останні роки підряд мої учні брали участь у фіналі МАН у відділенні «комп’ютерних наук» і вони в один голос це підтверджують.
Для того, щоб попасти у фінал, треба було пройти обласний відбір, для чого написати власне саму наукову роботу, написати контрольну з базової дисципліни (в комп’ютерних науках це математика), презентувати і захистити свою наукову роботу перед журі, де, як правило, запитання задають як члени журі так і учні-конкуренти.
Щоб отримати диплом у фіналі, необхідно попасти в першу половину рейтингу, тобто якщо у фіналі в даній секції було 20 учасників, то треба попасти по рейтингу в першу десятку.
Критики такого положення звертали увагу на факт «повної загальності» конкурсу МАН. Можна було захистити роботу в секції «Кліматологія та метеорологія», при цьому написати контрольну з географії, а отримані додаткові 10 балів витратити для вступу в медичний університет. Критики системи вважали це дуже неправильним. Крім того, оцінювання учасників – вкрай складна тема, а коли мова йде не про шматок картону на ім’я «грамота», а про 10 балів для вступу в ВНЗ, то, звичайно, все стає на порядок складніше у суддівстві. Також критики такої системи висловлювались, що практично неможливо визначити автора роботи, що наукову роботу дуже часто пишуть зовсім не діти, а вчителі, що взагалі нівелює цінність конкурсу.
11 жовтня 2019 року наказом №1285 Міністерство освіти і науки України змінило правила.
Цитата:
«Призерам (особам, нагородженим дипломами I–III ступенів) IV етапу Всеукраїнських учнівських олімпіад в рік вступу з базових предметів, призерам III етапу Всеукраїнського конкурсу-захисту науково-дослідницьких робіт учнів - членів Малої академії наук України в рік вступу під час вступу на спеціальності, визначені Переліком спеціальностей, яким надається особлива підтримка (додаток 2), останній доданок встановлюється рівним 10, а якщо конкурсний бал вступника при цьому перевищує 200, він встановлюється таким, що дорівнює 200. Інформацію про них приймальні комісії отримують з ЄДЕБО.»
Отже, якщо призер фіналу МАН обере собі спеціальність, якої немає в додатку 2, то його 10 балів не враховується. Але перед тим, як представити додаток 2, звернемо увагу на ще одну важливу деталь з Умов прийому. Цитата:
Примітка. З 2021 року статус спеціальностей, яким надається особлива підтримка, надаватиметься спеціальностям (спеціалізаціям, предметним спеціальностям), з яких прохідний бал широкого конкурсу МОН не перевищує 130 балів, статус припиняється для спеціальностей (спеціалізацій, предметних спеціальностей), з яких упродовж двох попередніх років поспіль прохідний бал широкого конкурсу МОН становить не менше ніж 170 балів за умови набору усіма закладами вищої освіти (крім вищих військових навчальних закладів, закладів вищої освіти із специфічними умовами навчання, військових навчальних підрозділів закладів вищої освіти) не менше ніж 50 % від загального набору студентів на перший курс денної форми здобуття освіти на основі повної загальної середньої освіти за кошти фізичних та юридичних осіб.
Звичайною мовою: якщо цього року спеціальність є у Додатку 2, але прохідний бал на неї більше 170 балів і університети набирають на дану спеціальність більше 50% студентів, то спеціальність із додатку 2 на наступний рік зникне. А туди допишеться спеціальність, на яку прохідний бал малий, менше 130 балів. Тобто, спеціальності зовсім не рейтингові, скажемо прямо.
Цілком зрозуміло, що в додатку 2 прогнозовано немає комп’ютерних спеціальностей галузі знань 12 "Інфомаційні технології". Для вступу на топову 121 спеціальність «Інженерія програмного забезпечення» в 2020 році не допоможе ні призове місце в фіналі МАН ні призове місце в фіналі будь-якої всеукраїнської олімпіади. Там серед комп’ютерних залишилась лише неймовірно складна «124 – Системний аналіз», але якщо поспілкуватися зі студентами, що навчаються на даній спеціальності, наприклад, в ІПСА КПІ, можна зрозуміти, що вчитися там неймовірно складно. Скоріше за все, саме тому 124 спеціальність поки що залишається в Додатку 2.
На мою думку, цей закон дуже змінить розстановку сил в МАН. Сенс брати участь у МАН стрімко змінився. Знову таки, обидва мої учні, що пройшли до фіналу, і придумували і писали свої роботи самостійно, витративши на це море сил і часу. Який вони могли б витратити на підготовку до ЗНО. Звичайно, ми розраховували на 10 балів, тут ніякої таємниці немає. Щодо мотивації наступних МАНівців – питання, на мою думку, цілком зрозуміле.
Мова не про оцінювання даного закону або даного факту, мова про декларування зміни правил. Важливих правил для абітурієнтів.
І, обіцяний додаток №2 (на 2020 рік):
Додаток 2 до Умов прийому на навчання до закладів вищої освіти України в 2020 році (пункт 3 розділу III)
ПЕРЕЛІК спеціальностей, яким надається особлива підтримка
Шифр галузі
Галузь знань
Код спеціальності
Назва спеціальності
01
Освіта
014
Середня освіта (за основними предметними спеціалізаціями: 014.04 - 014.10, 014.15)
Даний довідник може стати вам у пригоді для розв'язку задач
Введення цілих чисел:
Якщо вам треба ввести ціле число від користувача в вашу програму, то використовуйте конструкцію:
x = int(input())
Якщо вам треба ввести два цілих числа, кожне з яких записане в окремому рядку, то це можна зробити так:
x = int(input())
y = int(input())
Якщо вам треба ввести в вашу програму кілька цілих чисел, що записані через пропуск, то це можна зробити так:
a, b, c = map(int, input().split())
Я підібрав для вас задачі таким чином, що в перших змаганнях вам для введення даних більше ніякі конструкції не потрібні.
Введення тексту:
Якщо вам треба ввести текст від користувача в вашу програму то використовуйте таку конструкцію:
x = input()
Якщо вам треба ввести текст від користувача в вашу програму, при цьому обрізати пропуски на початку тексту і в кінці, то використовуйте таку конструкцію:
x = input().strip()
Пам'ятайте, що з текстом не можна проводити математичні операції. З тексту ви можете вирізати один або кілька символів, але вирізана частина буде також текстом. Якщо ж вам треба виконати математичні дії з цими даними, то треба конвертувати текст в число. Якщо це стосується цілих чисел, то конструкція така:
y = int(x)
Задача для прикладу. Ваша програма повинна зчитати трицифрове натуральне число і вивести суму першої і останньої цифри.
Ось як може виглядати ваша програма:
x = input().strip()
a = int(x[0])
b = int(x[2])
print(a+b)
Виведення даних:
Для виведення даних використовується оператор print()
Приклад:
a = 5
b = 3
print(a-b)
Розгалуження:
Задача для прикладу:
Програма повинна прочитати з консолі ціле число та вивести -1, 0 або 1, якщо введене значення від’ємне, нульове і додатне, відповідно.
Приклад коду:
n = int(input())
if n < 0:
print(-1)
elif n == 0:
print(0)
else:
print(1)
Цикл FOR:
Задача для прикладу:
Програма повинна прочитати з консолі ціле число та вивести числа від одиниці до цього числа включно. Кожне число - в окремому рядку.
Приклад коду:
n = int(input())
for x inrange(1, n + 1):
print(x)
Задача для прикладу:
Програма повинна прочитати з консолі ціле число та вивести числа від цього числа до нуля в порядку зменшення. Кожне число - в окремому рядку.
Приклад коду:
n = int(input())
for x inrange(n, - 1, -1):
print(x)
Якщо це саме треба зробити так, щоб всі числа були в одному рядку, ось приклад:
Проста задача, в принципі. Знову таки, з дивно високим коефіцієнтом складності, 21%. Треба побудувати квадратну матрицю, як на обкладинках зошитів з математики. Вхідні дані - розмірність матриці, від 1 до 9 включно. Результат відповідним чином відформатувати:
n = 5
1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
4 8 12 16 20
5 10 15 20 25
n = 7
1 2 3 4 5 6 7
2 4 6 8 10 12 14
3 6 9 12 15 18 21
4 8 12 16 20 24 28
5 10 15 20 25 30 35
6 12 18 24 30 36 42
7 14 21 28 35 42 49
Запропонував Саша цю задачу. З приміткою «неробіт». Проходить 70% тестів. E-olimp, на відміну від codeforces, тести не відкриває, шукаємо помилку аналітично.
Чудовий в своєму різноманітті інструментарію Python дозволяє чудово форматувати текст при виводі. Нам треба вирівняти текст вправо в межах двох символів? Не проблема. Як просто і елегантно, правда?
Не дуже популярна у нас інтелектуальна гра – це відомий європейський хіт. Гра року Швеції (2005), Фінляндії (2006), Франції (2006), володар призу Mensa Select (2006). Абстрактна гра для двох гравців, винайдена Томасом Флоденом (Tomas Flodén). Комерційні права на Пентаго належать шведської кампанії Mindtwister Games. Гра має офіційний сайт, з 2006 року в технічному музеї в Стокгольмі проводиться чемпіонат з Pentago.
Стандартні класичні правила:
Гра проводиться на полі 6 на 6 лунок. Ігрове поле поділено на чотири сектори, кожний сектор обертається навколо своєї осі. Грають два гравця, у одного шари чорного кольору, у іншого – білого. Грають по черзі. Гравець кладе шар свого кольору в одну з вільних лунок після чого повинен повернути один будь-який з чотирьох секторів ігрового поля на 90 градусів або за годинниковою стрілкою або проти. Після чого ходить інший гравець своїм кольором шару аналогічним чином. Виграє той, хто побудує пряму лінію з п’яти шариків свого кольору по горизонталі, вертикалі або діагоналі. В принципі – все.
Ціна офіційної версії гри на Розетці – 600 гривень. Ціна китайської версії на Аліекспресі починається від 300 гривень. В Україні продається цікава версія для кількох гравців, трьома кольорами шарів і картками.
Коштує від 130 гривень. Якщо ви хочете з розширеної версії отримати класичну, можна купити шариків двох кольорів в потрібній кількості, або використати щось підручне, я, наприклад, розпустив дерев’яне намисто.
Цікаве, як на мене, відео-представлення гри від Светлани Коробач, вони в родині навіть трохи ускладнили правила:
Але на сайті e-olymp на початок 2020 року задача має рейтинг складності 41%. Це означає, що з тих, хто брався, 41% не змогли розв'язати дану задачу. Отже, умова:
Трицифрове число
https://www.e-olymp.com/uk/problems/5628
Дано ціле трицифрове число.
Переставляючи цифри цього числа створіть найменш можливе трицифрове число.
Вхідні дані
Одне ціле трицифрове число.
Вихідні дані
Відповідь до задачі.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані
132
Вихідні дані
123
Ще раз звертаю увагу на уважне читання умови. Трицифрове число, що є вхідними даними, може бути як додатнім, так і від'ємним. Якщо число додатнє, то, очевидно, що треба з трьох цифр сформувати якомога менше число. Саме такому випадку відповідає тестовий приклад:
Вхідні дані
132
Вихідні дані
123
Давайте візьмемо вхідними даними від’ємне число:
Вхідні дані
-132
Очевидно, що розв’язком задачі буде:
-321
Відповідно, якщо вхідне число – від’ємне, то нам треба перестановками сформувати якомога більше по модулю число.
Крім того, числа, що ми отримаємо після перестановки і які варті уваги, повинні бути трицифрові. Тобто, якщо у вхідних даних число 901, то ми можемо брати до уваги не всі варіанти перестановок, а лише ті, що трицифрові, а таких варіантів чотири: 901, 910, 109, 190. Бо всі інші (19, 91) не є трицифровими. Умову перевірки на трицифровість в даному випадку пропоную використати таку: x>99.
Зверніть увагу, всього з трицифрового числа без знака, можна сформувати перестановками ще п'ять чисел. Разом з вхідним числом буде шість чисел. Можуть бути повтори, звичайно, наприклад якщо вхідним числом буде 111.
Для початку пропоную запам’ятати, додатнє чи від'ємне у нас число. Далі будемо працювати з модулем числа, формуючи нові числа перестановками і додаючи нові числа в список. За допомогою list comprehension можна відфільтрувати нетризначні числа і, в залежності, від знака вхідного числа, знайти потрібне нам.
Виходить, що задача нескладна, якщо уважно прочитати і зрозуміти умову.
Ось один з варіантів самого простого розв’язку:
n = int(input())
s = str(abs(n))
i = []
i.append(int(s))
i.append(int(s[0] + s[2] + s[1]))
i.append(int(s[1] + s[2] + s[0]))
i.append(int(s[1] + s[0] + s[2]))
i.append(int(s[2] + s[1] + s[0]))
i.append(int(s[2] + s[0] + s[1]))
i = [x for x in i if x>99]
if n>0:
print(min(i))
else:
print(-max(i))
Звичайно, якщо мова йде про «здати задачу», то такий код нас влаштовує. Якщо ж ви отримали цю задачу на співбесіді при прийомі на роботу, то слабкою ланкою в коді є нарізання шматків тексту і формування з них нових чисел. Пайтон-програмер, що проводить співбесіду, побачивши таке, може подумати, що це ви просто зайшли погрітися. Логічно припустити, що у потужному і стильному Пайтоні існують інструменти, для того, щоб швидко і без помилок сформувати всі можливі варіанти перестановок. Звичайно, так і є, да ще і в стандартній бібліотеці, в модулі itertools. Наскільки краще читається тепер код, правда? Крім того, підправивши умову відбору тризначних чисел, даний код можна використати для n-значних чисел, не переживаючи, що можна помилитися в нарізанні текстових даних.
Перед самим Новим Роком дід Мороз вирішив знайти собі помічничку-Снігурку. Дідусь був трохи дивний – він боявся високих снігурок, але малі йому не подобались. Тому він шукав або таку, яка одного з ним зросту, або трошки меншу.
Дід Мороз прийшов на спеціальні курси і побачив там одночасно стоп’ятсот снігурок. Можна було, звичайно, мірятися зростом з кожною з них, але так можна було шукати до травня. Але дід був програмістом на Python і тому попросив снігурок вишукуватися в шеренгу, як на уроці фізкультури – відсортованими по зросту, від самої малої до самої високої.
Він поділив цю шеренгу навпіл, підійшов до снігурки, що була посередині і помірявся з нею зростом. Снігурка була вища зростом за діда Мороза. Це означало, що серед другої, високої половини снігурок йому пари немає, він їх всіх боїться, тому високу половину можна з пошуків виключити. Половину, що залишилась, він знову поділив на дві частини, підійшов до снігурки, що була посередині і помірявся з нею зростом. Ну і так далі до тих пір, поки не знайшов саме ту Снігурку, що шукав.
Подібний алгоритм пошуку, з поділом сортованого списку на дві частини зветься бінарним або двійковим пошуком. Це відомий і швидкий алгоритм.
І не просто так дід Мороз був програмістом на Python. Річ у тому, що в Python бінарний пошук вже є. Він реалізований в стандартній бібліотеці. Потрібні діду Морозу функції знаходяться в модулі bisect.
Якщо б всі снігурки були б різного зросту, то ось як просто діду Морозу знайти свою:
Результат: 4 (четверта в черзі, черга нумерується від нуля, це снігурка зі зростом 171)
А якщо зріст снігурок може дублюватися і діду Морозу підходить не одна, а кілька снігурок? Давайте ми йому в такому випадку скажемо кількість снігурок, що йому підходять, нехай сам з тим розбирається:
Вже тривалий час в Інституті Местецтв, Мутантів та Інформаційоних Технологій розводять милих різнокольорових звіряток. Для зручності кожний колір позначено своїм номером, усього кольорів не більше 109. В один з прекрасних днів у розпліднику сталося диво: усі тваринки вишикувалися в ряд в порядку зростання кольорів. Користуючись нагодою, лаборанти вирішили порахувати, скільки звіряток різних кольорів живе у розпліднику, і, за законом жанру, попросили вас написати програму, яка допоможе їм у вирішенні цього нелегкого завдання.
Вхідні дані
У першому рядку вхідного файлу міститься єдине число N (0 ≤ N ≤ 105) - кількість звіряток в Інституті. У наступному рядку знаходиться N упорядкованих за неспаданням невід'ємних цілих чисел, які не перевищують 109 і відокремлених пропусками - їх кольори. У третьому рядку файлу записано число M (1 ≤ M≤ 100000) - кількість запитів вашій програмі, у наступному рядку через пропуск записано M цілих невід'ємних чисел (які не перевищують 109+1).
Вихідні дані
Вихідний файл повинен містити M рядків. Для кожного запиту виведіть кількість звіряток заданого кольору у розпліднику.
Ліміт часу 4 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
10
1 1 3 3 5 7 9 18 18 57
5
57 3 9 1 179
Вихідні дані #1
1
2
1
2
0
Можна підряд перебирати список і шукати потрібні елементи. Але при такому підході ми не встигнемо розв’язати задачу за відведений час. Тому, розуміючи, що бінарний пошук – чудова по оптимальності штука, давайте використаємо саме його. Думаю, після допомоги діду Морозу в його пошуку Снігурок, лістинг програми «Мутанти» не потребує пояснень: