Задача A -Шоколадка
Full
score:
|
100
|
Time
limit:
|
100
ms
|
Real
time limit:
|
5
s
|
Memory
limit:
|
64M
|
Шоколадка
Степан вирішив пригостити однокласників шоколадками.
Шоколадка коштувала N грн. З першого листопада вартість шоколадки
збільшилась рівно на Р відсотків. Визначте скільки шоколадок зможе
купити Степан на S грн після подорожчання.
Формат вхідних даних:
У першому рядку задано число N (1 ≤ N ≤ 107) -
вартість шоколадки до подорожчання. У другому рядку Р (0 ≤ Р ≤ 100) -
величина подорожчання шоколадки у відсотках. В третьому рядку - S (1 ≤ S ≤
107) - сума грошей, яка є у Степана.
Формат вихідних даних:
Виведіть одне число - кількість шоколадок, які може
купити Степан.
Examples
Input
|
Output
|
25
5
100
|
3
|
Задача B - Напрямок руху
Full
score:
|
100
|
Time
limit:
|
100
ms
|
Real
time limit:
|
5
s
|
Memory
limit:
|
64M
|
Напрямок руху
Степан влітку відпочиває у бабусі в селі. Особливо
йому подобається купатись на сільському озері. Посередині озера плаває пліт,
який має форму прямокутника. Сторони плота спрямовані уздовж паралелей і
меридіанів. Введемо систему координат, в якій вісь ОХ направлена на схід, а
вісь ОY - на північ. Нехай південно-західний кут плоту має координати (x1,
y1), північно-східний кут - координати (x2, y2).
Cтепан знаходиться в точці з координатами (x, y). Визначте, до якої сторони плоту (північної, південої, західної чи східної) або до будь-якого кута плоту (північно-західному, північно-східному, південно-західному, південно-східному) Степану потрібно плисти, щоб якомога швидше дістатися до плоту.
Формат вхідних даних:
Дано шість чисел в наступному порядку: 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».
Examples
Input
|
Output
|
-1
-2
5
3
-4
6
|
NW
|
Задача C - Пакування речей
Full
score:
|
100
|
Time
limit:
|
200
ms
|
Real
time limit:
|
5
s
|
Memory
limit:
|
64M
|
Пакування речей
Степан збирає речі у відпустку. З собою в літак він
може взяти ручну поклажу і багаж. Для ручної поклажі у нього є рюкзак, а для
багажу - здоровенна валіза.
За правилами перевезення маса ручної поклажі не повинна перевищувати S кг, а багаж може бути будь-якої маси (за наднормативний багаж Степан готовий доплатити). Зрозуміло, найбільш цінні речі - ноутбук, фотоапарат, документи і т. д. - Степан хоче покласти в ручну поклажу.
Степан розклав усі свої речі в порядку зменшення їх цінності і починає складати найбільш цінні речі в рюкзак. Він діє в такий спосіб - бере найцінніший предмет, і якщо його маса не перевищує S, то кладе його в рюкзак, інакше кладе його до валізи. Потім він бере наступний за цінністю предмет, якщо його можна покласти в рюкзак, тобто якщо його маса разом з масою вже покладених в рюкзак речей не перевищує S, то кладе його в рюкзак, інакше до валізи, і таким же чином процес триває для всіх предметів в порядку спадання їх цінності.
Визначте вагу рюкзака і валізи після того, як Степан складе всі речі.
За правилами перевезення маса ручної поклажі не повинна перевищувати S кг, а багаж може бути будь-якої маси (за наднормативний багаж Степан готовий доплатити). Зрозуміло, найбільш цінні речі - ноутбук, фотоапарат, документи і т. д. - Степан хоче покласти в ручну поклажу.
Степан розклав усі свої речі в порядку зменшення їх цінності і починає складати найбільш цінні речі в рюкзак. Він діє в такий спосіб - бере найцінніший предмет, і якщо його маса не перевищує S, то кладе його в рюкзак, інакше кладе його до валізи. Потім він бере наступний за цінністю предмет, якщо його можна покласти в рюкзак, тобто якщо його маса разом з масою вже покладених в рюкзак речей не перевищує S, то кладе його в рюкзак, інакше до валізи, і таким же чином процес триває для всіх предметів в порядку спадання їх цінності.
Визначте вагу рюкзака і валізи після того, як Степан складе всі речі.
Формат вхідних даних:
Перший рядок вхідних даних містить число S (1 ≤
S ≤ 2 × 109) - максимальнодозволенa вага рюкзака. У другому рядку вхідних
даних записано число N (1 ≤ N ≤ 105) - кількість предметів.
У наступних N рядках дано маси предметів, самі предмети перераховані в порядку спадання цінності (спочатку вказана маса найціннішого предмета, потім маса другого по цінності предмета і т. Д.). Всі числа натуральні, сума ваг всіх предметів не перевищує 2 × 109.
У наступних N рядках дано маси предметів, самі предмети перераховані в порядку спадання цінності (спочатку вказана маса найціннішого предмета, потім маса другого по цінності предмета і т. Д.). Всі числа натуральні, сума ваг всіх предметів не перевищує 2 × 109.
Формат вихідних даних:
Виведіть два числа - вагу рюкзака і вагу валізи
(вага порожнього рюкзака і валізи не враховується).
Examples
Input
|
Output
|
10
4
6
3
2
1
|
10
2
|
Задача D-Розбиття на групи
Full
score:
|
100
|
Time
limit:
|
100
ms
|
Real
time limit:
|
5
s
|
Memory
limit:
|
64M
|
Розбиття на групи
Степан виписує на листочку усі цілі числа від 1 до N в
кілька груп, при цьому якщо одне число ділиться на інше, то вони обов'язково
будуть у різних групах.
Наприклад, якщо N = 9, то отримаємо 4 групи:
Перша група: 1.
Друга група: 2 3 7.
Третя група: 4 5 6.
Четверта група: 8 9.
Очевидно, що оскільки, будь-яке число ділиться на 1, то одна група завжди буде складатись тільки з числа 1, а от інші групи можуть бути створені різними способами.
Допоможіть Степану, напишіть програму, яка визначає мінімальне число груп, на яке можна розбити усі числа від 1 до N у відповідності до наведеної вище умови.
Наприклад, якщо N = 9, то отримаємо 4 групи:
Перша група: 1.
Друга група: 2 3 7.
Третя група: 4 5 6.
Четверта група: 8 9.
Очевидно, що оскільки, будь-яке число ділиться на 1, то одна група завжди буде складатись тільки з числа 1, а от інші групи можуть бути створені різними способами.
Допоможіть Степану, напишіть програму, яка визначає мінімальне число груп, на яке можна розбити усі числа від 1 до N у відповідності до наведеної вище умови.
Формат вхідних даних:
Перший рядок вхідних даних містить єдине число N
(1 ≤ N ≤ 109).
Формат вихідних даних:
Виведіть одне число - шнайдену мінімальну кількість
груп.
Examples
Input
|
Output
|
9
|
4
|
Задача E - Новий податок в Ужляндії
Full
score:
|
100
|
Time
limit:
|
500
ms
|
Real
time limit:
|
5
s
|
Memory
limit:
|
64M
|
Новий податок в Ужляндії
Для поповнення бюджету в Ужляндії, відомій своїми
гірськими туристичними маршрутами, ввели новий податок для туристів. Величина
податку пропорційна довжині маршруту, але, оскільки маршрут проходить по горах
і пройдену відстань, яка залежить від висоти спуску і підйому, підрахувати
складно, податок вважається без урахування висоти, тобто величина податку
пропорційна горизонтальному переміщенню, скоєного туристичною групою. Крім
того, в силу старовинного звичаю усі туристичні групи повинні переміщатися по горах
Ужляндії строго із заходу на схід.
Турфірма хоче заощадити на податку, тому вона хоче розробити туристичний маршрут з мінімальною величиною податку. При цьому, оскільки маршрут є гірським, він повинен містити підйом в гору і спуск з гори, тобто на маршруті має бути точка, яка знаходиться строго вище початку і кінця маршруту.
Турфірма склала карту гір Ужляндії, що містить інформацію про висоту гір при пересуванні із заходу на схід. Висоти гір виміряні в точках через рівні відстані. Знайдіть на цій карті гір туристичний маршрут мінімальної довжини, що задовольняє умові наявності підйому і спуску.
Турфірма хоче заощадити на податку, тому вона хоче розробити туристичний маршрут з мінімальною величиною податку. При цьому, оскільки маршрут є гірським, він повинен містити підйом в гору і спуск з гори, тобто на маршруті має бути точка, яка знаходиться строго вище початку і кінця маршруту.
Турфірма склала карту гір Ужляндії, що містить інформацію про висоту гір при пересуванні із заходу на схід. Висоти гір виміряні в точках через рівні відстані. Знайдіть на цій карті гір туристичний маршрут мінімальної довжини, що задовольняє умові наявності підйому і спуску.
Формат вхідних даних:
Перший рядок вхідних даних містить число N -
кількість точок на карті гір Ужляндії. Наступні N рядків містять
інформацію про висоту гір в даних N точках при русі із заходу на
схід. Всі числа натуральні, не перевищують 105.
Формат вихідних даних:
Виведіть два числа - номер точки початку маршруту і
номер точки закінчення маршруту. Точки нумеруються від 1 до N. Якщо
маршруту, що задовольняє умовам, не існує, програма повинна вивести одне число
0. Якщо знайдеться декілька маршрутів, то вивести той що починається лівіше.
Пояснення до прикладів:
Перший приклад: Дано 7 точок з висотами 18, 10, 15,
20, 20, 10, 3. Найкоротший маршрут, який містить підйом і спуск, - це 15, 20,
20, 10. Він починається в точці номер 3 і закінчується в точці номер 6.
Другий приклад: Висота гір монотонно спадає, тому шуканого маршруту не існує.
Другий приклад: Висота гір монотонно спадає, тому шуканого маршруту не існує.
Examples
Input
|
Output
|
7
18
10
15
20
20
10
3
|
3
6
|
3
9
8
5
|
0
|
Немає коментарів:
Дописати коментар