Код:
from turtle import *
def paint(x):
for i in range(x, x + 1):
circle(70 + x, x)
left(40)
if x < 100:
return paint(x + 1)
speed(0)
pensize(2)
color('darkviolet')
paint(5)
Завдання для допитливих: яку мінімальну кількість рядків цього коду треба змінити, щоб ручка розписувалась так само, але не проти, а за годинниковою стрілкою?
Успіхів!
В 1996 році ізраїльська компанія Mirabilis запустила програму миттєвого обміну повідомленнями на ім’я ICQ. В наших краях цю неймовірну для свого часу штуку звали аською. Після кількох перекупів, останній власник виключив ICQ у 2024 році.
Але поки все працювало, у кожного користувача ICQ був свій ідентифікатор, так званий UIN (Universal Identification Number), що складався з 5-9 цифр. У кого був менший номер, той, іноді, дійсно вважав себе крутішим. У різних часів різні дефекти )
Для свого часу аська була неймовірна штука, бо зручне миттєве спілкування в XX столітті на кожному кроці не валялося.
А після преамбули ми розглянемо задачу на ім’я ICQ:
https://www.eolymp.com/uk/problems/443
Умова:
У деякій школі у кожного школяра є свій особистий номер ICQ. У школі поширена думка, що чим менше значення номера ICQ, тим більш «продвинутим» є школяр. Відомо список всіх школярів з номерами ICQ. Потрібно вивести список K самих «продвинутих» школярів.
Вхідні дані
У першому рядку міститься кількість учнів у школі N (1 ≤ N ≤ 100) і число K (1 ≤ K ≤ N). Далі йде N рядків, у кожному рядку міститься прізвище школяра (без пропусків, містить не більше 20 рядкових латинських букв) і через пропуск номер ICQ (1 ≤ ICQ ≤ 10^9). Номера ICQ і прізвища у школярів різні.
Вихідні дані
Вивести прізвища K самих «продвинутих» школярів у лексикографічному порядку (за алфавітом). Кожне прізвище виводиться в окремому рядку.
Приклади
Вхідні дані #1
1 1
d 1
Відповідь #1
d
Обмеження на час виконання: 0,5 секунди
Обмеження на використання пам'яті: 64 мегабайти
Нам буде зручно використати структурований список даних, елементом якого буде запис, в якому буде прізвище користувача та номер ICQ. Двовимірний список в Python нам може стати у пригоді. Для пояснення ми використаємо свій приклад. Наприклад, у нас буде 8 учнів, у кожного буде свій номер, а обирати ми будемо трьох самих «продвинутих», тобто тих, у кого найменші номери ICQ. Не забуваємо, що прізвища цих трьох нам буде треба відсортувати у лексикографічному порядку, тобто за алфавітом.
Наш приклад:
8 3
umkin 92654
dudkin 22654
mamkin 12754
papkin 82654
bubkin 92654
memkin 87054
titkin 222454
babaikina 12254
Після введення даних в кожному записі у нас першим параметром буде прізвище, а другим – номер ICQ. Гарний спосіб відсортувати дані за номером ICQ (перший параметр) надає Python за допомогою функції itemgetter модуля operator. Так просто:
data.sort(key = operator.itemgetter(1))
Після сортування списку ми можемо обрати лише потрібну кількість записів (k).
Дискусійним може бути питання, чи краще коригувати вже існуючий список:
data = data[:k]
мінус такого рішення: ми назавжди губимо повний список учнів і їх номерів ICQ (хоча для даної задачі, після сортування нам цей список більше не потрібний)
чи заводити новий список:
data_result = data[:k]
мінус такого рішення: для нового списку ми використовуємо пам’ять, яку могли б не використовувати.
Як правильно і як краще для цієї задачі – чудова тема для обговорення з вчителем, університетським викладачем або практикуючим розробником (це можуть бути дуже різні люди)
Отже, повний лістинг такого підходу:
import operator
data = []
n, k = map(int, input().split())
for _ in range(n):
name, icq = input().split()
data.append([name, int(icq)])
data.sort(key = operator.itemgetter(1))
data_ = data[:k]
data.sort(key = operator.itemgetter(0))
for x in range(k):
print(data[x][0])
Ось результат роботи програми:
babaikina
bubkin
dudkin
Але можна відсортувати наші дані без використання функції «itemgetter». Для цього можна використати лямбда-функцію. Наприклад, так:
data = []
n, k = map(int, input().split())
for _ in range(n):
name, icq = input().split()
data.append([name, int(icq)])
data.sort(key = lambda x: x[1])
data = data[:k]
data.sort(key = lambda x: x[0])
for x in range(k):
print(data[x][0])
Можете порівняти ці різні варіанти сортування. Обидва коди здають задачу на 100%.
Обирайте, пробуйте, успіхів!
Вітаю!
Для малювання феєрверку вирішив циклічно змінювати кольори: червоний-синій-червоний-синій... Звичайно, можна змінювати актуальний колір за допомогою розгалуження. Але у нас в циклі є змінна циклу (x), яка в даному прикладі змінюється як парна-непарна-парна-непарна... Тому для задачі зміни кольору не потрібно витрачати час на розгалуження. В прикладі можна переглянути один з можливих варіантів.
from turtle import *
speed(0)
pensize(5)
c = ['red','blue']
right(45)
for x in range(15, 55):
penup()
forward(2 * x)
left(45)
pendown()
color(c[x % 2])
dot(20)
Темою випуску є чудова задача, представлена на ІІІ етапі Всеукраїнської олімпіади з інформатики в Житомирській області 26 січня 2024 р.
Балансуючі елементи:
https://basecamp.eolymp.com/uk/problems/11658
Умова:
Задано послідовність з N елементів, які є цілими числами. Назвемо «балансуючим елементом» такий, що сума всіх елементів перед ним дорівнює сумі елементів після нього. При цьому перший та останній елементи послідовності не можуть бути «балансуючими».
Знайдіть кількість «балансуючих елементів» у заданій послідовності.
Вхідні дані
У першому рядку записане ціле число N. У другому рядку записано N цілих чисел, розділених пробілом. Всі числа не перевищують за модулем 100000.
Вихідні дані
Виведіть одне число – кількість «балансуючих елементів».
Приклади
Вхідні дані #1
3
1 2 1
Відповідь #1
1
Звичайно, ми можемо розмістити елементи у список, що дозволить зручно їх опрацьовувати.
Один з очевидних підходів полягає у виборі потенційно балансуючого елемента, починаючи від другого і до передостаннього і розрахунку суми елементів зліва від нього і справа від нього. Якщо ці дві суми співпадають, то елемент є «балансуючим» і ми збільшуємо лічильник кількості «балансуючих» елементів.
Звичайно, це гарно: if sum(s[:x]) == sum(s[x + 1:]), але головна проблема такого підходу полягає в тому, що нам при аналізі кожного потенційно балансуючого елемента необхідно двічі виконати операцію підрахунку суми елементів, зліва і справа. А це займає багато часу. І тому код на основі такого алгоритму не проходить по часу всі тести. На Python точно не проходить. Чудово, що автори задачі так підібрали тести, що це мотивує шукати більш оптимальні розв'язки.
Наступний алгоритм, більш оптимальний, полягає в тому, що при аналізі ми можемо рахувати суму елементів лише з одного боку. На початку програми ми можемо один раз підрахувати суму всіх елементів. А далі обирати циклом потенційного кандидата на роль балансуючого елемента і рахувати суму елементів, наприклад, лише зліва від нього. Тоді, якщо елемент, що розглядається, дійсно балансуючий, то загальна сума всіх елементів, мінус значення самого елементу, повинні дорівнювати подвійній сумі зліва. Це і буде означати, що сума зліва дорівнює сумі справа. Але і тут у нас при аналізі кожного елементу буде потрібно рахувати суму всіх елементів зліва від нього. А це також не швидко. Автори задачі знову чудово підібрали тести і Python-код на основі даного алгоритму не розв’язує повністю задачу за визначений час.
Розглянемо ще більш оптимальний алгоритм. Ми взагалі не будемо при аналізі кожного елементу рахувати суму зліва. Давайте визначимо якусь змінну, наприклад «left», в якій будемо накопичувати суму елементів зліва від того, що наразі аналізується. Коли ми перейдемо до наступного елемента, ми просто додамо до значення змінної «left» значення одного єдиного елемента, того що лівіше. Це буде значно швидше. Переглянувши всі елементи з другого до передостаннього, накопичуючи значення змінної «left» і маючи один раз пораховану на початку програми суму всіх елементів, ми за визначений час розв’яжемо задачу на 100%.
Кода не буде, якщо у вас не виходить це розписати, питайте.
Успіхів!
Представляю простий інструмент, такий собі метод малих колективних проєктів: коротких, простих, легких, об’єднуючих. Тим більше актуальний на тлі тривалих відключень електрики під час навчання.
Правила: колектив учнів обирає коробку пазлів. Очевидне завдання полягає в тому, щоб зібрати ці пазли, але при важливій умові: під час збирання учням заборонено спілкуватися між собою. Виключити цей канал комунікації. Взагалі. мУкати також не можна. А ще битися не можна, про це відразу питають :)
Для того, щоб не було критично тихо і сумно, вчитель може включити музику. З музикою не проблема навіть без електрики, особисто я використовую радіоприймач на акумуляторі, що вміє програвати mp3. З репертуаром треба пробувати, одній компанії гарно заходить chillout-музика, іншій — динамічно-танцювальна.
Якщо колектив серйозний, як, наприклад, гурток програмістів, то їм можна відразу дати велику коробку. Вони все одно перед збиранням обговорюють оптимізацію і працюють як легендарний німецький годинник — чітко та злагоджено. Ось, менше ніж за годину зібрали пазл на 500 елементів під медитативну музику:
Для середньої школи гарно підходять пазли на 80 елементів з картинками українських казок. Тим більше, можна згадати свої казки, особисто Ви — можете переказати от зараз казку про кривеньку качечку? Яку кількість елементів краще обрати для самої молодшої школи, думаю, варто попитати вчителів, що практично працюють з цими дітьми. Якщо група велика, можливо, варто розділити, бо хтось просто не протиснеться до столу. Я викоростовую спеціальну площину для роботи, але підійде і велика парта чи стіл.
На фоні збирання пазлів можна додавати завдання. Наприклад, після збирання пазлу можна обговорити що то за казка і крім представлення безпосередньо пазлу ще і театрально представити саму казку. Короткою сценкою, наприклад. Або розповіддю-презентацією. І лише тоді завдання буде прийнято, бо буде і пазл і представлення.
Звичайно, можна додавати інші завдання, враховуючи аудиторію та настрій.
Завдання вчителя — не заважати, слідкувати, щоб не почали спілкуватися, щоб не побилися, підібрати музику. А ще перед тим, як розпочати, вчителю варто зробити кілька кольорових копій коробки, щоб у дітей було кілька картинок того, що вони збирають.
Мінімум часу, мінімум обладнання, море задоволення. Тихі музичні пазли:
Анатолій Анатолійович,
листопад 2024
У 2012 році дослідники з лабораторії Ісікава Ватанабе Токійського університету створили робота-руку, який може грати в камінь-ножиці-папір із 100%-ним коефіцієнтом перемоги проти людини. Використовуючи високошвидкісну камеру, робот протягом однієї мілісекунди розпізнає, яку форму створює людська рука, а потім створює відповідну виграшну форму. © Вікіпедія.
Історія з епіграфу чудово демонструє, що до однієї тої самої події можна підходити по-різному. З точки зору алгоритму швидкого розпізнавання жестів достатно різних по фізиології людей — то можна привітати дослідників з успіхом. Якщо подивитися з точки зору справедливості, то тих би самих японських розробників в справедливому селі беззлобно побили б, а робота-руку втопили б у найближчій річці. Бо нечесно. Це так само, коли на Паску хтось хитрий намагається стукатися фарбованим дерев’яним яйцем.
Варто зауважити, що існує інший підхід і навіть змагання алгоритмів для цієї гри. Наприклад, Iocaine Powder, який виграв Перший міжнародний конкурс програмістів RoShamBo у 1999 році, використовує евристично розроблену компіляцію стратегій. Оптимальна стратегія або метастратегія вибирається на основі минулих результатів. Основними стратегіями, які він використовує, є зіставлення історії, частотний аналіз і випадкове вгадування. Його найсильніша стратегія, зіставлення історії, шукає послідовність у минулому, яка збігається з кількома останніми ходами, щоб передбачити наступний хід алгоритму. У частотному аналізі програма просто визначає хід, який найчастіше грають. Випадкова здогадка — це запасний метод, який використовується для запобігання нищівним втратам у разі невдачі інших стратегій.
Чого тільки не дізнаєшся у Вікіпедії! Привіт. Розглянемо задачу, створену за мотивами відомої гри. В старій версії сайту eolymp.com було вказано джерело задачі: 2007 ACM North America - Pacific Northwest, Problem A.
Умова:
Камінь, Ножиці чи Папір?
https://basecamp.eolymp.com/uk/problems/1215
У гру Камінь, Ножиці, Папір грають двоє. Кожен гравець на рахунок три одночасно вибирає один з трьох предметів. Гра триває певну наперед встановлену кількість раундів. Гравець, який виграє більшу частину раундів, оголошується переможцем. За заданою кількістю раундів та їх результатам необхідно визначити переможця.
Наступні правила описують правила перемоги:
Вхідні дані
Перший рядок містить кількість тестів t (0 < t < 1000). Перший рядок кожного тесту містить кількість раундів n (0 < n < 100), зіграних у гру Камінь, Ножиці, Папір. Кожен з наступних n рядків містить одну з великих літер R (Камінь), P (Папір) або S (Ножиці), пропуск і знову велику літеру R, P чи S. Перша літера позначає вибір першого гравця; друга літера - вибір другого гравця.
Вихідні дані
Для кожного тесту в окремому рядку вивести ім'я переможця (Player 1 чи Player 2). Якщо гра завершується унічию, вивести TIE.
Приклади
Вхідні дані:
3
2
R P
S R
3
P P
R S
S R
1
P R
Відповідь:
Player 2
TIE
Player 1
Пропоную залишити без розгляду питання кількості тестів і раундів. Вкладені цикли це чудово розв’язують і матеріалів в цьому напрямку — море. Давайте розглянемо задачу по суті.
Одна гра — це коли два учасники одночасно викидують фігуру. Це може бути або Камінь (Rock), або папір (Paper) або ножиці (Scissors). Зліва записується буква фігури першого гравця, справа — буква фігури другого.
Пропоную піти простим шляхом. Записати всі можливі варіанти, які можуть випасти:
R R
R P
R S
P P
P R
P S
S R
S P
S S
Вісім варіантів. Чому саме вісім? Всі бачуть формулу? Якщо два учасника і три фігури (R P S), то виходить вісім. Якщо було б тих самих два учасника і чотири фігури, наприклад, RPSF то скільки було б варіантів? Можна виписати на листочку всі можливі і тоді, думаю, ви точно побачите формулу-залежність.
Пропоную вилучити «нічійні» варінти з наших восьми, залишилось шість:
R P
R S
P R
P S
S R
S P
Ділимо ці варінти на дві групи. Нагадаю, що як зветься: камінь (R), папір (P), ножиці (S).
Запишемо ті варіанти, коли виграє перший гравець:
R S
P R
S P
Запишемо ті варіанти, коли виграє другий гравець:
R P
P S
S R
Формулюємо:
Якщо випадає комбінація R S або P R або S P, то додаємо один бал до кількості виграшів першого гравця, якщо випадає комбінація R P або P S або S R, то додаємо один бал до кількості виграшів другого гравця. Коли раунд завершується, аналізуємо кількості виграшів гравців і виводимо відповідне повідомлення, скидуємо лічильники виграшів і починаємо новий раунд.
Для тих, хто готовий писати код, успіхів. Для тих, хто не готовий — варіант кода є тут.
Успіхів!
У програмуванні багато чого можна робити по-різному. Підходи, методи, інструменти, оцінки якості варіантів, оптимізація — все це є цілим світом, різноманітним і захопливим. Пропоную сьогодні розглянути близьку, хоч і менш масштабну тему — взяти просту задачу і розв’язати її двома різними інструментами. Обидва, звичайно, мають свої переваги і недоліки, отже буде про що подумати тим, хто таке любить.
Задача: Кульки
(https://basecamp.eolymp.com/uk/problems/113)
У продавця повітряних кульок є n кульок. Кожна з них має деякий колір. Але зовсім недавно Три Товстуни видали наказ, який дозволяє торгувати кульками тільки якогось одного кольору. Щоб не порушувати закон, але при цьому і не втратити прибуток, продавець вирішив перефарбувати деякі із своїх кульок.
Напишіть програму для визначення мінімальної кількості перефарбувань.
Вхідні дані
В першому рядку задано кількість кульок n (1 ≤ n ≤ 100000). Другий рядок містить n цілих чисел, в межах від 1 до 9, що визначає колір кульок (1 - синій, 2 - зелений, 3 - голубий, 4 - червоний, 5 - рожевий, 6 - жовтий, 7 - сірий, 8 - чорний, 9 - білий).
Вихідні дані
Виведіть мінімальну кількість кульок, які необхідно перефарбувати, щоб всі кульки були одного кольору.
Приклади
Вхідні дані #1
4
3 1 2 1
Відповідь #1
2
Вхідні дані #2
4
4 9 9 6
Відповідь #2
2
Вхідні дані #3
1
1
Відповідь #3
0
Проаналізувавши приклади бачимо, що задача нескладна. Нам треба якомога менше кульок перефарбувати? Тоді давайте знайдемо, найбільшу кількість кульок одного кольору, а всі інші — перефарбуємо. Може бути варіант з повтором найбільшої кількості, наприклад 1 1 2 3 3. Але то не проблема, найбільша кількість кульок одного кольору — дві. А вже які ми будемо перефарбовувати, чи то 2 3 3 чи то 1 1 2 — для нашої задачі неважливо. В будь-якому варіанті перефарбувати доведеться три кульки.
В Python, як і в багатьох інших сучасних мовах програмування є можливість порахувати кількість елементів множини, що відповідає критерію. У нас в задачі всього дев’ять кольорів, тому давайте пошукаємо кількість кульок кожного кольору, знайдемо найбільшу з них і визначимо кількість кульок, які треба перефарбувати. Наприклад, так:
n = int(input())
b = [x for x in input().split()]
c1 = b.count('1')
c2 = b.count('2')
c3 = b.count('3')
c4 = b.count('4')
c5 = b.count('5')
c6 = b.count('6')
c7 = b.count('7')
c8 = b.count('8')
c9 = b.count('9')
print(n - max(c1, c2, c3, c4, c5, c6, c7, c8, c9))
Цей код здає задачу на 100%. Можна поговорити про оптимальність, про красу коду, посварити за дев’ять змінних, може було б гарніше тримати дані по кількостям в списку. Це на ваш розсуд. Як на мене — цей розв’язок простий і зрозумілий. Традиційне запитання адептів уніфікованих рішень «А якщо кольорів буде не дев’ять, а стомільонів?» пропоную не розглядати, бо то буде інша умова, відповідно, інша задача і даний код може бути неоптимальним, а то і непрацюючим взагалі. Ми ж розглядаємо не універсальну, а конкретну задачу.
Але ж в Python так багато смачного… Є відчуття, що код може бути гарніший. Може :) Давайте спробуємо Counter з модуля collections.
Припускаємо, що у нас є двадцять кульок різних кольорів, наприклад, таких
1 2 3 7 1 5 6 7 4 7 4 2 7 8 1 4 7 9 8 9
Давайте ми ці значення закинемо у список, а список віддамо в Counter. Що буде? Ось код:
from collections import Counter
n = int(input())
b = [x for x in input().split()]
c = Counter(b)
print(c)
Ось що буде:
Counter({'7': 5, '1': 3, '4': 3, '2': 2, '8': 2, '9': 2, '3': 1, '5': 1, '6': 1})
Кольору «7» — п’ять кульок, кольору «1» — три кульки, кольору «4» — три кульки і т.д.
І, очікувано, ми можемо визначити найбільш популярний колір:
print(c.most_common(1)[0][0])
І кількість кульок цього найпопулярнішого кольору:
print(c.most_common(1)[0][1])
Весь код розв’язку цієї задачі з використанням Counter:
from collections import Counter
n = int(input())
b = [x for x in input().split()]
c = Counter(b)
print(n - c.most_common(1)[0][1])
Як на мене, цей код теж має право на існування. Знайдуться ті, кому він подобається і ті, кому ні. Буде тема для обговорення. Може кому буде цікаво, в офіційному Python-help при поясненні Counter автори рахують кількість найпопулярніших слів в файлі hamlet.txt :)
Якщо вас зацікавила тема, у нас на «Плетиві» вже є стаття, де описано використання Counter, там розв'язується задача «Покер».
Успіхів!