Олімпіади з інформатики: листопада 2014

неділя, 30 листопада 2014 р.

Задача. Гірлянда

Новорічну ялинку прикрашено гірляндою нескінченної довжини, що складається з послідовно з'єднаних лампочок. Коли гірлянду вмикають, загоряється лише перша лампочка, рахуючи від вимикача, яка горить одну секунду. Далі гірлянда починає мигати за таким правилом. Щосекунди для кожної лампочки перевіряється умова: якщо рівно одна із її сусідніх лампочок горить, то ця лампочка буде горіти на наступній секунді; інакше – не буде горіти. Перша лампочка має лише одну сусідню.

Завдання

Напишіть програму GARLAND, яка за номером секунди знаходить кількість лампочок гірлянди, що будуть горіти протягом цієї секунди.

Вхідні дані

Єдиний рядок вхідного файлу GARLAND.DAT містить одне ціле число N (1≤N≤10⁹) – номер секунди.

Вихідні дані

Єдиний рядок вихідного файлу GARLAND.SOL має містити ціле число – кількість лампочок, що будуть горіти на секунді N.

Приклад вхідних та вихідних даних

GARLAND.DAT	GARLAND.SOL
5	2

Опис тестів до задачі garland
№	N	бітів у N	1-бітів у N	Відповідь	Розв'язок за O(logN)	Розв'язок за O(N^2)
1	1	1	1	1	+	+
2	7	3	3	4	+	+
3	20	5	2	2	+	+
4	105	7	4	8	+	+
5	1023	10	10	512	+	+
6	25860	15	5	16	+	−
7	520511	19	14	8192	+	−
8	16621499	24	19	262144	+	−
9	67149824	27	3	4	+	−
10	536600575	29	27	67108864	+	−

Розв′язання. Мовою Паскаль.

Var fi,fo:text;

i,j,k,l,m,n:longint;

a:array[1..4] of longint;

Begin

readln(n);

a[1]:=1;

a[2]:=2;

a[3]:=2;

a[4]:=4;

i:=1;

l:=0;

while i<n do begin

i:=i*2+1;

inc(l);

end;

if n<>1 then begin

i:=(i-1)div 2;

m:=n-i;

k:=1;

for i:=1 to l do k:=k*2;

while k>4 do begin

l:=(k div 4);

j:=1;

if m>l then inc(j);

if m>(2*l) then inc(j);

if m>(3*l) then inc(j);

i:=a[j];

a[1]:=i;

a[2]:=2*i;

a[3]:=2*i;

a[4]:=2*2*i;

k:=k div 4;

dec(j);

m:=m-(l*j);

end;

m:=a[m];

writeln(m);

end else writeln('1');

End.

Задачі Всеукраїнських олімпіад з інформатики 1998-2007 рр

Збірник різнорівневих задач олімпіад з інформатики

Збірник алгоритмічних задач олімпіад з інформатики

Даний збірник містить тексти олімпіадних задач, які були запропоновані учням протягом 15 років на олімпіадах різних рівнів: шкільних олімпіадах? районних олімпіадах та обласних олімпіадах Львівської та Хмельницької областей.

Задачі на складання алгоритмів для чисел

1.Скласти алгоритм визначення способу розміну монети будь-якої вартості до 99 коп. монетами 1,2,5,10,25,50 коп.

2.Знайти всі чотирицифрові числа виду abcd, де

а)a,b,c,d - різні цифри;

б)ab-cd=a+b+c+d.

3.Дано натуральні числа М,А₁,А₂,А₃,А₄. Знайти всі натуральні X₁, X₂, X₃, X₄, для яких M=X₁*A₁+X₂*A₂+X₃*A₃+X₄*A₄.

4.Знайти суму цифр натурального числа N.

5.Записати алгоритм розкладу натурального числа на прості множники.

6.Скласти програму, яка визначає всі Піфагорові числа A,B,C

(A² +B² =C² ), 1<=A<=20, 1<=B<=20.

7.Знайти всі трицифрові числа, що дорівнюють середньому арифметичному чисел, одержаних з кожного такого числа перестановками (включаючи і дане число) його цифр.

8.Дописати до числа 523*** три такі цифри справа, щоб одержане число ділилося на 7,8,9.

9.Чи існує чотиризначне натуральне число, яке дорівнює кубу суми своїх цифр?

10.Знайти кількість трицифрових натуральних чисел, що діляться на кожну з своїх цифр (нуль виключається).

11.Знайти кількість натуральних чисел <N, куб кожного з яких можна подати у вигляді суми квадратів трьох натуральних чисел.

12.Задані натуральні числа М1,М2,М3. Знайти найбільше натуральне число, яке не можна представити сумою цих чисел. Сума може складатися з одного доданка. Кожне число може входити в нього тільки один раз.

13.Видрукувати всі трицифрові натуральні числа, сума цифр яких дорівнює деякому цілому числу N.

14.Знайти і надрукувати всі досконалі числа (рівні сумі своїх дільників, крім даного числа).

15.Задане деяке дійсне число T. Заокруглити його за прийнятою схемою до цілого.

16.Знайти всі цілі корені рівняння ax³ +bx² +cx + d = 0, де a, b, c, d - задані цілі числа (a<>0, d<>0). Цілими коренями можуть бути тільки додатні і від'ємні дільники коефіцієнта d.

17.Прості числа, різниця між якими дорівнює 2, називаються "близнятами". Скільки пар "близнят" в першій сотні?

18.Чи можна задане число М представити у вигляді суми квадратів двох натуральних чисел?

19.Скласти програму, яка видруковує всі чотиризначні натуральні числа, в десятковому записі яких немає двох однакових цифр.

20.Скласти програму, яка видруковує всі правильні нескоротні дроби з знаменником 9 в порядку зростання.

21.Скласти програму, яка скорочує дроби.

22.Скласти програму, яка видрукує всі представлення натурального числа N сумою натуральних чисел. Перестановка доданків нового способу не дає.

23.Квадрат трицифрового числа закінчується трьома цифрами, що рівні даному числу. Знайти такі числа.

24.Перевести десяткове число в систему числення з основою N (n<10).

25.Знайти всі двоцифрові числа, сума цифр яких не змінюється при множенні на 2,3,4,5,6,7,8,9.

26. Сума цифр трицифрового числа кратна 7. Саме число теж кратне 7. Знайти всі такі числа.

27.Чотирицифрове число і число, записане у зворотному напрямі до нього (цифри з кінця) є точними квадратами. Знайти всі такі числа.

28.Серед трійок натуральних чисел N,M,K знайти такі, що

1/N+1/M+1/K - ціле число.

29.Ціле додатне число можна зобразити сумою його частин, що називається розбиттям. Наприклад, для 4 : (3+1,2+2,2+1+1,1+1+1+1). P(n)-кількість таких розбиттів. Для заданого числа n знайти його розбиття та їх кількість.

30.Число з N цифр називається числом Амстронга, якщо сума цифр, піднесених до степеня N, дорівнює самому числу. Наприклад,

ABC=A^N+B^N +C^N.

Виконати для двох, трьох, чотирьох цифр.

31. Клієнт банку забув чотирицифровий шифр свого сейфа, але пам¢ятав, що цей шифр – просте число, а добуток його цифр дорівнює 243. За яку найменшу кількість спроб він зуміє відкрити сейф? На екран вивести всі необхідні спроби і їх кількість.

32. Спортсмен в перший день пробігає n км. Кожний наступний день він збільшує денну норму на 100% від норми попереднього дня. Визначити, через скільки днів спортсмен буде пробігати більше k км. Записати алгоритм. Повідомити, якого це буде дня.

33. Малюк і Карлсон живуть в кімнаті, площа підлоги якої А*В. Як їм порахувати, скільки потрібно буде квадратних килимків зі стороною m, щоб повністю застелити підлогу кімнати?

34. Вияснити, в якій координатній чверті розміщений трикутник, утворений прямою y=ax+b і осями координат.

35. Поміняти місцями значення цілих змінних a,b,c так, щоб a>=b>=c.

36.Скласти алгоритм розв'язування рівняння ax + b = с.

37.Скласти алгоритм розв'язування рівняння ax² +bx + c = d , де a, b, c, d - задані цілі числа (a<>0, d<>0).

38.Скласти алгоритм розв'язування системи двох лінійних рівнянь з двома невідомими: ax + bу = c , kx +mу = n де a, b, c, k, m, n - задані цілі числа (a<>0, m<>0).

Задачі олімпіад з інформатики різних років

пʼятниця, 28 листопада 2014 р.

Задача Многочлен. Задача Відстань між числами.

Задача1. Многочлен

Заданий многочлен вигляду:

Завдання Напишіть програму POLYNOM, яка за степенем многочлена N обчислить суму його коефіцієнтів за модулем 9973 після розкриття дужок та зведення подібних членів.

Вхідні дані Єдиний рядок вхідного файлу POLYNOM.DAT містить одне ціле число N (1≤N≤100) – степінь многочлена.

Вихідні дані Єдиний рядок вихідного файлу POLYNOM.SOL має містити єдине ціле число, що дорівнює сумі коефіцієнтів многочлена за модулем 9973 після розкриття дужок та зведення подібних (тобто остачу від ділення суми коефіцієнтів на 9973).

Оцінювання Не менш ніж у 15% тестів число N не буде перевищувати 4. Не менш ніж у 50% тестів число N не буде перевищувати 50.

Приклад вхідних та вихідних даних

POLYNOM.DAT	POLYNOM.SOL
2	100

Розв′язання.

const m = 9973;

var n,i,res,t,j : longint;

f1,f2 : text;

begin

assign(f1,'POLYNOM.DAT'); reset(f1);

assign(f2,'POLYNOM.SOL'); rewrite(f2); readln(f1,n);

res := 0;

for i := 1 to (n*n) do

res := (res+i) mod m;

for i := 2 to n do begin

t := 0;

for j := 1 to (n*n) do

t := (t+res*j) mod m;

res := t;

end;

writeln(f2,res); close(f1); close(f2);

end.

Задача2. Відстань між числами

Нехай числа a і b записані у десятковій системі числення. Визначимо відстань між ними як:
(a₁-b₁)²+(a₂-b₂)²+(a₃-b₃)²+…, де a_i позначає i-ту цифру числа a, а b_i позначає i-ту цифру числа b. Нумерація цифр починається із молодшого розряду числа, якому відповідає номер 1. Якщо значення i більше, ніж довжина числа, то вважається, що i-та цифра рівна нулеві.

Завдання Напишіть програму NUMBERS, яка за трьома цілими невід’ємними числами A, B та C знайде такі числа X і Y, для яких виконуються умови:

1. A≤X≤B і A≤Y≤B

2. X є мінімальним серед таких чисел, від яких відстань до C найменша можлива.

3. Y є максимальним серед таких чисел, від яких відстань до C найбільша можлива.

Вхідні дані Перші три рядки вхідного файлу NUMBERS.DAT містять відповідно цілі числа A, B та C (0≤A≤B≤10¹⁸, 0≤C≤10¹⁸).

Вихідні дані Вихідний файл NUMBERS.SOL має містити два рядки, які містять відповідно цілі числа X та Y.

Оцінювання Щонайменше у 50% тестів журі числа A, B та C не будуть перевищувати 100 000.

Приклад вхідних та вихідних даних

NUMBERS.DAT	NUMBERS.SOL
11 25 130	20 19

Відстань від числа 20 до числа 130: (1-0)²+(2-3)²+(0-0)²=1+1+0=2

Відстань від числа 19 до числа 130: (1-0)²+(1-3)²+(9-0)²=1+2²+9²=1+4+81=86

Розв′язання.

var
max,maxa,min,mina:array[0..1000]of longint;
ttmp,a,b,c:string;
j,q1,q2,t,smin,smax,gmax,gmin,nn,i:longint;

procedure run(x,p:longint);
var i,q1,q2,q3:longint;
begin
if x>nn then
begin
if smin<gmin then
begin
gmin:=smin;
min:=mina;
end;
exit;
end;

q1:=ord(a[x])-48;
q2:=ord(b[x])-48;
q3:=ord(c[x])-48;

if p = 1 then
begin
mina[x+t]:=q3;
run(x+1,1);
end
else
begin
if p = 0 then
begin
mina[t+x]:=q1;
smin:=smin+(q3-q1)*(q3-q1);
run(x+1,2);
smin:=smin-(q3-q1)*(q3-q1);

for i:=q1+1 to q2-1 do
begin
mina[x+t]:=i;
smin:=smin+(q3-i)*(q3-i);
run(x+1,1);
smin:=smin-(q3-i)*(q3-i);
end;

mina[t+x]:=q2;
smin:=smin+(q3-q2)*(q3-q2);
run(x+1,3);
smin:=smin-(q3-q2)*(q3-q2);
end
else
if p = 2 then
begin
mina[x+t]:=q1;
smin:=smin+(q3-q1)*(q3-q1);
run(x+1,2);
smin:=smin-(q3-q1)*(q3-q1);
for i:=q1+1 to 9 do
begin
mina[x+t]:=i;
smin:=smin+(q3-i)*(q3-i);
run(x+1,1);
smin:=smin-(q3-i)*(q3-i);
end;
end
else
begin
for i:=0 to q2-1 do
begin
mina[x+t]:=i;
smin:=smin+(q3-i)*(q3-i);
run(x+1,1);
smin:=smin-(q3-i)*(q3-i);
end;

mina[t+x]:=q2;
smin:=smin+(q3-q2)*(q3-q2);
run(x+1,3);
smin:=smin-(q3-q2)*(q3-q2);
end;

end;

end;

procedure gen(x,p:longint);
var i,q1,q2,q3:longint;
begin
if x>nn then
begin
if smax>gmax then
begin
gmax:=smax;
max:=maxa;
end;
exit;
end;

q1:=ord(a[x])-48;
q2:=ord(b[x])-48;
q3:=ord(c[x])-48;

if p = 1 then
begin
if q3<5 then
begin
maxa[x+t]:=9;
smax:=smax+(9-q3)*(9-q3);
gen(x+1,1);
smax:=smax-(9-q3)*(9-q3);
end
else
begin
maxa[x+t]:=0;
smax:=smax+(0-q3)*(0-q3);
gen(x+1,1);
smax:=smax-(0-q3)*(0-q3);
end;
end
else
begin
if p = 0 then
begin
maxa[t+x]:=q2;
smax:=smax+(q3-q2)*(q3-q2);
gen(x+1,3);
smax:=smax-(q3-q2)*(q3-q2);

for i:=q2-1 downto q1+1 do
begin
maxa[x+t]:=i;
smax:=smax+(q3-i)*(q3-i);
gen(x+1,1);
smax:=smax-(q3-i)*(q3-i);
end;

maxa[t+x]:=q1;
smax:=smax+(q3-q1)*(q3-q1);
gen(x+1,2);
smax:=smax-(q3-q1)*(q3-q1);
end
else
if p = 2 then
begin
for i:=9 downto q1+1 do
begin
maxa[x+t]:=i;
smax:=smax+(q3-i)*(q3-i);
gen(x+1,1);
smax:=smax-(q3-i)*(q3-i);
end;

maxa[x+t]:=q1;
smax:=smax+(q3-q1)*(q3-q1);
gen(x+1,2);
smax:=smax-(q3-q1)*(q3-q1);
end
else
begin
maxa[t+x]:=q2;
smax:=smax+(q3-q2)*(q3-q2);
gen(x+1,3);
smax:=smax-(q3-q2)*(q3-q2);

for i:=q2-1 downto 0 do
begin
maxa[x+t]:=i;
smax:=smax+(q3-i)*(q3-i);
gen(x+1,1);
smax:=smax-(q3-i)*(q3-i);
end;
end;

end;

end;

begin
assign(input,'numbers.dat');reset(input);
assign(output,'numbers.sol');rewrite(output);
readln(a);
readln(b);
readln(c);
ttmp:=c;
nn:=length(a);
if length(b)>nn then nn:=length(b);
if length(c)>nn then nn:=length(c);

while length(a)<nn do a:='0'+a;
while length(b)<nn do b:='0'+b;
while length(c)<nn do c:='0'+c;

smin:=0;
smax:=0;
t:=0;
while (length(a)>0) do
begin
if a[1]=b[1] then
begin
inc(t);
q1:=ord(a[1])-48;
q2:=ord(c[1])-48;
mina[t]:=q1;
maxa[t]:=q1;
smin:=smin+(q1-q2)*(q1-q2);
smax:=smax+(q1-q2)*(q1-q2);
delete(a,1,1);
delete(b,1,1);
delete(c,1,1);
end
else break;
end;

nn:=length(a);
gmin:=10000000;
gmax:=0;

run(1,0);

j:=1;
while (j<nn+t)and(min[j]=0) do inc(j);

for i:=j to nn+t do write(min[i]);
writeln;
gen(1,0);
j:=1;
while (j<nn+t)and(max[j]=0) do inc(j);

if gmax=0 then
begin
writeln(ttmp);
end
else
begin
for i:=j to nn+t do write(max[i]);
writeln;
end;
close(input);close(output);
end.

неділя, 30 листопада 2014 р.

Задача. Гірлянда

Задачі Всеукраїнських олімпіад з інформатики 1998-2007 рр

Збірник різнорівневих задач олімпіад з інформатики

пʼятниця, 28 листопада 2014 р.

Задача Многочлен. Задача Відстань між числами.

неділя, 30 листопада 2014 р.

пʼятниця, 28 листопада 2014 р.