Школа олімпійського резерву з інформатики

Оголошення

Добавил(а) Administrator

26.01.11 11:27

Увага!!!

Заняття в школі обдарованих дітей з інформатики в 2011 році розпочнуться 04 лютого 2011 року (п'ятницю) о 15.00.

Вітаємо переможців

Добавил(а) Administrator

26.01.11 11:05

Переможці ІІІ етапу Всеукраїнської учнівської олімпіади з інформатики 2010-2011 н. р.

№ п.п.	Прізвище, ім'я та по батькові учня	Клас	Зайняте місце
1	Лагода Віталій Володимирович	8	ІІІ
2	Маснуха Іван Іванович	9	І
3	Пілецький Назар Анатолійович	9	ІІІ
4	Прус Владислав Васильович	10	ІІ
5	Омелян Володимир Петрович	10	ІІІ
6	Міщук Юрій Сергійович	10	ІІІ
7	Семенюк Олександр Петрович	10	ІІІ
8	Бойко Роман Вікторович	11	І
9	Дідух Сергій Сергійович	11	ІІ
10	Кочетков Олексій Олександрович	11	ІІІ
11	Радзивилюк Іван Михайлович	11	ІІІ
12	Лугвіщик Андрій Вікторович	11	ІІІ
13	Задворний Юрій Миколайович	11	ІІІ

Матеріали III етапу Всеукраїнської учнівської олімпіади з інформатики

Добавил(а) Administrator
19.01.11 05:41
Тести та умови до завдань III етапу Всеукраїнської учнівської олімпіади з інформатики
Последнее обновление 19.01.11 05:53

II етап Всеукраїнської олімпіади 2010-2011

Добавил(а) Administrator
08.12.10 14:13
У вкладці Файли розміщено матеріали II етап Всеукраїнської олімпіади 2010-2011 н.р.
Последнее обновление 08.12.10 14:25

Побудова опуклої оболонки

Добавил(а) Гісь І.В.
25.11.10 16:58
Опукла оболонка View more presentations from igis.
Последнее обновление 25.11.10 17:40

Задача Island

Добавил(а) Гісь

18.11.10 13:59

Задача Island

Алгоритм

Якось на Багатокутію напали Трикутники. Королівство Багатокутія лежить на острові і займає всю його територію. Острів має вигляд опуклого багатокутника (такого багатокутника, у якого кожен внутрішній кут менший від 180°). У Багатокутії знаходиться певне число фабрик програмного забезпечення. Кожна фабрика приносить певні постійні прибутки або збитки.

Трикутники вирішили заволодіти частиною площі Багатокутії, яка має наступні властивості:

• має вигляд трикутника, вершинами якого є три різні вершини багатокутника-острова;

• принесе їм якнайбільші прибутки, тобто сума прибутків (збитків), що приносять фабрики, які знаходяться на території, буде якнайбільшою.

Відомо, що якщо фабрика лежить на границі або у вершині території, якою заволоділи Трикутники, то вона належить їй. Територія, яка не містить жодної фабрики, приносить прибуток рівний 0.

Король Багатокутії вирішив порахувати, наскільки великі збитки для економіки країни може принести нашестя Трикутників. Допоможіть йому і напишіть програму, яка визначає суму прибутків (збитків), що дають фабрики, якими хочуть заволодіти Трикутники.

Формат вхідних даних

Перший рядок вхідного файлу містить одне ціле число n (3<=n<=600), число вершин багатокутника-острова.

В наступних n рядках записано по два цілих числа xj та yj - координати вершин багатокутника-острова у порядку його обходу за годинниковою стрілкою (-10000<= xj,yj<=10000), відокремлених одним пробілом.

В (n+2)-му рядку міститься одне ціле число m – число фабрик (1<=m<=10000), що розташовані на острові.

В наступних m рядках міститься по три цілих числа: x'i, y'i і wi (-10000<=x'i, y'i<=10000, -100000<=wi=0) або збиток (для wi<0), який фабрика приносить. Кожна фабрика лежить на острові-багатокутнику, тобто всередині його або на його границі (березі). Декілька фабрик можуть лежати в одному і тому ж місці, тобто мати ті самі координати.

Формат вихідних даних

Перший і єдиний рядок вихідного файлу повинен містити одне ціле число, що означає максимальну суму прибутків, які приносять фабрики, що знаходяться в межі трикутника, вершинами якого є три різні вершини багатокутника-острова. Може бути, що число це буде від’ємним.

Приклад

Island.DAT

Island.SOL

4 1

1 4

8 9

11 5

8 1

7 2 3

6 3 -1

4 5 3

9 6 -4

1. Перебрати всі трикутники опуклого многкутника

(три вкладених цикли

i=1..n-2

j=i+1 .. n-1

k=j+1.. n

для чотирикутника 1,2,3; 1,2,4; 1,3,4; 2,3,4)

2. Перевірити належність точок трикутнику перебравши всі точки

(перевірити можна за площою трикутників: якщо точка лежить в трикутнику то сума площ трьох трикутників утворених з даною точкою та вершинами тркутника рівна площі трикутника)

Формула площі трикутника за кординатами вершин:

S=1/2*|x1*y2-x2*y1+ x2*y3-x3*y2+ x3*y1-x1*y3|

1. Задача river

Добавил(а) Гісь

18.11.10 13:46

1. Задача river (20 балів)

Алгоритм

1. Задача river (20 балів)

Ім’я вхідного файлу: river.DAT

Ім’я вихідного файлу: river.SOL

Максимальний час роботи на одному тесті: 3с

Між двома королівствами Читанія та Писанія протікає річка Пряма, яка тече або з Півночі на Південь, або з Заходу на Схід. Король Писанії вирішив завоювати Читанію. Для нападу необхідно збудувати переправу.

Де розпочинати будівництво, якщо король хоче, щоб всі війська, що розташовані в N (1<=N<=100) гарнізонах, могли якнайшвидше зібратися біля переправи? Війська вирушають з пунктів дислокації одночасно і рухаються з однаковою швидкістю по прямій до переправи.

Формат вхідних даних

Перший рядок вхідного файлу містить чотири цілих числа: a1, a2, b1, b2 ((a1,a2), (b1,b2) – координати двох точок річки Прямої).

Відомо, що або a1=b1 , або a2=b2, -30000<=a1, a2, b1, b2 <=30000.

У другому рядку знаходиться ціле число N – кількість гарнізонів (1<=N<=100).

В наступних N рядках записано по два цілих числа xj та yj – координати гарнізонів

(-30000<= xj,yj<=30000), відокремлених одним пробілом.

Формат вихідних даних

Ваша програма повинна вивести у вихідний файл рядок, що містить два числа X, Y – координати переправи з точністю до двох знаків після коми, розділених одним пропуском.

Приклад

river.DAT

river.SOL

2 1 2 4

3 2

6 3

9 9

8 6

2.00 8.75

1. Знайти максимальне та мінімальне значення серед координат точок по x (y).

2. На проміжку від мінімального до максимального значення з кроком 0.01 знайти максимальну відстань від точки на прямій до точок.

3. Серед знайдених максимальних відстаней вибрати мінімальну, знайдена точка на прямій буде розв'язком задачі.

обчислювальна геометрія

Добавил(а) Administrator

11.11.10 19:51

Обчислювальна геометрія

Література

Гісь І.В. Обчислювальна геометрія

Омелян П.П. Обчислювальна геометрія

Завдання та розв’язки ІІІ етапу Всеукраїнської учнівської олімпіади з інформатики в 2009-2010 н.р.

Другий тур

Задача VIОLАТION (20 балів)

В деякому місті шоферам заборонено при русі робити ліві повороти. За кожен такий поворот шофер повинен сплачувати штраф в розмірі М гривень. Для спостереження за рухом транспорту в місті встановлена комп'ютерна система, яка фіксує координати автомобіля на початку руху, в кінці та при кожному повороті.

Необхідно по заданій послідовності координат руху обчислити суму штрафу.

Вхідні дані: В першому рядку вхідного файлу VIOLATION.DAT записано N - кількість зафіксованих координат руху деякого автомобіля та М - величина штрафу, в наступних рядках координати автомобіля в процесі руху - (х_i, у_i), і=1,2,...,М, де (х₁, у₁) - точка початку руху, (х_N,у_N) - остання точка маршруту автомобіля.

Всі числа цілі та знаходяться в межах від -1000 до 1000.

Вихідні дані: Єдиний рядок вихідного файлу VIOLATION.SOL має містити суму штрафу.

Приклад:

VIOLATION.DAT

VIOLATION.SOL

5 50

0 0

2 0

1 1

5 1

5 -1

Розв’язок

{Визначення координат векторів}

x[n+1]:=x[1];

y[n+1]:=y[1];

for i:=1 to n do begin

a[i]:=x[i+1]-x[i];

b[i]:=y[i+1]-y[i];

end;

{Підрахунок кількості додатних добутків}

a[n+1]:=a[1];

b[n+1]:=b[1];

k:=0;

for i:=1 to n do

if a[i]*b[i+1]-a[i+1]*b[i]>0 then k:=k+1;

{Виведення результату}

writeln(k)

program violatio;

{$APPTYPE CONSOLE}

var x,y,a,b,vd:array[1..1000] of real;

s,n,i,j,k:integer;

f:text;

begin

{Задання координат вершин многокутника}

assign(f,'violatio.dat');

reset(f);

readln(f,n,s);

for i:=1 to n do

readln(f,x[i],y[i]);

close(f);

{Визначення координат векторів}

for i:=1 to n-1 do begin

a[i]:=x[i+1]-x[i];

b[i]:=y[i+1]-y[i];

end;

{Підрахунок кількості від'ємних добутків}

k:=0;

for i:=1 to n-1 do

begin

vd[i]:=a[i]*b[i+1]-a[i+1]*b[i];

if vd[i]>0 then k:=k+s;

end;

{Виведення результату}

assign(f,'violatio.sol');

rewrite(f);

writeln(f,k);

close(f);

end.

Другие статьи...

Страница 25 из 27

Главное меню

Статистика

Пользователей : 261
Статей : 225
Просмотрено статей : 105854

Вход/Регистрация

Нет

Сайт підготовки до олімпіади з інформатики

Главное меню

Статистика

Вход/Регистрация