Семінар вчителів інформатики Володимир-Волинського району,01.11.2013

П'ятниця, 01 листопада 2013, 21:31

Технологія роботи з обдарованими дітьми.

Розв’язування олімпіадних задач з інформатики

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=15 – Підгтовка до олімпіади 2013 (логін user400-user430; пароль 400-430).

Єдиний спосіб вивчати нову мову програмування –

писати на ній програми.
Брайен Керніган

План роботи

1) Олімпіадна інформатика. Методика організація роботи з обдарованими учнями.

2) Тематика олімпіадних задач. Методика складання алгоритмів та їх аналіз.

3) Правила проведення олімпіад по програмуванню. Типові помилки і налагодження програм. Система для автоматичного тестування програм ejudge.

4) Практикум з розв’язування олімпіадних задач.

Олімпіадна інформатика

1. Що таке олімпіадна інформатика?

Що потрібне для успішної участі в олімпіадах по інформатиці? Як показує практика, тільки знання мови програмування для цього явно не достатньо. Взагалі, виявляється, що олімпіадні задачі по інформатиці лежать десь на стику математики і програмування. І дуже часто виявляється, що розв’язуючи задачі школярі не тільки вчаться програмувати, але і освоюють нові розділи математики.

2. Як перевіряються розв’язки задач олімпіади

Історично склалося так, що розв’язки на олімпіадах по програмуванню перевіряються автоматично. Ваше завдання написати програму, яка за заданими вхідними даними обчислює і виводить вихідні дані.

3. Апаратне та програмне забезпечення

Учасникам олімпіади можуть вибирати мову програмування с заданого переліку: Pascal, C або C++. Система програмування Free Pascal 2.0 (чи новішої версії), GCC 4.2 (чи новішої версії), Turbo Delphi Explorer, Visual C++ 2008 Express).

4. Тематика задача олімпіади

Завдання олімпіади мають бути алгоритмічного характеру, тобто основними результатами роботи учасника має бути: алгоритм, що правильно та ефективно розв’язує поставлену задачу, та програма, що реалізує запропонований алгоритм.

Основними категоріями олімпіадних задач є:

Геометрія Графічні задачі Динамічне програмування Довга арифметика Жадібний алгоритм Задачі для початківців Комбінаторика Масиви Математика Математичне моделювання			Обробка рядків Послідовності Рекурсія, перебір Логічні задачі Сортування Структури даних Теорія графів Теорія ігор Теорія чисел
	· Етап олімпіади	· Інформатика	· Інформаційні технології
	· ІІ етап	- Теорія чисел: розклад числа на множники - Обчислювальна геометрія: довжина відрізка, властивості геометричних фігур - Пошук та сортування масивів - Повний перебір, динамічне програмування ·	- Текстовий редактор: параметри сторінки, форматування шрифту і абзацу, колонтитули, форматування графічних об’єктів, колонки - Презентації: створення авто фігур, налаштування анімації руху по колу з налаштуванням періоду - Електронні таблиці: формули з використанням функцій (логічних, математичних ЕСЛИ, СУММЕСЛИ, ABS), побудова діаграм - СУБД: створення таблиць, форм, запитів на вибір та з параметром, звітів з групуванням
	· ІІІ етап	- Синтаксичний аналіз: робота з рядками - Пошук та сортування масивів - Теорія чисел: НСД - Динамічне програмування - Теорія графів	- Текстовий редактор: параметри сторінки, форматування шрифту і абзацу, колонтитули, форматування графічних об’єктів, колонки, розділи - Презентації: створення авто фігур, групування, налаштування анімації, кнопки, гіперпосилання - Електронні таблиці: формули з використанням функцій (логічних, математичних, посилання і масиви, перевірка властивостей і значень ЕСЛИ, СУММЕСЛИ, ABS, СТОЛБЕЦ, СТРОКА, ЕПУСТО), побудова діаграм, елементи форми - СУБД: створення таблиць, зв’язок між таблицями, створення декількох ключових полів, форм в ручну, запитів на вибір та з параметром, групові операції , звітів з групуванням, макроси
	· ІV етап	- Повний перебір - Жадібні алгоритми - Динамічне програмування - Граф: пошук найкоротшого шляху, пошук в ширину - Обчислювальна геометрія: опуклі многокутники - Структури даних: дерево	- Текстовий редактор: макрос в режимі автозаписуванням

5. Системи тестування

Працюйте в он-лайн системах, які автоматично перевіряють та тестують Ваші розв’язки:

http://olymp.sumdu.edu.ua - Веб-ресурс підтримки та проведення шкільних та студентських олімпіад з інформатики

http://www.e-olimp.com.ua/ - Інтернет-портал організаційно-методичного забезпечення дистанційних олімпіад з програмування для обдарованої молоді навчальних закладів України

http://www.olymp.vinnica.ua/ - Центр підтримки та проведення олімпіад школярів з використанням можливостей Internet.

Список тестуючи систем

Назва	Сайт	Система
ejudge	ejudge.ru	Linux
PCMS2	посилання	Windows
Contester	contester.ru	Windows, Linux
Executor	acmtest.ru	Windows
PC²	посилання	Windows, Linux
olympiads.ru	посилання	Windows
DOMjudge	посилання	Linux
dudge	посилання	Кросс-платформенная (Java)

7. Логічні задачі

Задача 1.

Переможці олімпіад.

П’ятеро однокласників: Ірина, Тарас, Катя, Сергій і Микола стали переможцями олімпіад школярів з фізики, математики, інформатики, літератури та географії. Відомо, що:

- переможець олімпіади з інформатики вчить Іірину і Тараса працювати на комп’ютері;

- Катя і Сергій також зацікавились інформатикою;

- Тарас завжди побоювався фізики;

- Катя, Тарас і переможець олімпіади з літератури займаються плаванням;

- Тарас і Катя привітали переможця олімпіади з математики;

- Іра шкодує, що в неї залишається мало часу на літературу.

Переможцем якої олімпіади став кожен з учнів?

8. Базові структури алгоритмів: слідування, розгалуження, цикл.

Задача 2. «Фотокартка» (PHOTO)

Учень на новенькому кольоровому струменевому принтері учень надрукував фотографії зроблені у свій день народження. Розмір фото AxB cм. Роздільна здатність принтера R точок на дюйм (1 дюйм = 2,54 см).

Завдання

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

Вхідні дані

Перший рядок містить два дійсні числа, які задають розмір фотокартки. Останній рядок містить натуральне число, яке задає роздільну здатність. Усі числа вхідного файлу за абсолютною величиною не перевищують 1 000 000 000.

Вихідні дані

Єдиний рядок файлу містить шукану кількість мегапікселів на фотографії, як дійсне число з двома знаками після коми.

Приклад

input.dat

output.ans

2.54

1000

1.00

Задача 3. «Клас» .

На початку навчального року класний керівник між учнями класу поділила N зошитів та M олівців. Скільки учнів в класі, якщо відомо їх не менше ніж K і кожний з учнів отримав однакову кількість зошитів та олівців.

Вхідні дані

Перший рядок містить натуральні числа N, M, K. Усі числа вхідного файлу не перевищують 1 000 000 000.

Вихідні дані

Єдиний рядок файлу містить знайдену кількість учнів. Якщо результатів декілька, то вивести всі через пропуск в зростаючому порядку.

Приклад

input.dat

output.ans

138

Задача 4. «День народження» – 30 балів.

Учень на своє день народження роздав учням класу цукерки, в тому числі і собі. Хлопцям давав парну кількість, а дівчатам непарну кількість. Підрахувати кількість дівчат та хлопців в класі.

Вхідні дані

Перший рядок містить загальну кількість учнів, натуральне число N.

В наступних рядках кількість розданих цукерок.

Усі числа вхідного файлу не перевищують 1 000 000 000.

Вихідні дані

Єдиний рядок файлу містить кількість дівчат та хлопчиків через пропуск.

Приклад

input.dat

output.ans

3 2

9. Структуровані типи величин.

Операції з масивом.

Операція з масивом

Pascal

C++

Опис

Var a:array[1..100] of integer;

i, n:integer;//індекс, кількість елементів

int a[100];

int i, n;//індекс, кількість елементів

Введення

readln(n);

for i:=1 to n do read(a[i]);

cin>>n;

for(i=1;i<=n;i++)cin>>a[i];

Виведення

for i:=1 to n do write(a[i],’ ‘);

for(i=1;i<=n;i++)cout<<a[i]<<” “;

Сумування

s=0;

for i:=1 to n do s:=s+a[i];

s=0;

for(i=1;i<=n;i++)s=s+a[i];

Пошук

readln(k);

for i:=1 to n do if a[i]=k then writeln(i);

cin>>k;

for(i=1;i<=n;i++) if (a[i]==k) cout<<i;

Пошук максимального

max:=a[1];nmax:=1;

for i:=2 to n do if a[i]>max then begin max:=a[i];nmax:=i;end;

max=a[1];nmax=1;

for(i=2;i<=n;i++)if (a[i]>max) {max=a[i];nmax=i;}

Сортування

for i:=1 to n -1do

for j:=1 to n -1do

if a[j]>a[j+1] then begin

temp:=a[j];

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

a[j+1]:=temp;

end;

for(i=1;i<n;i++)

for(j=1;j<n;j++)

if (a[j]>a[j+1])

{temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;}

Стирання

n:=n-1;

for i:=k to n do a[i]:=a[i+1];

n=n-1;

for(i=k;i<=n;i++)

a[i]=a[i+1];

Вставка

n:=n+1;

for i:=n downto k+1 do

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

n=n+1;

for(i=n;i>=1;i--)

a[i]=a[i-1];

10. Робота з файлами

Pascal

C++

var f1,f2:text;

assign(f1,’input.dat’);

reset(f1);

read(f1,...);

close(f1);

assign(f2,’output.dat’);

rewite(f2);

write(f2,...);

close(f2);

#include <fstream.h>

void main()

{

ifstream inp;inp.open("input.dat");

int a,b,c;

inp>>a>>b;

inp.close();

c=a+b;

ofstream out;out.open("output.sol");

out<<c;

out.close();

}

assign(input,’input.dat’);

reset(input);

read(...);

close(input);

assign(output,’output.dat’);

rewite(output);

write(...);

close(output);

#include <fstream.h>

ifstream inp("input.dat");

ofstream out("output.sol");

void main()

{

int a,b,c;

inp>>a>>b;

c=a+b;

out<<c;

}

· Є велика кількість завдань, які вимагають знання з теорії чисел. Наприклад , знаходження простих чисел, розкладання на прості множники , поділ з остачею, НСД та НСК і т.д.

· Ряд	· Приклад	· Формула N елемента	· Рекурентне співвідношення
· Непарні числа	· 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21	· 2n-1	· a_n=a_n-1+2
· Арифметична прогресія	· 3, 6, 9, 12,15,18,21	· a_n=a₁+(n-1)d	· a_n=a_n-1+d
· Прості	· 2, 3, 5, 7, 11, 13, 17, 23	·	·
· Фібоначчі	· 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233	· 1/√5((1+√5)/2-(1-√5)/2)ⁿ	· F(n) = F(n-1) + F(n-2) для F(0) = 0 та · F(1) = 1.
· Факторіал	· 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800	· n(n-1)(n-2)…2.1	· F(n)=F(n-1)*n
· Каталана	· 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796	· (2n)!/(n!(n+1)!)	· C_n=∑C_iC_n-1-i
· Комбінації	· 1,3,6,3,1	· n!/(k!(n-k)!	· C_mⁿ=C_m^n-1(m-n+1)/n
· …	·	·	·

http://oeis.org - Інтерактивна Енциклопедія цілочислових послідовностей

Практичний тур

http:://olymp.gimn14.lutsk.ua/new-register

- вибрати турнір: Опорна школа. Теорія чисел

- створити обліковий запис, зареєструватися в системі ввівши логін, адресу електронну пошту (пароль записати)

- ввійти в систему

- відредагувати дані (ввести ім’я учасника: Прізвище, ім’я, школа)

- підтвердити реєстрацію

- протестувати задачі

Задача 5.

XVII Всеукраїнська олімпіада з інформатики. Другий тур. Працівники (100 балів)

На заводі кожна з N деталей може бути обробленою на одному з двох верстатів: A або B. Кожна деталь має порядковий номер від 1 до N. До обробки деталі поступають послідовно, у відповідності зі своїми номерами. Кількість деталей завжди парна.

Існують правила, за якими визначається чи можна обробляти деталь на певному верстаті.

1) Якщо на поточний момент на верстаті B була оброблена така ж кількість деталей, як і на верстаті A, то наступна деталь повинна бути оброблена на верстаті A.

2) У підсумку на кожному з верстатів повинно бути оброблено однакову кількість деталей.

Скільки існує людей, стільки і думок. Кожен із працівників цього заводу запропонував свою послідовність обробки деталей, причому всі пропозиції виявилися різними, але такими, що задовольняють правилам 1 і 2.

Завдання

Напишіть програму STAFF, що за інформацією про кількість деталей N визначає максимальну можливу кількість працівників заводу.

Вхідні дані

Єдиний рядок вхідного файлу STAFF.DAT містить парне число N (2≤N≤28) – кількість деталей яку необхідно обробити.

Вихідні дані

Єдиний рядок вихідного файлу STAFF.SOL має містити ціле число – максимальну можливу кількість працівників заводу.

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

input.dat	output.ans
4	2

Перший працівник вважає що на верстаті A необхідно обробити деталі 1 та 2, а на верстаті B, відповідно, 3 та 4. Другий має думку, що на верстаті A потрібно обробити деталі 1 та 3, а на станке B – деталі 2 та 4. Інших варіантів послідовності обробки немає.

Задача 6.

XIX Всеукраїнська олімпіада з інформатики. Перший тур. Дільники (100 балів)

За заданим натуральним числом N необхідно обчислити кількість натуральних чисел, які є дільниками N! (факторіалу числа N).

Наприклад, при N=4, N!=4·3·2·1=24. Це число має такі дільники: 1, 2, 3, 4, 6, 8, 12, 24. Таким чином шукана кількість дорівнює 8.

Завдання

Напишіть програму DIVISOR, що за натуральним N, знаходить кількість дільників його факторіалу.

Вхідні дані

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

Вихідні дані

Єдиний рядок вихідного файлу DIVISOR.SOL має містити одне ціле число – знайдену кількість дільників числа N!

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

input.dat	output.ans
4	8

Задача 7.

Просте число — це натуральне число, яке має рівно два натуральних дільника (лише 1 і саме число)

Послідовність простих чисел починається так:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 , 127, 131, 137, 139, 149, …

Написати програму виведення простих чисел в діапазоні до N.

Мова програмування

Варіант 1

Варіант 2

Pascal

var n,i,j:integer;

p:integer;

begin

readln(n);

for i:=2 to n do

begin

p:=0;

for j:=2 to round(sqrt(i)) do

if i mod j =0 then p:=1;

if p=0 then write(i,' ');

end;

end.

var a:array[1..100000000] of integer;

j,k,n,i:integer;

begin

readln(n);

for i:=1 to n do a[i]:=i;

a[1]:=0;

i:=1;

while i<=n div 2 do begin

while a[i]=0 do i:=i+1;

j:=i+a[i];

while j<=n do begin

a[j]:=0;

j:=j+a[i];

end;

i:=i+1;

end;

for k:=1 to n do

if a[k]<>0 then write(a[k],' ');

writeln;

end.

С++

// прості 2 3 5 7 11 13 17

#include "stdafx.h"

#include "iostream"

using namespace std;

int main()

{int n,i,j,p;

cin>>n;

for (i=2;i<=n;i++)

{p=0;

for (j=2;j<i; j++)

if (i%j==0) p=1;

if ( p==0) cout<<i<<" ";}

return 0;

}

#include "iostream"

using namespace std;

int main()

{int n;

cin>>n;

int *a=new int[2*n];

int j,i;

for(i=1;i<=n;i++)a[i]=i;

a[1]=0;i=1;

while (i<=n/2)

{while (a[i]==0) i++;

j=i;

while (j<=n){j=j+a[i];a[j]=0;}

i++;

}

for (i=1;i<=n;i++)

if (a[i]!=0)cout<<a[i]<<" ";

}

Фіксація часу роботи програми

Pascal (Delphi)

C++ (Visual C++)

uses

SysUtils, windows;

var time:int64;

begin

time:=gettickcount;

//*****************************

time:=gettickcount-time;

writeln(time/1000:0:5);

end.

#include <time.h>

using namespace std;

int main()

{

//системний час до

clock_t start = clock();

//*********************

// час після

long double r=(clock() - start)*1. / CLOCKS_PER_SEC;

cout<<"times work = "<<r<<endl;

return 0;

}

Теорія графів

1	Пошук в глибину	void p(int k, int v) {c[k]=v; if (v==v2 \|\| k>=n) { if (v==v2) { //for (int i=1;i<=k;i++)cout<<c[i]<<" ";cout<<endl; int s=0; for (int i=1;i<k;i++)s=s+a[c[i]][c[i+1]]; //cout<<"s="<<s<<endl; if (s<m) m=s; } } else for (int i=1;i<=n;i++) if (a[v][i]>0) p(k+1,i); }
2	Флойда	k= 1; for(i= 1;i<=n;i++)x[i]=a[v1][i]; // {инвариант: x[i] = МинСт(1,i,k)} while (k!=n) { for(s=1;s<=n;s++){ y[s]=x[s]; for(i=1;i<=n;i++) if (y[s]>x[i]+a[i][s]) y[s]= x[i]+a[i][s]; // {y[s] = МинСт(1,s,k+1)} for (i=1;i<=n;i++) x[s]=y[s]; } k++; }
3	Форда	for (int k=1; k<=n; k++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) a[i][j] = min (a[i][j], a[i][k] + a[k][j]);
4	Прима

Задача 8. Дорога в гімназію.

Задача Дорога в школу

Имя входного файла:	`input.dat`
Имя выходного файла:	`output.ans`
Ограничение времени:	30 с
Ограничение памяти:	64 M

Задача 4. Дорога в гімназію

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

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

Наступні N рядків містять через проміжок координати Xi , Yi точок на карті. Значення координат по модулю менші 50000. Перші координати задають – координати доми, а останні – координати гімназії. Наступні рядків задають карту намальованих доріг початкова та кінцева точка.

Формат результату

Єдиний рядок має містити дійсне число з трьома знаками після коми – дожину найкоротшої дороги. Якщо дороги немає вивести "no".

Приклад

input.dat

output.ans

150 70

160 90

100 100

170 120

120 140

80 160

1 2

2 3

2 4

3 5

4 5

5 6

152.556

Задача 9. Дорога в гімназію 2.

На вимогу класного керівника учень знайшов в Інтернеті карту міста на якій він визначив і задав в декартовій системі координат координати точок на шляху від доми до гімназії, і намалював дороги між ними (див. рис). Допоможіть учню визначити довжину найкоротшої дороги та сам маршрут від доми до школи.

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

Формат результату

Єдиний рядок має містити дійсне число з трьома знаками після коми – дожину найкоротшої дороги та рядок цілих чисел, які задають маршрут. Якщо дороги немає вивести "no".

Приклад

input.dat

output.ans

150 70

160 90

100 100

170 120

120 140

80 160

1 2

2 3

2 4

3 5

4 5

5 6

152.556

1 2 4 5 6

Задача 10.

Збирання мита (TALLAGE) -100 балів.

Король країни Аріїв завоював N міст на території сусідніх держав.

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

Вхідні дані:

Перший рядок вхідного файлу містить натуральне число N (1≤N≤100) – кількість міст у країні, а також цілі числа X та Y – координати столиці.

Наступні N рядків містять через проміжок координати X_i , Y_i завойованих міст.

Значення координат по модулю менші 50000.

Вихідні дані:

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

Приклади:

input.dat

output.ans

6 0 0

1 1

-1 1

0 2

1 -1

-1 -1

0 -2

8.485

6. Список ресурсів

· http://vippolabinfo.16mb.com – сайт «Лабораторія інформатики сьогодні», методична підтримки напрямків роботи.

· http://vippoolimp.16mb.com – Волинська учнівська Інтернет олімпіада з програмування.

· http://schoololymp.byethost32.com – заочна школа роботи з обдарованими учнями з інформатики.

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=3 – ІІ етап (районний) Всеукраїнської олімпіади з інформатики 2012-2013 н.р. (логін user400-user430; пароль 400-430).

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=11 – ІІІ етап (обласний) Всеукраїнської олімпіади з інформатики 2012-2013 н.р. (логін user400-user430; пароль 400-430).

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=12 – тренувальний тур по підготовці до ІV етапу Всеукраїнської олімпіади з інформатики 2012-2013 н.р. (логін user400-user414; пароль 400-414).

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=15 – Підгтовка до олімпіади 2013 (логін user400-user430; пароль 400-430).