Embedded Files
Задача А. Шоколадка
Задача А. Шоколадка
Задача Chocolates. Петрик святкував день народження 3 листопада і вирішив пригостити однокласників шоколадками. Шоколадка коштувала N грн. З першого листопада вартість шоколадки збільшилась рівно на Р відсотків. Визначте скільки шоколадок зможе купити Петрик на S грн після подорожчання.
Технічні умови. Програма Chocolates читає з пристрою стандартного введення (клавіатури) 3 цілих числа: N (1 ≤ N ≤ 10^7) - вартість шоколадки до подорожчання, Р (0 ≤ Р ≤ 100) - величина подорожчання шоколадки у відсотках, S (1 ≤ S ≤ 10^7) - сума грошей, яка є у Петрика. Програма виводить одне число - кількість шоколадок, які може купити Петрик.
Приклад:
Введення
25
5
100
Виведення
3
Підказка >>>
Підказка >>>
Склади формулу 100S/N(100+P)
Розв'язок Python >>>
Розв'язок Python >>>
f1=open('input.txt', 'r')
f2=open('output.txt', 'w')
n=int(f1.readline())
p=int(f1.readline())
s=int(f1.readline())
result=int(s//(n*(100+p)/100))
f2.write(str(result))
f1.close()
f2.close()
Задача В. Напрямок
Задача В. Напрямок
Задача Raft. Петрик влітку відпочиває у бабусі в селі. Особливо йому подобається купатись на сільському озері. Посередині озера плаває пліт, який має форму прямокутника. Сторони плота спрямовані уздовж паралелей і меридіанів. Введемо систему координат, в якій вісь ОХ направлена на схід, а вісь ОY - на північ. Нехай південно-західний кут плоту має координати (x1, y1), північно-східний кут - координати (x2, y2). Петрик знаходиться в точці з координатами (x, y). Визначте, до якої сторони плоту (північної, південної, західної чи східної) або до будь-якого кута плоту (північно-західному, північно-східному, південно-західному, південно-східному) Петрику потрібно плисти, щоб якомога швидше дістатися до плоту.
Технічні умови. Програма Raft читає з пристрою стандартного введення шість чисел в наступному порядку: x1, y1 (координати південно-західного кута плоту), x2, y2 (координати північно-східного кута плоту), x, y (координати Петрика). Всі числа цілі і по модулю не перевершують 100. Гарантується, що x1 < x2, y1 < y2, x ≠ x1, x ≠ x2, y ≠ y1, y ≠ y2, координати Петрика знаходяться поза плотом. Якщо Петрику слід пливти до північної сторони плоту, програма повинна вивести на пристрій стандартного виведення символ «N», до південної - символ «S», до західної - символ «W», до східної - символ «E». Якщо Петрику слід пливти до кута плоту, потрібно вивести один з наступних рядків: «NW», «NE», «SW», «SE».
Приклад:
Введення
-1
-2
5
3
-4
6
Виведення
NW
Підказка >>>
Підказка >>>
Розділіть озеро лініями на 8 частин і запишіть умови на x та y.
Розв'язок Python >>>
Розв'язок Python >>>
f1=open('input.txt', 'r')
f2=open('output.txt', 'w')
x1=int(f1.readline())
y1=int(f1.readline())
x2=int(f1.readline())
y2=int(f1.readline())
x=int(f1.readline())
y=int(f1.readline())
if y>y2 and x<x1:
result='NW'
if y>y2 and x>x2:
result='NE'
if y<y1 and x<x1:
result='SW'
if y<y1 and x>x2:
result='SE'
if y>y2 and x>x1 and x<x2:
result='N'
if y<y1 and x>x1 and x<x2:
result='S'
if y>y1 and y<y2 and x<x1:
result='W'
if y>y1 and y<y2 and x>x2:
result='E'
f2.write(result)
f1.close()
f2.close()
Задача C. Пакування речей
Задача C. Пакування речей
Задача laying. Бізнесмен Петро Петрович збирає речі у відпустку. З собою в літак він може взяти ручну поклажу і багаж. Для ручної поклажі у нього є рюкзак, а для багажу – здоровенна валіза. За правилами перевезення маса ручної поклажі не повинна перевищувати S кг, а багаж може бути будь-якої маси (за наднормативний багаж Петро Петрович готовий доплатити). Зрозуміло, найбільш цінні речі - ноутбук, фотоапарат, документи і т. д. – Петро Петрович хоче покласти в ручну поклажу. Петро Петрович розклав усі свої речі в порядку зменшення їх цінності і починає складати найбільш цінні речі в рюкзак. Він діє в такий спосіб - бере найцінніший предмет, і якщо його маса не перевищує S, то кладе його в рюкзак, інакше кладе його до валізи. Потім він бере наступний за цінністю предмет, якщо його можна покласти в рюкзак, тобто якщо його маса разом з масою вже покладених в рюкзак речей не перевищує S, то кладе його в рюкзак, інакше до валізи, і таким же чином процес триває для всіх предметів в порядку спадання їх цінності. Визначте вагу рюкзака і валізи після того, як Петро Петрович складе всі речі.
Технічні умови. Програма laying читає з пристрою стандартного введення число S (1 ≤ S ≤ 2 × 10^9) – максимально дозволенa вага рюкзака та число N (1 ≤ N ≤ 10^5) - кількість предметів. У наступному рядку дано N чисел через пропуски - маси предметів, самі предмети перераховані в порядку спадання цінності (спочатку вказана маса найціннішого предмета, потім маса другого по цінності предмета і т. д.). Всі числа натуральні, сума ваг всіх предметів не перевищує 2 × 10^9. Програма виводить на пристрій стандартного виведення два числа - вагу рюкзака і вагу валізи (вага порожнього рюкзака і валізи не враховується).
Приклад:
Введення
10
4
6
3
2
1
Виведення
10 2
Підказка >>>
Підказка >>>
Просто змоделювати процес, котрий описаний в умові задачі. Це можна було робити разом із зчитуванням предметів.
Розв'язок Python >>>
Розв'язок Python >>>
f1=open('input.txt', 'r')
f2=open('output.txt', 'w')
s=int(f1.readline())
n=int(f1.readline())
# m - маса окремого предмета
mr=0
mv=0
i=0
while i<n:
m=int(f1.readline())
if m<=s-mr:
mr=mr+m
else:
mv=mv+m
i=i+1
f2.write(str(mr)+' '+str(mv))
f1.close()
f2.close()
Задача D. Розбиття на групи
Задача D. Розбиття на групи
Степан виписує на листочку усі цілі числа від 1 до N в кілька груп, при цьому якщо одне число ділиться на інше, то вони обов'язково будуть у різних групах.
Наприклад, якщо N = 9, то отримаємо 4 групи:
Перша група: 1.
Друга група: 2 3 7.
Третя група: 4 5 6.
Четверта група: 8 9.
Очевидно, що оскільки, будь-яке число ділиться на 1, то одна група завжди буде складатись тільки з числа 1, а от інші групи можуть бути створені різними способами.
Допоможіть Степану, напишіть програму, яка визначає мінімальне число груп, на яке можна розбити усі числа від 1 до N у відповідності до наведеної вище умови.
Формат вхідних даних: Перший рядок вхідних даних містить єдине число N (1 ≤ N ≤ 10^9). Формат вихідних даних: Виведіть одне число - знайдену мінімальну кількість груп.
Приклад:
Вхідні дані
9
Вихідні дані
4
Підказка >>>
Підказка >>>
Відповіддю в залежності від числа N є к-сть степеней 2(двійки), котрі не перевищують числа N.Іншими словами відповідь = log2(N) + 1 округлений донизу.
Розв'язок Python >>>
Розв'язок Python >>>
f1=open('input.txt', 'r')
f2=open('output.txt', 'w')
n=int(f1.readline())
result=0
s=1
while s<=n:
s=s*2
result=result+1
f2.write(str(result))
f1.close()
f2.close()
Задача Е. Новий податок в Ужляндії
Задача Е. Новий податок в Ужляндії
Задача Mountain. Для поповнення бюджету країни, що відома своїми гірськими маршрутами, ввели новий податок для альпіністів. Величина податку пропорційна довжині маршруту, але, оскільки маршрут проходить по горах і пройдену відстань, яка залежить від висоти спуску і підйому, підрахувати складно, податок утримується без урахування висоти, тобто величина податку пропорційна горизонтальному переміщенню туристичної групи. Крім того, в силу старовинного звичаю усі туристичні групи повинні переміщатися по горах строго із заходу на схід. Експедиція хоче заощадити на податку, тому вона розробляє гірський маршрут з мінімальною величиною податку. При цьому, оскільки маршрут є гірським, він повинен містити підйом в гору і спуск з гори, тобто на маршруті має бути точка, яка знаходиться строго вище початку і кінця маршруту.
Альпіністи склала карту, що містить інформацію про висоту гір при пересуванні із заходу на схід. Висоти гір виміряні в точках через рівні відстані. Знайдіть на цій карті туристичний маршрут, за який податок буде мінімальний, а підйом та спуск, як і личить альпіністам, буде на маршруті.
Технічні умови. Програма Mountain читає з пристрою стандартного введення число N - кількість точок на карті гір. У наступному рядку N чисел через пропуск містять інформацію про висоту гір в даних N точках при русі із заходу на схід. Всі числа натуральні, не перевищують 10^5. Програма виводить два числа - номер точки початку маршруту і номер точки закінчення маршруту. Точки нумеруються від 1 до N. Якщо маршруту, що задовольняє умовам, не існує, програма повинна вивести одне число 0. Якщо знайдеться декілька маршрутів, то вивести той що починається ближче до точки старту експедиції.
Приклади:
Введення
7
18 10 15 20 20 10 3
Виведення
3 6
Введення
3
9 8 5
Виведення
0
Підказка >>>
Підказка >>>
Дана задача була найважчою задачею олімпіади, адже в ній треба було реалізувати структуру даних, котра могла відшуковувати мінімум/максимум. Однією зі відомих структур даних це дозволяє робити дерево відрізків/інтервалів. Алгоритм розв’язку наступний:
Заведемо два дерева відрізків, один буде для значень, котрі будуть зліва, інше – те , що буде справа.
Будемо рухатися зліва направо, кожного разу будемо перераховувати відповідь і перебудовувати наші дерева відрізків.
Page updated
Google Sites
Report abuse