На даній сторінці будуть розгглянуті задачі районної олімпіади з інформатики у Косівському районі.
1. Зарплата (15 балів).
У відділі працюють три співробітники, які отримують заробітню плату у гривнях. Необхідно визначити наскільки зарплата найбільш оплачуваного з них відрізняється (більша) від зарплати найменш оплачуваного.
Вхідні дані: В єдиному рядку файлу записані через пропуск три числа (зарплати).
Вихідні дані:
У вихідний файл необхідно вивести одне число - різницю між мінімальною і максимально. зарплатою
Приклад:
Вхід : 1500 1100 2000 Вихід: 900.
Напевне, пояснень дана задача не потребує.
program min_max;
var
a, b, c, min, max: longint;
begin
readln(a, b, c);
if a < b then begin min := a; max := b end else begin max := a; min := b; end;
if min > c then min := c;
if max < c then max := c;
writeln(max - min);
end.
2. Гіпотеза (20 балів)
Розглянемо наступний алгоритм генерації послідовності чисел. Почнемо з натуралього числа n. Якщо n парне, то поділимо його на два. Якщо n непарне, то помножимо його на 3 і додамо 1. Будемо повторювати цей процес з новим одержаним n, поки n не стане рівним 1. Наприклад для n=22 буде згенерована наступна послідовність чисел: 22,11,34 17 52 26 13 40 20 10 5 16 8 4 2 1. Припускають, що цей алгоритм зводить до 1 будь-яке натуральне число. Для даного n довжиною циклу будемо називати кількість згенерованих членів послідовності включаючи n та 1. Завдання: для даного n визначити довжину циклу.
Приклад
Вхід: 22 Вихід: 16
Також досить проста задача
program min_max;
var
n,k: longint;
begin
readln(n);
k:=1;
repeat
if n mod 2=0 then n:=n div 2 else n:=n*3+1;
k:=k+1;
// write(n,' '); для перевірки послідовності.
until n=1;
writeln;
writeln(k);
end.
3. Демократія в небезпеці (25 балів)
В одній з острівних держав Карибського басейну усі рішення традиційно приймалися простою більшістю голосів на загальному зібранні громадян, яких, на щастя, було не дуже багато. Одна з місцевих партій, намагаючись прийти до влади якомога більш законним шляхом, змогла добитися певної реформи виборчої системи. Головним аргументом було те, що населення острова в останній час значно зросло, і проведення загальних зборів стало проблемою. Суть реформи полягала в наступному; з моменту введення її в дію усі виборці острова ділилися на К груп (не обов'язково рівних по чисельності). Голосування з будь-якого питання тепер належало проводити окремо в кожній групі, причому вважалося, що група висловлюється “за", якщо “за" голосує більше половини людей в цій групі, а в іншому випадку вважалося, що група висловлюється “проти". Після проведення голосування в групах підраховувалася кількість груп, що висловилися “за" і “проти", і питання вирішувалося позитивно тільки в тому випадку, коли груп, що висловилися “за", виявилося більше половини від загальної кількості груп. Ця система спочатку була з радістю сприйнята жителями острова. Однак, з часом стали зрозумілі і певні недоліки нової системи. Виявилося, що прибічники партії, яка запропонувала систему, змогли певним чином вплинути на формування груп виборців. Завдяки цьому; вони отримали можливість проводити деякі рішення, не володіючи при цьому реальною більшістю голосів. Нехай, наприклад, на острові були сформовані три групи виборців, чисельністю 5, 5 і 7осіб відповідно. Тоді партії достатньо мати трьох прибічників у кожній із перших двох груп, і вона зможе провести рішення усього шістьма голосами “за”,* замість дев'яти, що необхідні при загальному голосуванні. Необхідно написати програму, яка за заданим розбиттям виборців па групи визначає мінімальну кількість прибічників партії, достатню, при певному розподілі їх по групах, для прийняття будь-якого рішення.
Вхідні дані
В першому рядку файлу записане непарне число К — кількість груп виборців (І <K<І01). В другому рядку через пропуск записані К непарних чисел, які задають кількість виборців в групах. Населення острова не перевищує 9999осіб.
Вихідні дані
Файл містить єдине число - мінімальну кількість прибічників партії, здатних вирішити долю голосування.
Приклад
Вхід: Вихід:
3 6
5 7 5
Давайте аналізувати дану умову задачі. Зрозуміло, що для того щоб вирішити долю голосування потрібно зібрати голоси "за" в більш ніж половині груп виборців. Так як по умові задачі кількість груп непарне число, то необхідну кількість груп можна знайти поділивши націло загальну кількість груп і додати одиничку. В групі голос "за" також вирішує більше половини виборців, тому необхідну кількість голосів у групі також можна знайти поділивши націло на 2 і додати 1. По умові задачі необхідно знайти мінімальну кількість виборців у всіх групах разом. Тому після зчитування у масив даних по кількості виборців у різних групах, його необхідно відсортувати за зростанням. Тоді ми на початку одержимо групи з найменшою кількістю виборців. Сумуючи необхідну кількість виборців у необхідній кількості груп одержимо розв’язок задачі.
program demokr;
var
a: array[1..1000] of integer;
i, j, k, g, s: integer;
begin
readln(k);
for i := 1 to k do readln(a[i]);
for i := 1 to k - 1 do
for j := i + 1 to k do
if a[j] < a[i] then
begin
//swap(a[i],a[j]); {не всюди swap працює, тоді так як рядком нижче}
g := a[i]; a[i] := a[j]; a[j] := g;
end;
for i := 1 to k div 2 + 1 do s := s + a[i] div 2 + 1;
writeln(s);
end.
4. Черга в кіно (40 балів).
Щойно з'явився новий фільм про “Міцного горішка”, а біля каси за квитками в кіно N людей уже вишикувалися у довжелезній черзі. Кожен з них має тільки одну купюру номіналом 5, 10 або 20 гривень. Квиток на “Міцного горішка” коштує 5 гривень. На момент початку продажу квитків гроші в касі відсутні. Касир обслуговує людей строго в порядку черги, продаючи кожному квиток і видаючи здачу. Очевидно, що здачу покупцю можна видати тільки купюрами, отриманими від людей, що придбали квитки перед ним. Якщо в якийсь момент касир не зможе видати здачу наступному покупцю, то продаж квитків припиняється.
Вхідні дані
У першому рядку вхідного файлу 4.in записане ціле число n (1<=n<=1000) — кількість людей в черзі. В наступних n рядках записано по одному натуральному числу, кожне з яких рівне 5, 10 або 20 — номінали купюр у людей. Числа задані в порядку від початку черги (від каси) до кінця черги.
Вихідні дані
У вихідний файл 4.out вивести одне натуральне число — найбільша кількість людей, яким касир зміг продати квитки.
Приклад
Вхід: Вихід:
8 6
5
5
10
10
5
20
10
5
Для розв’язування даної задачі потрібно змоделювати ситуацію по умові задачі. Після зчитування вхідних даних потрібно в циклі перевіряти наявність купюр в 5 і 10 гривень, так як тільки цими купюрами можна дати здачу, якщо клієнт дає купюру відмінну від 5 гривень. Також в циклі перевіряється чи ми не дійшли до кінця черги. Всередині циклу рахуємо кількість купюр, які в нас є в наявності. Якщо покупець дав купюру в 20 гривень, то, при можливості, спочатку даємо здачі 10 гривень, а потім решту. Так як цикл в будь-якому випадку хоча б один раз виконається, то результат зменшуємо на одиничку.
program ddd;
var
a: array[1..1000] of integer;
i, n, n5, n10, n20: integer;
begin
writeln('Введіть кількість глядачів');
readln(n); {зчитуємо вхідні дані}
for i := 1 to n do readln(a[i]);
n5 := 0; {задаємо початкову кількість купюр}
n10 := 0; {кожного номіналу, зрозуміло, що для того щоб хоча б один білет можна було}
n20 := 0; {продати, то перший покупець повинен мати купюру в 5 гривень}
i := 0;
repeat
if a[i + 1] = 5 then n5 := n5 + 1;
if a[i + 1] = 10 then begin n10 := n10 + 1; n5 := n5 - 1; end;
if a[i + 1] = 20 then
begin
n20 := n20 + 1; {можна було б і не рахувати }
if n10 >= 1 then begin n10 := n10 - 1; n5 := n5 - 1; end else n5 := n5 - 3;
end;
i := i + 1;
until (n5 < 0) or (n10 < 0) or (i > n); {закінчуємо торгівлю}
writeln(i - 1 );
end.
1. Зарплата (15 балів).
У відділі працюють три співробітники, які отримують заробітню плату у гривнях. Необхідно визначити наскільки зарплата найбільш оплачуваного з них відрізняється (більша) від зарплати найменш оплачуваного.
Вхідні дані: В єдиному рядку файлу записані через пропуск три числа (зарплати).
Вихідні дані:
У вихідний файл необхідно вивести одне число - різницю між мінімальною і максимально. зарплатою
Приклад:
Вхід : 1500 1100 2000 Вихід: 900.
Напевне, пояснень дана задача не потребує.
program min_max;
var
a, b, c, min, max: longint;
begin
readln(a, b, c);
if a < b then begin min := a; max := b end else begin max := a; min := b; end;
if min > c then min := c;
if max < c then max := c;
writeln(max - min);
end.
2. Гіпотеза (20 балів)
Розглянемо наступний алгоритм генерації послідовності чисел. Почнемо з натуралього числа n. Якщо n парне, то поділимо його на два. Якщо n непарне, то помножимо його на 3 і додамо 1. Будемо повторювати цей процес з новим одержаним n, поки n не стане рівним 1. Наприклад для n=22 буде згенерована наступна послідовність чисел: 22,11,34 17 52 26 13 40 20 10 5 16 8 4 2 1. Припускають, що цей алгоритм зводить до 1 будь-яке натуральне число. Для даного n довжиною циклу будемо називати кількість згенерованих членів послідовності включаючи n та 1. Завдання: для даного n визначити довжину циклу.
Приклад
Вхід: 22 Вихід: 16
Також досить проста задача
program min_max;
var
n,k: longint;
begin
readln(n);
k:=1;
repeat
if n mod 2=0 then n:=n div 2 else n:=n*3+1;
k:=k+1;
// write(n,' '); для перевірки послідовності.
until n=1;
writeln;
writeln(k);
end.
3. Демократія в небезпеці (25 балів)
В одній з острівних держав Карибського басейну усі рішення традиційно приймалися простою більшістю голосів на загальному зібранні громадян, яких, на щастя, було не дуже багато. Одна з місцевих партій, намагаючись прийти до влади якомога більш законним шляхом, змогла добитися певної реформи виборчої системи. Головним аргументом було те, що населення острова в останній час значно зросло, і проведення загальних зборів стало проблемою. Суть реформи полягала в наступному; з моменту введення її в дію усі виборці острова ділилися на К груп (не обов'язково рівних по чисельності). Голосування з будь-якого питання тепер належало проводити окремо в кожній групі, причому вважалося, що група висловлюється “за", якщо “за" голосує більше половини людей в цій групі, а в іншому випадку вважалося, що група висловлюється “проти". Після проведення голосування в групах підраховувалася кількість груп, що висловилися “за" і “проти", і питання вирішувалося позитивно тільки в тому випадку, коли груп, що висловилися “за", виявилося більше половини від загальної кількості груп. Ця система спочатку була з радістю сприйнята жителями острова. Однак, з часом стали зрозумілі і певні недоліки нової системи. Виявилося, що прибічники партії, яка запропонувала систему, змогли певним чином вплинути на формування груп виборців. Завдяки цьому; вони отримали можливість проводити деякі рішення, не володіючи при цьому реальною більшістю голосів. Нехай, наприклад, на острові були сформовані три групи виборців, чисельністю 5, 5 і 7осіб відповідно. Тоді партії достатньо мати трьох прибічників у кожній із перших двох груп, і вона зможе провести рішення усього шістьма голосами “за”,* замість дев'яти, що необхідні при загальному голосуванні. Необхідно написати програму, яка за заданим розбиттям виборців па групи визначає мінімальну кількість прибічників партії, достатню, при певному розподілі їх по групах, для прийняття будь-якого рішення.
Вхідні дані
В першому рядку файлу записане непарне число К — кількість груп виборців (І <K<І01). В другому рядку через пропуск записані К непарних чисел, які задають кількість виборців в групах. Населення острова не перевищує 9999осіб.
Вихідні дані
Файл містить єдине число - мінімальну кількість прибічників партії, здатних вирішити долю голосування.
Приклад
Вхід: Вихід:
3 6
5 7 5
Давайте аналізувати дану умову задачі. Зрозуміло, що для того щоб вирішити долю голосування потрібно зібрати голоси "за" в більш ніж половині груп виборців. Так як по умові задачі кількість груп непарне число, то необхідну кількість груп можна знайти поділивши націло загальну кількість груп і додати одиничку. В групі голос "за" також вирішує більше половини виборців, тому необхідну кількість голосів у групі також можна знайти поділивши націло на 2 і додати 1. По умові задачі необхідно знайти мінімальну кількість виборців у всіх групах разом. Тому після зчитування у масив даних по кількості виборців у різних групах, його необхідно відсортувати за зростанням. Тоді ми на початку одержимо групи з найменшою кількістю виборців. Сумуючи необхідну кількість виборців у необхідній кількості груп одержимо розв’язок задачі.
program demokr;
var
a: array[1..1000] of integer;
i, j, k, g, s: integer;
begin
readln(k);
for i := 1 to k do readln(a[i]);
for i := 1 to k - 1 do
for j := i + 1 to k do
if a[j] < a[i] then
begin
//swap(a[i],a[j]); {не всюди swap працює, тоді так як рядком нижче}
g := a[i]; a[i] := a[j]; a[j] := g;
end;
for i := 1 to k div 2 + 1 do s := s + a[i] div 2 + 1;
writeln(s);
end.
4. Черга в кіно (40 балів).
Щойно з'явився новий фільм про “Міцного горішка”, а біля каси за квитками в кіно N людей уже вишикувалися у довжелезній черзі. Кожен з них має тільки одну купюру номіналом 5, 10 або 20 гривень. Квиток на “Міцного горішка” коштує 5 гривень. На момент початку продажу квитків гроші в касі відсутні. Касир обслуговує людей строго в порядку черги, продаючи кожному квиток і видаючи здачу. Очевидно, що здачу покупцю можна видати тільки купюрами, отриманими від людей, що придбали квитки перед ним. Якщо в якийсь момент касир не зможе видати здачу наступному покупцю, то продаж квитків припиняється.
Вхідні дані
У першому рядку вхідного файлу 4.in записане ціле число n (1<=n<=1000) — кількість людей в черзі. В наступних n рядках записано по одному натуральному числу, кожне з яких рівне 5, 10 або 20 — номінали купюр у людей. Числа задані в порядку від початку черги (від каси) до кінця черги.
Вихідні дані
У вихідний файл 4.out вивести одне натуральне число — найбільша кількість людей, яким касир зміг продати квитки.
Приклад
Вхід: Вихід:
8 6
5
5
10
10
5
20
10
5
Для розв’язування даної задачі потрібно змоделювати ситуацію по умові задачі. Після зчитування вхідних даних потрібно в циклі перевіряти наявність купюр в 5 і 10 гривень, так як тільки цими купюрами можна дати здачу, якщо клієнт дає купюру відмінну від 5 гривень. Також в циклі перевіряється чи ми не дійшли до кінця черги. Всередині циклу рахуємо кількість купюр, які в нас є в наявності. Якщо покупець дав купюру в 20 гривень, то, при можливості, спочатку даємо здачі 10 гривень, а потім решту. Так як цикл в будь-якому випадку хоча б один раз виконається, то результат зменшуємо на одиничку.
program ddd;
var
a: array[1..1000] of integer;
i, n, n5, n10, n20: integer;
begin
writeln('Введіть кількість глядачів');
readln(n); {зчитуємо вхідні дані}
for i := 1 to n do readln(a[i]);
n5 := 0; {задаємо початкову кількість купюр}
n10 := 0; {кожного номіналу, зрозуміло, що для того щоб хоча б один білет можна було}
n20 := 0; {продати, то перший покупець повинен мати купюру в 5 гривень}
i := 0;
repeat
if a[i + 1] = 5 then n5 := n5 + 1;
if a[i + 1] = 10 then begin n10 := n10 + 1; n5 := n5 - 1; end;
if a[i + 1] = 20 then
begin
n20 := n20 + 1; {можна було б і не рахувати }
if n10 >= 1 then begin n10 := n10 - 1; n5 := n5 - 1; end else n5 := n5 - 3;
end;
i := i + 1;
until (n5 < 0) or (n10 < 0) or (i > n); {закінчуємо торгівлю}
writeln(i - 1 );
end.
Немає коментарів:
Дописати коментар