Умови та розв’язки задач ІІ етапу Всеукраїнської олімпіади з програмування 2016-2017 н.р. м.Чернігів
Шоколадка
Input
Output
25
3
5
100
Ідея
розв’язку:
Input
Output
-1
NW
Ідея
розв’язку:
1
2
3
8
4
7
6
5
Очевидно, що якщо точка з координатами (x,
y) знаходиться у 2,
4, 6 або 8 частині площині, то найкоротша відстань до плота буде перпендикуляр,
опущений відповідно до північної, східної, південної або західної сторони.
Input
Output
10
10 2
Ідея
розв’язку:
Input
Output
9
4
Ідея
розв’язку:
Input
Output
7
3 6
3
0
Ідея
розв’язку:
Шоколадка
Степан вирішив
пригостити однокласників шоколадками. Шоколадка коштувала N грн. З першого
листопада вартість шоколадки збільшилась рівно на Р відсотків. Визначте скільки
шоколадок зможе купити Степан на S грн після подорожчання.
Формат вхідних даних:
У першому рядку
задано число N (1 ≤ N ≤ 107) - вартість шоколадки до подорожчання. У другому
рядку Р (0 ≤ Р ≤ 100) - величина подорожчання шоколадки у відсотках. В третьому
рядку - S (1 ≤ S ≤ 107) - сума грошей, яка є у Степана.
Формат вихідних даних:
Виведіть одне
число - кількість шоколадок, які може купити Степан.
Examples
Input
|
Output
|
25
|
3
|
5
|
|
100
|
Ідея
розв’язку:
1.
Для точності
обчислень переведемо вартість шоколадки n та суму грошей s, що є в Степана в копійки.
2.
Знайдемо вартість
шоколадки t після подорожчання. Оскільки у нас вартість n в копійках, то дробову частину t відкидаємо.
3.
Знайдемо кількість
шоколадок
k, які може купити
Степан після подорожчання.
Лістінг
програми:
var n,s,p,k,t:real;
read(n);
readln(s);
s:=s*100;
n:=n*100;
t:=n+trunc(n*p/100);
k:=s/t;
write(trunc(k));
end.
Напрямок руху
Степан влітку
відпочиває у бабусі в селі. Особливо йому подобається купатись на сільському
озері. Посередині озера плаває пліт, який має форму прямокутника. Сторони плота
спрямовані уздовж паралелей і меридіанів. Введемо систему координат, в якій
вісь ОХ направлена на схід, а вісь ОY - на північ.
Нехай південно-західний кут плоту має координати (x1,
y1), північно-східний кут - координати (x2, y2).
Формат вхідних даних:
Дано шість чисел
в наступному порядку: 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
|
Ідея
розв’язку:
Плот умовно розбиває площину умовно на 8 частин. (див.мал.)
1
|
2
|
3
|
8
|
4
|
|
7
|
6
|
5
|
Очевидно, що якщо точка з координатами (x,
y) знаходиться у 2,
4, 6 або 8 частині площині, то найкоротша відстань до плота буде перпендикуляр,
опущений відповідно до північної, східної, південної або західної сторони.
Якщо точка з координатами (x, y) знаходиться у 1,
3, 5, 7 частинах площини, то найкоротшою відстанню буде відповідний кут плота.
Лістінг
програми:
var x1,x2,x,y1,y2,y:integer;
begin
read(x1,y1,x2,y2,x,y);
if (x<x1) and (y>y1) and (y<y2) then write('W');
if (y>y2) and (x>x1) and (x<x2) then write('N');
if (x>x2) and (y>y1) and (y<y2) then write('E');
if (y<y1) and (x>x1) and (x<x2) then write('S');
if (x<x1) and (y>y2) then write('NW');
if (x>x2) and (y>y2) then write('NE');
if (x<x1) and (y<y1) then write('SW');
if (x>x2) and (y<y1) then write('SE');
end.
Пакування
речей
Степан збирає
речі у відпустку. З собою в літак він може взяти ручну поклажу і багаж. Для
ручної поклажі у нього є рюкзак, а для багажу - здоровенна валіза.
За правилами
перевезення маса ручної поклажі не повинна перевищувати S кг, а багаж може бути будь-якої маси (за
наднормативний багаж Степан готовий доплатити). Зрозуміло, найбільш цінні речі
- ноутбук, фотоапарат, документи і т. д. - Степан хоче покласти в ручну
поклажу.
Степан розклав
усі свої речі в порядку зменшення їх цінності і починає складати найбільш цінні
речі в рюкзак. Він діє в такий спосіб - бере найцінніший предмет, і якщо його
маса не перевищує S, то кладе його
в рюкзак, інакше кладе його до валізи. Потім він бере наступний за цінністю
предмет, якщо його можна покласти в рюкзак, тобто якщо його маса разом з масою
вже покладених в рюкзак речей не перевищує S,
то кладе його в рюкзак, інакше до валізи, і таким же чином процес триває для
всіх предметів в порядку спадання їх цінності.
Визначте вагу
рюкзака і валізи після того, як Степан складе всі речі.
Формат вхідних даних:
Перший рядок
вхідних даних містить число S (1 ≤ S ≤ 2 × 109) - максимальнодозволенa вага рюкзака. У другому рядку вхідних даних
записано число N (1 ≤ N ≤ 105) - кількість предметів.
У наступних N рядках дано маси предметів, самі предмети
перераховані в порядку спадання цінності (спочатку вказана маса найціннішого
предмета, потім маса другого по цінності предмета і т. Д.). Всі числа
натуральні, сума ваг всіх предметів не перевищує 2 × 109.
Формат вихідних даних:
Виведіть два числа
- вагу рюкзака і вагу валізи (вага порожнього рюкзака і валізи не
враховується).
Examples
Input
|
Output
|
10
4
6
3
2
1
|
10 2
|
Ідея
розв’язку:
Нехай k1– вага рюкзака і k2 – вага валізи.
Беремо перший предмет з вагою а і перевіряємо, якщо k1+a не перевищує s, то збільшуємо k1 на а,
інакше k2 збільшуємо на a.
Лістінг
програми:
var s,n,a,k1,k2,i:int64;
begin
readln(s);
readln(n);
i:=1;
k1:=0;
k2:=0;
while i<=n do
begin
readln(a);
if (k1+a<=s) then k1:=k1+a
else k2:=k2+a;
i:=i+1;
end;
write(k1,' ',k2);
end.
Розбиття
на групи
Степан виписує
на листочку усі цілі числа від 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
|
Ідея
розв’язку:
Очевидно, що числа 20=1, 21=2, 22=4, 23=8,
24=16 і т.д.будуть лежати в різних групах. Всі інші числа можна
розподілити між цими групами.
Отже потрібно знайти найбільшу степінь k числа 2, таку що 2k≤ n.
Лістінг
програми:
var n,k,n2:int64;
begin
read(n);
k:=0;
n2:=1;
while n2<=n do
n2:=n2*2;
k:=k+1;
end;
write(k);
end.
Новий
податок в Ужляндії
Для поповнення
бюджету в Ужляндії, відомій своїми гірськими туристичними маршрутами, ввели
новий податок для туристів. Величина податку пропорційна довжині маршруту, але,
оскільки маршрут проходить по горах і пройдену відстань, яка залежить від
висоти спуску і підйому, підрахувати складно, податок вважається без урахування
висоти, тобто величина податку пропорційна горизонтальному переміщенню,
скоєного туристичною групою. Крім того, в силу старовинного звичаю усі
туристичні групи повинні переміщатися по горах Ужляндії строго із заходу на
схід.
Турфірма хоче
заощадити на податку, тому вона хоче розробити туристичний маршрут з
мінімальною величиною податку. При цьому, оскільки маршрут є гірським, він
повинен містити підйом в гору і спуск з гори, тобто на маршруті має бути точка,
яка знаходиться строго вище початку і кінця маршруту.
Турфірма склала
карту гір Ужляндії, що містить інформацію про висоту гір при пересуванні із
заходу на схід. Висоти гір виміряні в точках через рівні відстані. Знайдіть на
цій карті гір туристичний маршрут мінімальної довжини, що задовольняє умові
наявності підйому і спуску.
Формат вхідних даних:
Перший рядок
вхідних даних містить число 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
|
Ідея
розв’язку:
Нехай масив А складається з елементів, що містять інформацію про висоту гір
в даних N точках при русі із заходу на схід.
Потрібно розглянути випадки:
1.
Якщо існує
послідовність з трьох елементів масиву А таких, що
A[i-1]<A[i] і A[i]>A[i+1], то це буде
найкоротший маршрут.
2.
Якщо існують послідовності
з елементів масиву А такі, що A[i-1]<A[i], A[i]=A[i+1], A[i]=A[i+2],… ,A[i]<A[i+k], де k≤n то серед них потрібно знайти найкоротшу.
Лістінг
програми:
var A:array [1..100000] of int64;
i,n,s,k,j,f:longint;
begin
readln(n);
for i:=1 to n do
readln(A[i]);
s:=1000000;
for i:=2 to n-1 do
begin
if (A[i]>A[i-1]) and
(A[i]>A[i+1]) then begin
write(i-1,' ',i+1);
exit;
end;
if (A[i]>A[i-1]) and
(A[i]=A[i+1]) then begin
k:=i-1;
j:=i;
while (A[j]=A[i]) and (j<n) do
begin
j:=j+1;
end;
if
(j=n) and (A[j]=A[i]) then begin
if s<1000000 then write(f,' ',f+s-1) else write(0);
exit;
end;
if
A[j]<A[i] then begin
if s>(j-k+1) then
begin
s:=j-k+1;
f:=k;
end;
end;
end;
end;
if s<1000000 then write(f,' ',f+s-1) else write(0);
end.
Немає коментарів:
Дописати коментар