Підготовка до олімпіади з програмування
Задача Combination.Дана
послідовність, що складається з N
натуральних чисел. Написати програму, що визначає, чи є ця послідовність
перестановкою перших N
натуральних чисел.
g
Технічні умови N - не більше 10000, а кожне з чисел менше 2000000. Ви вводите з клавіатури число N, а потім - N натуральних чисел через пропуск. Ви виводите на екран 0, якщо послідовність виявиться перестановкою, а якщо ні - мінімальне число, що не входить в цю послідовність.
Технічні умови N - не більше 10000, а кожне з чисел менше 2000000. Ви вводите з клавіатури число N, а потім - N натуральних чисел через пропуск. Ви виводите на екран 0, якщо послідовність виявиться перестановкою, а якщо ні - мінімальне число, що не входить в цю послідовність.
Приклади:
|
Введення
|
Виведення
|
3 2 1 3
|
0
|
|
Введення
|
Виведення
|
|
3 1 4 2
|
3
|
Розв′язання.
Спосіб
1.
Відсортуємо послідовність за неспаданням. Потім за один прохід знаходимо
найменше число, якого немає в цій послідовності. Якщо це число дорівнює N+1,
послідовність є перестановкою, в іншому випадку знайдене число є відповіддю на
задачу. Щоб знайти число, якого немає в послідовності, перевіримо, що перший її
елемент дорівнюе1. Якщо це не так, 1 в послідовності немає. Якщо ж перший елемент дорівнює 1, перевіримо всі
папи сусідніх елементів послідовності, ли дорівнює 1 або 0 різниця міх
наступним і пепереднім елементами. Якщо в якійсь парі ця різниця складає 2 або
більше, відповідь – попередній елемент цієї пари, збільшений на 1. Якщо такої
пари не знайшлося, відповідь – останній елемент послідовності, збільшений на 1.
Складниість алгоритму –N*log(N).
Спосіб
2. Ця проста задача має вельми елегантний
однопрохідний розв’язок. Створимо хеш-масив
А з N елементів та
заповнимо його нулями. . Для кожного введеного числа
послідовності будемо перевіряти, чи
входить воно у множину N перших натуральних чисел,
і якщо так – то надаємо значення 1 відповідному елементу масива (тобто, А[M]:=1,
якщо було введено M). У підсумку, якщо весь масив виявиться «одиничним», то
виводимо 0, інакше номер першого «одиничного» елемента.
program combination;
const maxn=100000;
var
n,i,j:longint;
a:array[1..maxn] of integer;
begin
read(n);
for
i:=1 to n do begin a[i]:=0; end;
for
i:=1 to n do begin read(j);
if j<=n then a[j]:=1; end;
for
i:=1 to n do if a[i]=0 then begin
writeln(i); exit; end; writeln(0);
end.
Задача. Записати алгоритм, який знаходить суму чисел
елементів масиву, що знаходяться на діагоналях. Масиву задати випадкові числа.
program matriza;
const m=4;
n=4;
var sum,f,s:real;
b:array[1..m*n] of
real;
a:array[1..m,1..n]
of real;
i,j,p, k:integer;
begin
writeln('massiv :
');
s:=0;
for i:=1 to m do
for j:=1 to n do
begin
a[i,j]:=int(random*20-10);
b[(i-1)*n+j]:=a[i,j];
end;
writeln(' ');
writeln(' ');
for i:=1 to m do
begin
for j:=1 to n do
begin
write(' a[ ',i,';',j,' ]:= ',a[i,j]{' b[',i-1*n+j,']= ',b[(i-1)*n+j]});
end;
writeln(' ');
writeln(' ');
end;
s:=0;
for i:=1 to n do
begin
s:=s+a[i,i];
end;
f:=0;
for i:=1 to n do
begin
f:=f+a[i,n+1-i];
end;
if
n mod 2 =1 then
sum:=s+f- a[n div
2 +1, n div 2 +1]
else
sum:=s+f;
writeln(' ');
writeln('suma
головної diagonaley= ',s); writeln('
');
writeln('suma
бічної diagonaley= ',f);
writeln(' ');
writeln('suma обох
diagonaley= ',sum);
end.
Олімпіада з інформатики. Підготовка до міської
олімпіади.
Задача Boredom. Василь та Петро бавилися на уроці. На прямокутному
аркуші паперу в клітинку Василь по лінях сітки малює відрізок, паралельний
одному з країв аркуша, та рамку прямокутної форми. Він шепоче на вухо Петрові
координати кінців відрізка та координати двух протилежних кутів рамки, а Петро
намагається швидко визначити довжину частини відрізка, що опинилася всередині
рамки. У нього це погано виходило, і він написав програмку, яка це робила
завжди правильно. Напишіть її й ви.Технічні умови Координати - цілі числа, що не перевищують по модулю 35000. Ви вводите з клавіатури через пропуск 8 чисел - координати початку та кінця відрізка та координати протилежних кутів рамки. Ви виводите на екран одне число - довжину частини відрізка, що виявилась всередині рамки.
Приклади:
|
Введення
|
Виведення
|
4 1 9 1 2 3 5 –2
|
1
|
|
Введення
|
Виведення
|
|
2 1 2 7 -2 2 2 -2
|
0
|
Розв′язання. Задача досить
проста. Для кожної цілочисельної точки відрізка визначимо, є вона
зовнішньою відносно даного нам прямокутника, внутрішньою чи граничною (на
малюнку зовнішні точки позначено цифрою 1, граничні – цифрою 2, а внутрішні –
цифрою 3). Одиничний відрізок, що з'єднує дві цілочисельні точки буде належати
прямокутнику тоді й тільки тоді, коли хоча б один його кінець буде внутрішньою
точкою (окремо розглядається випадок, коли довжина (або ширина) прямокутної
рамки дорівнює 1).
Можливий і інший
варіант розв’язку. «Відріжемо» від відрізка ті частини, про які заздалегідь
відомо, що вони не лежать всередині рамки – все що знаходиться ліворуч від
лівої сторони і праворуч від правої (або вище від верхньої та нижче від нижньої
сторони) прямокутника (таких частин може бути дві, одна, або жодної). Перевіряємо, чи не перебуває
відрізок на якійсь зі сторін рамки, і якщо ні, то робимо висновок, що відповідь
– довжина отриманого «обрізаного» відрізка.
program boredom;
var x1,y1,x2,y2,x3,y3,x4,y4:longint;
procedure obm(var x,y:longint);
var
tmp:longint;
begin tmp:=x; x:=y; y:=tmp;
end;
BEGIN
read(x1,y1,x2,y2,x3,y3,x4,y4);
if y1=y2 then begin
obm(x1,y1); obm(x2,y2);
obm(x3,y3);obm(x4,y4); end;
if
y1>y2 then obm(y1,y2); if x3>x4
then obm(x3,x4); if y3>y4 then obm(y3,y4);
if
(x1<=x3)or(x1>=x4) then begin
writeln(0); exit; end;
if
(y1>=y4)or(y2<=y3) then begin
writeln(0); exit; end;
if
(y3<=y1)and(y4>=y2) then begin
writeln(y2-y1); exit; end;
if
(y2>=y4)and(y1<=y3) then begin
writeln(y4-y3); exit; end;
if
y1>=y3 then writeln(y4-y1) else writeln(y2-y3);
END.
Олімпіада з інформатики. Підготовка до міської
олімпіади.
Задача Bishop.На шаховiй
дошцi розмiрами М*N клiтинок
стоїть слон (фiгура, що ходить по дiагоналi). З'ясувати, чи може слон дiйти до
поля (x,y) Якщо може, то за яку найменшу кiлькiсть ходiв; якщо
кiлькiсть ходiв бiльша за 1, то вказати, через якi промiжнi клiтинки повинен
пройти слон (якщо таких маршрутiв кiлька, вказати будь-який один з них). Поля
шахової дошки кодуються парою натуральних чисел 1..М, 1..N, де перше
число – номер горизонталi, а друге - номер вертикалi (1≤М,N≤1000).
.
Технічні умови Ви вводите з клавiатури через пропуск числа М, N, а далi координати початкового та кiнцевого полiв бажаного маршруту слона. Ви виводите на екран число К (мiнiмальна кiлькiсть ходiв), а далi в К-1 рядках по 2 числа через пропуск - координати вiдвiданих полiв. Якщо розв'язкiв немає, вивести 0.
Технічні умови Ви вводите з клавiатури через пропуск числа М, N, а далi координати початкового та кiнцевого полiв бажаного маршруту слона. Ви виводите на екран число К (мiнiмальна кiлькiсть ходiв), а далi в К-1 рядках по 2 числа через пропуск - координати вiдвiданих полiв. Якщо розв'язкiв немає, вивести 0.
Приклад:
|
Введення
|
Виведення
|
10 10 1 1 1 7
|
2
4 4 |
Олімпіада з інформатики. Підготовка до міської
олімпіади.
Задача Robots. Колонiя
роботiв iснує за такими законами: КЕ
1. За один рiк M роботiв складає А нових роботiв, а N роботiв складає B нових роботiв .
2. Роботи завжди намагаються зiбрати якнайбiльше нових роботiв.
На момент заснування колонiї було К роботiв. Скiльки буде роботiв через Т рокiв? (Всi вхiднi величини не бiльшi 100, результат не перевищує 2000000000). И А
Течнічні умови Ви вводите з клавiатури числа М,А,N,B,K,T через пропуск. Ви виводите на екран єдине шукане число.
1. За один рiк M роботiв складає А нових роботiв, а N роботiв складає B нових роботiв .
2. Роботи завжди намагаються зiбрати якнайбiльше нових роботiв.
На момент заснування колонiї було К роботiв. Скiльки буде роботiв через Т рокiв? (Всi вхiднi величини не бiльшi 100, результат не перевищує 2000000000). И А
Течнічні умови Ви вводите з клавiатури числа М,А,N,B,K,T через пропуск. Ви виводите на екран єдине шукане число.
Приклад:
|
Введення
|
Виведення
|
3 5 5 9 15 1
|
42
|
Олімпіада з інформатики. Підготовка до міської
олімпіади.
Задача Table. Нехай N - деяке натуральне
число. Розглянемо таблицю А[1:N], яка містить цілі числа з діапазону
[-32768..32767], серед яких немає двох однакових. Знайти місце в таблиці, де
знаходиться K-е число за спаданням (тобто таке, що рівно К-1 чисел у таблиці
більші за нього).
Технічні умови. Ви вводите з клавіатури число N (1≤N≤20000), далі - N елементів
таблиці, через пропуск, а тоді - число К (1≤K≤N). Ви виводите на екран одне
число - місце знаходження К-го за спаданням елемента таблиці.
Приклад:
|
Введення
|
Виведення
|
7
|
5
|
|
9 5 1 2 8 6 3
|
||
2
|
Ця задача
може бути розв’язана різними способами.
Розглянемо деякі з них.
Спосіб
1. Впорядкуємо даний масив за спаданням,
відповідь – місце знаходження К-го
числа у впорядкованому масиві. Щоб отримати номер місця знаходження числа,
можна заповнити допоміжний масив послідовними натуральними числами, а при
сортуванні переставляти значення одночасно і в заданому, і в допоміжному
масиві. Складність n·log(n), витрати пам’яті залежать від методу сортування.
Складність не залежить від того, чи шукається перше число (тобто найбільше) чи
ж 9999-е серед 19999 чисел. Звичайно, можна сортувати і за зростанням, тоді
відповідь – місце (N+1-K)-го елемента
відсортованого масиву.
Спосіб
2. Введемо допоміжну таблицю В[1:K], в якій запишемо перші К елементів в порядку їх спадання.
Починаючи з (К+1)-го елемента і до
кінця будемо «вставляти» його в таблицю В, зберігаючи її впорядкованість, зайві
значення з неї вилучатимемо. Останній елемент таблиці – відповідь задачі.
Проілюструємо на прикладі роботу цього алгоритму.
Нехай у таблиці з
10 елементів записані такі числа: 7,2,4,9,5,1,3,10,6,8. Необхідно знайти
четверте за спаданням число.
Спочатку в таблицю
В запишемо [9,7,4,2] – це перші 4
числа, впорядковані за спаданням.
Починаємо подальшу
обробку. П’ятий, наступний елемент таблиці дорівнює 5. Так як 5>4 и 5<7,
то число 5 вставимо між 7 и 4, а 2 вилучаємо. В таблиці буде записано
[9,7,5,4]. Далі у вхідних даних записано 1. Так як 4>1, таблиця В не змінюється. Аналогічно обробка
числа 3 також не змінить таблицю В.
Після обробки числа 10 в таблиці буде записано [10,9,7,5], після обробки 6 –
[10,9,7,6], після обробки 8 – [10,9,8,7]. Таким чином, відповідь – 7, число, що
знаходиться на 4-й позиції. Для знаходження номера місця знайденого числа
в масиві (див. спосіб 1).
Складність
алгоритму дорівнює N·K (N·logK, якщо для пошуку місця вставки
числа в масив В використати бінарний пошук і якщо мова програмування дозволяє
переписати «хвіст» масиву за одну операцію). Витрати пам’яті – К комірок. Ефективність можна підвищити,
якщо для великих К шукати не К-е за спаданням, а (N+1-K)-е за зростанням. Оскільки К<N, теоретично спосіб 2 більш ефективний, ніж спосіб 1,
практично – залежить від компілятора.
Спосіб
3. Введемо хеш-масив Н[-32767..32768] и заповнимо його нулями. Для всіх елементів
вхідного масиву в комірку масиву Н з індексом, який дорівнює значенню чергового
елемента вхідного масиву, записуємо номер цього елемента. Після того, як всі
вхідні дані переглянуто, знаходимо (N+1-К)-е за рахунком ненульове значення в
хеш-масиві, починаючи з індексу -32767. Це і є відповідь. Так, для прикладу з
способу 2, в 7-й комірці запишеться 1, в 2-й – 2, в 4-й – 3 і т.д. (див.
таблицю 18.1).
Таблиця
18.1.
Індекс i
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
Значення Н[i]
|
0
|
6
|
2
|
7
|
3
|
5
|
9
|
1
|
10
|
4
|
8
|
0
|
Складність
алгоритму 65536 (на занулення хеш-масиву) + (обробка вхідних даних) + 65536
(пошук в хеш-масиві), тобто теоретично n.
Витрати пам’яті – 65536 комірок. Теоретично цей спосіб ефективніший за два
попередні, практично – залежить від реалізації.
Ще один спосіб
запропоновано автором мови Паскаль Н.Віртом. (Див §2.2.7 з його книги «Алгоритмы+структуры данных=программы» (М. «Мир», 1985).
Program Table;
Type dat=array[1..20001] of integer;
pdat=^dat;
Var n,m,i,j,w,l,r,x:integer;
a,b:pdat;
BEGIN
readln(m);
new(a);
new(b);
for i:=1 to m do
begin
read(a^[i]);
b^[i]:=i;
end;
readln(n);
l:=1;r:=m;
while ldo
begin
x:=a^[n];
i:=l;
j:=r;
repeat
while a^[i]>x do
i:=i+1;
while x>a^[j] do
j:=j-1;
if i<=j
then begin
w:=a^[i]; a^[i]:=a^[j]; a^[j]:=w;
w:=b^[i]; b^[i]:=b^[j]; b^[j]:=w;
i:=i+1;
j:=j-1;
end;
until i>j;
if jthen l:=i;
if nthen r:=j;
end;
writeln(b^[n]);
END.
Олімпіада з інформатики. Підготовка до міської
олімпіади.
Задача Graph2 (запропонована дизайнером фірми
"GraphSoft")
Одержав я вчора завдання намалювати
картинку розміром H на W пікселів, обгортку для цукерок "Сосиска в
шоколаді". Творчість - процес тонкий, натхнення потрібне. А тут - як ножем
відрізало, нічого не виходить… Від безвиході я намалював на білому екрані свого
комп’ютера червону замкнуту лінію, товщиною в один піксель. Скільки пікселів
виявилося в області, обмеженою червоною лінією? Для тих, хто не знайомий з
комп'ютерною графікою - піксель має форму квадратика.
Технічні умови. Програма повинна прочитати з клавіатури: з першого рядка - два числа H і
W, а з наступних H рядків прочитати по W чисел(1<H,W≤100). Червоний піксель
позначається одиницею, білий - нулем. Програма повинна вивести на екран
результат - число пікселів в області, що обмежена лінією. Кожен червоний
піксель має спільні сторони рівно з двома червоними пікселями.
Приклад:
|
Введення
|
Виведення
|
5 7
0 0 0 1 1 1 0
0 1 1 1 0 1 0
0 1 0 0 0 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0
|
4
|
Будь-який
піксель на картинці відноситься або до
червоної лінії ( назвемо їх «червоними») ,
або до області, що обмежена червоною лінією ( назвемо їх «внутрішніми» ,
або до області, що лежить поза нею (назвемо їх «зовнішніми»). Кількість «червоних» пікселів легко порахувати. Неважко
порахувати й кількість «зовнішніх»
пікселів. Достатньо помітити, що з кожного такого пікселя можна потрапити до
краю картинки, переходячи лише по білим пікселям, що мають спільну сторону або
кут. Шукана кількість «внутрішніх»
рівна різниці загальної кількості пікселів H*W та суми «червоних» та «зовнішніх»
Щоб
обійти всі «зовнішні» пікселі, зручно
скористатися пошуком в ширину. Спочатку поміщуємо в чергу всі крайні білі
пікселі і зафарбовуємо їх червоним кольором. Перебираючи всі пікселі в черзі
будемо додавати в чергу всіх ще
непофарбованих сусідів за кутом або стороною.
Одна
з можливих релізацій мовою Паскаль
Задача Graph2
program graph2;
const di: array [0 .. 7] of shortint = (-1,0,1,0,-1,1,-1,1);
dj: array [0 .. 7] of shortint = (0,1,0,-1,-1,1,1,-1);
var a: array [0 .. 101,0 .. 101] of byte;
h,w,i,j: byte;
r,p,l: longint;
qi,qj : array [1 .. 10000] of byte;
begin
read(h,w);
r := integer(h) * w;
p := 1;
l := 0;
fillchar(a,sizeof(a),2);
for i := 1 to h do
for j := 1 to w do
begin
read(a[i,j]);
if a[i,j] = 1
then dec(r)
else if (i = 1) or (i = h) or (j = 1) or (j = w)
then begin
inc(l);
qi[l] := i;
qj[l] := j;
dec(r);
a[i,j] := 2;
end;
end;
while p <= l do
begin
for i := 0 to 7 do
if a[qi[p] + di[i],qj[p] + dj[i]] = 0
then begin
a[qi[p] + di[i],qj[p] + dj[i]] := 2;
dec(r);
inc(l);
qi[l] := qi[p] + di[i];
qj[l] := qj[p] + dj[i];
end;
inc(p);
end;
writeln(r);
end.
Немає коментарів:
Дописати коментар