Олимпиадные задания по программированию

[Dreamer]

Предлагаю выкладывать тут олимпиадные задачи и решения к ним! А также, дисскутировать по поводу решений, предлагать альтернативные варианты, искать более рациональные подходы...

[Dreamer]

ОЛІМПІАДА КИЇВСЬКОГО НАЦІОНАЛЬНОГО
УНІВЕРСИТЕТУ ІМЕНІ ТАРАСА ШЕВЧЕНКА:
факультет кібернетики
Група "В"

2. Намисто
У пустелі Макмахара група дослідників знайшла залишки невідомої цивілізації. Було знайдено велику кількість намист, які використовувались представниками цієї цивілізації для запису чисел. Кожне з намист складається зі з’єднаної в кільце нитки, на яку нанизано деяку кількість бусинок.
Бусинки бувають двох кольорів, чорного та білого, і, зрозуміло, що намиста використовувались для подання двійкових чисел.
Нажаль, ніхто не знає, чи позначає чорний колір 1, а білий - 0 або навпаки. Також не зрозуміло, де число починається і навіть у якому напрямку його читати!
Просте намисто, що зображено нижче, може представляти декілька чисел.

[Dreamer]

Ми можемо сказати, що найменше число, яке може подаватись - 1, найбільше 14.
В цьому простому випадку мінімальне та максимальне числа співпадають незалежно від того, читаємо ми число за годинниковою стрілкою чи проти.Однак, існують більш складні випадки, коли різні напрямки читання дають різні найбільше та найменше значення. Ваша задача - написати програму, що за намистом визначить найбільше та найменше числа, що воно може представляти.

2007 p.

[Dreamer]

Вариант решения на языке Паскаль...

Program Namisto;
uses Crt;
type Mas=array[byte] of boolean;
var R,Temp:string;
max,min:word;
p,i:byte;
Function Trans(M:string):word;
var Tr,Temp:Mas;
i,k:byte;
T:word;
begin
k:=length(M)-1;
for i:=1 to k+1 do
if M[i]='Ч' then Tr[i-1]:=True else Tr[i-1]:=False;
Temp:=Tr;
for i:=k downto 0 do
Tr[abs(k-i)]:=Temp[i];
T:=0;
for i:=0 to k do
T:=T+ord(Tr[i])*round(Exp(i*ln(2)));
Trans:=T
end;
Procedure Check;
begin
if min>Trans(Temp) then min:=Trans(Temp) else
if max<Trans(Temp) then max:=Trans(Temp)
end;
Procedure Invertion;
begin
for p:=1 to length(Temp) do
case Temp[p] of
'Ч':Temp[p]:='Б';
'Б':Temp[p]:='Ч'
end
end;
begin
ClrScr;
readln(R);
Temp:=R;
min:=Trans(Temp);
max:=min;
R:=Temp;
for i:=1 to length(R) do
begin
Temp:=Copy(R,i,length(R))+Copy(R,1,i-1);
Check;
Invertion;
Check;
Temp:='';
for p:=i downto 1 do
Temp:=Temp+R[p];
for p:=length(R) downto i+1 do
Temp:=Temp+R[p];
Check;
Invertion;
Check
end;
writeln('min=',min);
writeln('max=',max);
ReadKey
end.

[pingwinator]

пипец, чувствую себя дауном

[Dreamer]

Сообщение от PingWin

пипец, чувствую себя дауном

Ты чего? Это ты так шутишь?

[pingwinator]

Сообщение от Dreamer

Ты чего? Это ты так шутишь?

помница раньше решал эти задачи легко, щас неосилил.
дергадирую (

[Dreamer]

Сообщение от PingWin

помница раньше решал эти задачи легко, щас неосилил.

Эт ещё ничего... ты на эту погляди...


3. Графіка
В деяких графічних програмах екран розділяється на 4 області, занумеровані 1, 2,3, 4, кожна з частин ділиться рекурсивно за тим же принципом, на довільну глибину. За цією схемою, кожна комірка на екрані може бути унікально ідентифікована послідовністю цифр від 1 до 4, як на малюнку:

[Dreamer]

Вам задано послідовність цифр з діапазону 1-4, що ідентифікують початкову коміркута послідовність переміщень в формі В(вверх), Н(вниз), Л(ліворуч), П(праворуч). Вашою задачею є визначити комірку, в яку приведе задана послідовність рухів, також як послідовність цифр 1-4, або сповістити, що послідовність рухів виводить за межі екрана.

P.S. Решения у меня нету! Покамись

[Muxa]

Сообщение от Dreamer

Вам задано послідовність цифр з діапазону 1-4, що ідентифікують початкову коміркута послідовність переміщень в формі В(вверх), Н(вниз), Л(ліворуч), П(праворуч). Вашою задачею є визначити комірку, в яку приведе задана послідовність рухів, також як послідовність цифр 1-4, або сповістити, що послідовність рухів виводить за межі екрана.

P.S. Решения у меня нету! Покамись

ты с городской олимпиады решал?(то шо я тебе кидал)
А то сам не осилил....

[Dreamer]

Сообщение от Muxa

ты с городской олимпиады решал?(то шо я тебе кидал)
А то сам не осилил....

Кстати, да... буду сейчас решать)))

[Dreamer]

ПІВДЕННОУКРАЇНСЬКИЙ РЕГІОНАЛЬНИЙ ІНСТИТУТ ПІСЛЯДИПЛОМНОЇ ОСВІТИ ПЕДАГОГІЧНИХ КАДРІВ

ЗАВДАННЯ II – ТУРУ

ВСЕУКРАЇНСЬКОЇ ОЛІМПІАДИ З ІНФОРМАТИКИ

2006 – 2007 навчальний рік

9-11 клас

Розробити програму до кожної задачі, яка за вхідними даними буде отримувати вихідні данні

Задача 3 “Парламент”.(20 балів)
Усім відома одна із суперечок у політичному житті України – якою повинна бути чисельність верховної ради та як її вибирати. Для вирішення цієї проблеми можна було б скористатися досвідом країни Hits. Кожному з N її громадян був присвоєний особистий номер від 1 до N, і з номерів був складений список у випадковому порядку. Спеціальна комп’ютерна програма почала рахувати громадян по списку: 1, 2, 3 і так до N+1. якщо номер при рахуванні співпадає з номером громадянина то він виключається із списку громадян і переноситься у список парламентарів, а рахунок починається заново з громадянина із наступним номером. Після останнього номера рахунок продовжується з початку списку громадян. Програма завершує вибори коли Ії рахунок має значення N+1.
Дізнайтесь про чисельний склад парламенту країни Hits та особисті номери парламентарів.

Технічні вимоги:
Вхідний файл: HITS.IN
Вихідний файл: HITS.OUT

Формат вхідних даних:
Перший рядок – число N – жителі (9<=N<=100000)
Другий рядок – ряд чисел, вказаних через пробіл

Формат вихідних даних:
Один рядок – ряд чисел, вказаних через пробіл
Приклади файлів вхідних та вихідних даних:
1) HITS.IN
9
1 3 5 7 9 2 4 6 8
HITS.OUT
2 1 8
2) HITS.IN
9
9 7 3 1 2 4 5 6 8
HITS.OUT
3 3 1 7

[Dreamer]

Вариант решения на языке Паскаль...

Program Hits;
const z=100000;
type zero=1..z;
var f:text;
N,num,i:zero;
m:0..z;
p:1..z+1;
A:array[1..z div 10] of zero;
Function Check(number:zero):boolean;
var i:zero;
C:boolean;
begin
C:=True;
for i:=1 to m do
if A[i]=number then C:=False;
Check:=C
end;
begin
Assign(f,'Hits.in');
Reset(f);
readln(f,N);
m:=0;
p:=1;
while p<N+1 do
begin
if eof(f) then
begin
Close(f);
Reset(f);
readln(f,N);
end;
read(f,num);
if Check(num) then
begin
if p=num then
begin
m:=m+1;
A[m]:=num;
p:=1
end else
p:=p+1
end
end;
Close(f);
Assign(f,'Hits.out');
Rewrite(f);
write(f,m,chr(32));
for i:=1 to m do
write(f,A[i],chr(32));
Close(f)
end.

[Dreamer]

Задача 1 “Труба”.(20 балів)
Під час трудового десанту учні фарбували трубу. Кожному учню було доручено фарбувати певний відрізок труби. Однак студент практикант, який керував роботою учнів, щось переплутав, і тому деякі ділянки труби були пофарбовані кілька разів. Вважаючи, що кожен учень був дуже старанним і пофарбував трубу шаром фарби товщиною в 1 мм, знайти максимальну товщину отриманого пофарбованого покриття на трубі.

Технічні вимоги:
Вхідний файл: TRUBA.IN
Вихідний файл: TRUBA.OUT

Формат вхідних даних:
У першому рядку ціле число N учнів, не більше 5000, далі на 2N рядках – координати початку та кінця ділянок, відведених кожному учню. Координати – додатні дійсні числа.

Формат вихідних даних:
Один рядок – ціле число – максимальна товщина шару фарби у міліметрах.

Приклад файлів вхідних та вихідних даних:
TRUBA.IN
2
50.000
103.138
36.105
106.363
TRUBA.OUT
2

[Dreamer]

Вариант решения на языке Паскаль...

Program Truba;
type zero=1..500;
var f:text;
A:array[zero,1..2] of real;
N:zero;
i,j,k,max:word;
begin
Assign(f,'Truba.in');
Reset(f);
readln(f,N);
for i:=1 to N do
begin
readln(f,A[i,1]);
readln(f,A[i,2]);
end;
Close(f);
max:=0;
for i:=1 to N do
begin
k:=0;
for j:=1 to N do
if (A[j,1]>=A[i,1]) and (A[j,1]<=A[i,2]) or (A[j,2]>=A[i,1]) and (A[j,2]<=A[i,2]) then k:=k+1;
if k>max then max:=k
end;
Assign(f,'Truba.out');
Rewrite(f);
writeln(f,max);
Close(f)
end.

[Dreamer]

1. Решта
У невеликій крамниці виникли проблеми від того, що недосвідчений продавець не може підрахувати скільки решти давати покупцям. Треба розробити програму, що допоможе йому у цьому!
Наявними банкнотами є 20 грн., 10 грн., 5 грн., 2 грн. та 1 грн., монетами: 50 коп., 20 коп., 10 коп., 5 коп.
Оскільки найменшою монетою є 5 коп., вартість покупки має заокруглюватись за таким принципом:
1 або 2 копійки – заокруглюється до 0.
3 або 4 копійки – заокруглюється до 5.
6 або 7 копійки – заокруглюється до 5.
8 або 9 копійки – заокруглюється до 10.
Програма має підрахувати решту та вказати які банкноти та монети використовувати, та у якій кількості. У кожному випадку сумарна кількість монет та банкнот має бути мінімальною з можливих.

[Dreamer]

Вариант решения на языке Паскаль...

Program Reshta;
uses Crt;
var R,s1,s2:real;
T,n,k:byte;
begin
ClrScr;
readln(s1);
readln(s2);
R:=abs(s1-s2);
writeln(R:1:2);
while R>=1 do
begin
if R>=20 then n:=20 else
if R>=10 then n:=10 else
if R>=5 then n:=5 else
if R>=2 then n:=2 else
n:=1;
k:=Trunc(R) div n;
writeln(n:2,' грн - ',k);
R:=R-k*n;
end;
R:=R*100;
T:=Round(R);
case T mod 10 of
1..2:T:=T-T mod 10;
3..7:T:=(T div 10)*10+5;
8..9:T:=(T div 10)*10+10;
end;
while T>0 do
begin
if T>=50 then n:=50 else
if T>=20 then n:=20 else
if T>=10 then n:=10 else
n:=5;
k:=T div n;
writeln(n:2,' коп - ',k);
T:=T-k*n;
end;
ReadKey
end.

[Grig]

Предлагаю данные примеры кода брать в специальный ТЭГ - [ code ]
после чего следует текст и закрывается тэг [ /code ] (в тэге без пробелов) .. очень экономиться расстояние пролистывания ...

PS еще большой плюс этого тэга - нет потери в некоторых случаях форматирования кода и замены скобок и прочих символов на смайлы (в цитировании заменяет)

[Dreamer]

Задача 2 “Їжак”.(20 балів)
План прямокутного саду розміром m*n складається з квадратних зон. У кожній зоні росте по дереву. З кожного дерева будь якої зони можуть упасти кілька яблук.
У лівому верхнбому квадратику знаходиться їжак, який повинен дійти до правого нижнього квадратика. В саду існують обмеження відносно способу переміщення: їжак може рухатися із поточного квадратика тільки один із двох сусідніх правий або нижній.
Складіть програму яка знаходить максимальну кількість яблук, яку може зібрати їжак, рухаючись у напрямі потрібного квадратика.

Технічні вимоги:
Вхідний файл: EG.IN
Вихідний файл: EG.OUT
План саду заданий таблицею apples, яка містить m рядків та т стовпчиків. Елемент apples[i,j] таблиці вказує на кількість яблук які впали з дерева в зону з координатами i,j.

Формат вхідних даних:
Перший рядок містить два числа m та n, вказаних через пропуск: перше число – кількість рядків, друге – кількість стовпчиків у таблиці.
У кожному із наступних m рядків міститься по n чисел, вказаних через пробіл.

Формат вихідних даних:
Один рядок – натуральне число.

Приклад файлів вхідних та вихідних даних:
EG.IN
3 3
1 2 3
1 2 3
1 2 3
EG.OUT
12

[Dreamer]

Вариант решения на языке Паскаль...

Program Eg;
type zero=1..00;
var apples:array[zero,zero] of byte;
m,n,i,j:zero;
max:word;
f:text;
Procedure Rec(i,j:zero;sum:word);
begin
if i=m then
while j<>n do
begin
j:=j+1;
sum:=sum+apples[i,j]
end else
if j=n then
while i<>m do
begin
i:=i+1;
sum:=sum+apples[i,j]
end else
begin
Rec(i+1,j,sum+apples[i+1,j]);
Rec(i,j+1,sum+apples[i,j+1])
end;
if sum>max then max:=sum
end;
begin
Assign(f,'eg.in');
Reset(f);
readln(f,m,n);
for i:=1 to m do
for j:=1 to n do
read(f,apples[i,j]);
Close(f);
max:=0;
Rec(1,1,apples[1,1]);
Assign(f,'eg.out');
Rewrite(f);
writeln(f,max);
Close(f)
end.

[Lelya]

а ві мне курсавые написать не хотите а то самой лень)

[Evil Genius]

Сообщение от Lelya

а ві мне курсавые написать не хотите а то самой лень)

тема, куда сдаётся, скока денег?

[Lelya]

малеха не потеме акссес

[Evil Genius]

Сообщение от Lelya

малеха не потеме акссес

лицей ?

[Dreamer]

Сообщение от Lelya

малеха не потеме акссес

Какой лицей какой аксесс... оффтоп

[zwitter]

бросай чего-нить актуально-замудренного. стариной потрясти хочецца ))

[Dreamer]

Сообщение от zwitter

бросай чего-нить актуально-замудренного. стариной потрясти хочецца ))

...давай условия...

[Absent]

Тема радует.
Еслиб не проэкт, померялся б.
Хочется, и колется 8)))

[TAVI$K@R()N]

вот задания заочной олимпиады ФТЛ:

Олимпиада по информатике (9-11 классы)
2006-2007 уч. год
Заочный тур
1. Квадратный корень. Пусть извлечение квадратного корня из числа 2 осуществляеться по итерационной формуле ХN=0,5* ХN-1+1/ХN-1. Необходимо выяснить, сколько шагов следует осуществить, чтобы добиться требуемой точности , если начальное значение корня (первая итерация) задаеться вручную и равно Х.
2. Многочлен. Вычислить значение многочлена (n<9).
3. Чай. Некто имеет чай трех сортов – цейлонский по 5 грн за фунт, индийский по 8 грн за фунт и китайский по 12 грн за фунт. В каких долях нужно смешать эти три сорта, чтобы получить чай стоимостью 6 грн за фунт.
4. Девичья хитрость. Золотошвея взяв 20 девушек в учение, разместила их в 8 комнатах своего дома так, как показано на рисунке. По вечерам золотошвея обходила дом и проверяла, чтобы в комнате на каждой стороне его было по 7 девушек. Однажды к девушкам в гости приехали 4 подружки и, заговорившись, остались у них ночевать, причем все 24 девушки разместились в комнатах так, что вечером золотошвея насчитала в комнатах на каждой стороне дома опять по 7 девушек. На следующий день 4 девушки пошли провожать своих подруг и дома не ночевали. Оставшиеся 16 девушек разместились так, что опять вечером золотошвея насчитала в комнатах с каждой стороны дома по 7 девушек. Как размещались девушки по комнатам в двух последних случаях?
5. Пляшущие человечки. В рисованных мультфильмах иллюзия движения создается последовательной сменой кадров, каждый из которых фиксирует очередное положение движущегося объекта. Используя этот принцип, получить мультфильм, показывающий пляшущего человечка.
6. Алгебра и гармония. Разработать орнамент на основе каких-либо математических кривых и заполнить ими экран.
7. Маршрут. В таблице размером МхМ, где М<13, клетки заполнены случайным образом числами от 0 до 9. Найти маршрут из ячейки С(1,1) в ячейку С(М,М) такой что:
1) он будет состоять из отрезков, соединяющих центры ячеек имеющих общую сторону;
2) длина маршрута минимально возможная;
3) из всех маршрутов удовлетворяющих условию 1) и 2), искомый маршрут тот, сумма цифр которого минимальна.
8. Суперчисло. На "Играх гигантов" проводится интеллектуальный конкурс "Суперчисло", в котором необходимо в десятичной записи натурального числа N поменять местами только две цифры, чтобы полученное число стало как можно большим. Помогите украинской команде победить в конкурсе.
9. Часы. Два товарища договариваются о встрече через определенное время. У одного из них на циферблате часы обозначаются числами от 1 до 12. У другого есть только секундомер, на котором отсчет времени ведется в секундах и может выражаться неотрицательным целым числом. Когда часы показывали время Н часов М минут S секунд, был включен секундомер. Определить время, которое будет показано на часах, если по секундомеру пройдет Т секунд.
10. Добровольное пожертвование. В загадочной стране Труляля, после очередной цветной революции, в борьбе с коррупцией ввели новые денежные купюры номиналом 1, 3, 9, 27, 81… Пока цветные воюют с мифическими коррупционерами, шустрый бармен свои «старые» привычки перенес на новый лад, назвав чаевые добровольным пожертвованием. Ваша задача помочь путешественнику минимизировать растраты, то есть заплатить по чеку и, не нарушая покоя в стране, выдать наименьшее добровольное пожертвование бармену. Обменные пункты в стране Труляля выдают только по одной купюре одного номинала и в кармане путешественника всех новых купюр ровно по одной. Инфляционные процессы не дают возможности «отдохнуть» на сумму большую одного миллиарда.
11. Физический эксперимент. При проведении физического эксперимента по фиксации траектории движения частиц с помощью ЭВМ детекторы сгруппированы так, что перекрытая ими область отображается в памяти ЭВМ матрицей С [1..n,1..k]. Элементы этой матрицы представляют собой цифровое фото исследуемой области. При фиксации детекторами элементарной частицы в позиции (i, j) соответствующий элемент матрицы С принимает значение 1, в противном случае 0.
Требуется определить, содержит ли данная цифровая фотография информацию, которая может быть интерпретирована как след прямолинейной траектории, начинающейся и заканчивающейся за пределами фотографии. Если такая информация обнаружена, то необходимо вывести координаты позиций – концов изображенной на фотографии траектории. Считать, что края фотографии параллельны осям системы координат, а частицы движутся под углом кратном 45 градусов, относительно краев фотографии.
12. Минимальное число. Из двух данных целых чисел создать наименьшее возможное, сохраняя первоначальную последовательность цифр чисел и используя все цифры данных чисел.
13. Кодировщик. Написать программу, реализующую шифрование/дешифрование методом Виженера данного текстового файла. Алгоритм заключается в следующем: каждой букве английского алфавита сопоставляется некоторое число (номер). Ключ задается словом из n букв и повторно записывается под шифруемым сообщением. Получаем таблицу k столбцов (k- количество символов в сообщении) и 2 строк. Далее в каждом столбце из 2 букв путем сложения номеров букв получаем некоторое новое число, которому соответствует некоторая буква. Эту букву записываем на место первоначальной буквы. Процесс дешифрования выполняется точно также, только необходимо вычитать (по модулю длины алфавита).
Например, если в алфавите 4 буквы: « _ », «А», «В», «С», с номерами от 0 до 3 соответственно, сообщение имеет вид: «», а ключ – «ВАС»,то шифрование будет иметь следующий вид:
Сообщение

ААВ_ВАС_ССАВ
Повторный ключ

ВАСВАСВАСВАС
Зашифрованное сообщение

СВАВСВВА_ВВВ


сори решений нема я не все смог сделать и всерцах все выкинул))

[Dreamer]

Олимпиада не хилая!
А что ты смог сделать?
Жаль в ФТЛе маловато информатики...