Вказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики icon

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

НазваниеВказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики
Дата конвертации06.10.2012
Размер137.17 Kb.
ТипЗадача
1. /_нформатика/Вказiвки до розв'язування завдань.doc
2. /_нформатика/Умови завдань(_нформатика 2009).doc
Вказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики
Завдання для проведення II етапу Всеукраїнської учнівської олімпіади з інформатики у 2009-2010 н р

Вказівки щодо розв’язування завдань ІІ етапу

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


(2009 -2010 н.р.)


Задача 1. CorrectLine (20 балів) На уроці англійської мови першокласник Петя переписав n разів рядок, написаний по-англійськи, з дошки у зошит. Виявилось, що через неуважність він у кожному рядку зробив рівно по одній помилці – невірно написав одну з літер рядка. Написати програму, яка допоможе учневі шукати початковий вигляд рядка.

Технічні умови.

Вхідний файл corln.dat містить n рядків однакової довжини l (1<n255, 1l255).

Вихідний файл corln.sol повинен містити шуканий рядок, якщо його можна визначити, або “NO” (без лапок), якщо цього не можна зробити.

В

Приклади:




corln.dat

corln.sol

абвгед

аувгдд

абвгод

абвгод

абагдд

абвгдд

qwerty

qwerta

qwerte

qwerty

NO




казівки до розв’язування
.

Для одержання правильно записаного рядка досить порівняння кількох написаних Петренком рядків. Природньо почати з двох перших. Врахувавши, що учень щоразу невірно писав лише одну літеру (1), після порівняння двох рядків можна точно вказати правильно написані літери. Можливі випадки:

1) Сумнівні дві літери. Наприклад, після порівняння рядків “абвгед“ та “аувгдд“, сумніви можуть виникнути лише для передостанньої літери “е“ у рядку “абвгед“ та другої літери “о“ у рядку “аувгдд“.

2) Сумнівна одна літера. З порівняння рядків “qwerty“ та “ qwerta“, бачимо, що тільки остання літера сумнівна.

Отже перше порівняння встановлює можливі місця сумнівних літер та їх кількість (2).

Далі аналіз досить проводити тільки для сумнівних місць. При цьому слід скористатись (1). У першому випадку, коли третій рядок “абвгод“ із спису сумнівних слід виключити друге місце, тобто друга літера точно “б“. Отже, у випадку 1) друге порівняння приводить до випадку 2).

Наступні порівняння слід проводити доти, поки не визначимо останню літеру, або, поки не закінчаться рядки (це означатиме, що визначити початковий рядок не можна).

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


Оцінка тестів до задачі CorrectLine

corln.dat

1

2

3

4

5

corln.sol

2

3

3

5

7



Задача 2. Sequence (25 балів) Деяка послідовність двійкових цифр одержується таким чином.

Першою записується цифра 1. Для продовження послідовності необхідно всі попередні цифри інвертувати (змінити 1 на 0, а 0 на 1) та дописати до уже побудованої послідовності справа, наприклад:

1-й крок

2-й крок

3-й крок

4-й крок

5-й крок

1

10

1001

10010110

1001011001101001

Написати програму Sequence, що визначає, яка двійкова цифра буде знаходитися на n-му місці в даній послідовності.

Технічні умови.

Вхідний файл У вхідному файлі seq.dat записано через пропуск в один рядок k+1 натуральне число, першом з яких є число k (1≤k≤10), що задає кількість наступних чисел, які є окремими тестами. Наступні k чисел задають числа ni (1≤ ni ≤65000, 1≤ik) − номери позицій у одержаній послідовності окремого тесту.

Вихідний файл seq.sol повинен містити єдиний рядок, у якому без пропусків та розділових знаків слід розмістити k двійкових цифр, які стоять на ni–х місцях відповідних тестів.


seq.dat

seq.sol

4 10 15 21 52

1011
Приклад:


Вказівки до розв’язування.

Щоб визначити двійкові символи, розміщені на вказаних місцях (у наведеному прикладі 1011), слід згенерувати послідовність щонайменше до 52-го символа включно. Отже перша проблема – запис цієї послідовності. Складності полягають у технічних умовах, адже максимальна довжина послідовності 65000 двійкових символів.

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




Але ці формули неефективні, бо обчислюють наступний елемент через попередній, крім того, для досить великих n рекурсія буде виконуватись довго. Але найбільшим недоліком є обмеженість розміру послідовності типом longint:

1844674407370955161510 = 11010011111111111111111111111111111111111111111111111111111111112

Тому необхідно знайти іншу математичну модель. Вона стає очевидною, а головне – несподівано легкою, коли співставити два сусідні елементи, наприклад, для 16 і 32 числових кодів:

1001011001101001 (1)

10010110011010010110100110010110. (2)

Співставлення приводить до гіпотези, проглядаючи елемент (1), необхідно у рядок (2) вставляти “10“, якщо у рядку (1) елемент дорівнює “1“, і “01“, якщо у (1) елемент дорівнює “0“. Виходячи з цього, програма матиме вигляд:

program Sequence;

var i,j,n,k:integer;

ari:array[0..20]of integer; ars:array[1..65536]of char; f:text;

begin

Assign(f,'seq1.dat');Reset(f);

i:=0;

repeat

Read(f,ari[i]);i:=i+1

until EoF(f);

n:=ari[0];Close(f);

ars[1]:='1';

for i:=1 to ari[n] do begin

j:=2*i;

if ars[i]='1'

then begin ars[j-1]:='1';ars[j]:='0' end

else begin ars[j-1]:='0';ars[j]:='1' end end;

Assign(f,'seq.sol');ReWrite(f);Close(f);

Assign(f,'seq.sol');Append(f);

i:=1;j:=ari[i];

while j<=ari[n] do begin

Write(f,ars[j]);

i:=i+1;j:=ari[i] end;

Close(f);

end.

Оцінка тестів до задачі Sequence

seq.dat

1

2

3

4

5

seq.sol

2

2

4

8

9



Задача 3. Coding (25 балів) Повідомлення із m (2≤m≤100) малих латинських літер без пропусків між ними, яке містить n (1≤n≤26) різних літер, однозначно зашифровано послідовністю нулів та одиниць наступним чином: одна з літер (l1) кодується нулем; код кожної з решти літер li (2≤in) визначається кодом попередньої, до якого зліва дописано одиницю. Якщо m>2, то остання літера кодується кодом передостанньої, в якій нуль замінено на одиницю. Написати програму розшифровки повідомлення.

Технічні умови.

Вхідний файл cod.dat у першому рядку містить натуральне число n – кількість різних англійських літер у повідомленні. У кожному з n наступних рядків записано через пропуск малу латинську літеру та її код. Останній рядок представляє собою зашифроване повідомлення.

Вихідний файл cod.sol повинен містити розшифроване повідомлення.



cod.dat

cod.sol

4

m 0

g 10

k 110

f 111

10010110110111

gmgkkf
Приклад:


Вказівки до розв’язування.

Наводити програму немає потреби, адже він очевидний. З прикладу видно, що перша цифра “0“ може бути лише для літери “m“, у решті випадків код літери починається з “1“. Аналіз коду наступної літери зводиться до підрахунку підряд ідучих цифр “1“. Це однозначно розшифровує чергову літеру. Якщо поставлено дві підряд цифри “0“ і передує не гранична кількість цифр “1“ (для розглянутого прикладу це 3: “f“ – “111“), то наступна літера знову “m“.


Оцінка тестів до задачі Coding

cod.dat

1

2

3

4

5

cod.sol

2

2

3

9

9



Задача 2. Robot (30 балів) Інопланетна дослідницька база, обнесена парканом, охороняється роботом, який здійснює обхід території бази по її периметру. Відомо, що всі ділянки паркану розташовані строго вздовж паралелей або меридіанів, у кожній точці периметра сходиться не більше, ніж дві ділянки паркану. Перед початком вартування робота доставляють в будь-яку точку периметра, після чого він під керівництвом спеціальної програми починає обхід. Повне виконання програми повертає робота в ту ж точку, з якої він почав обхід. Написати програму, яка за даною програмою руху робота встановлює площу інопланетної бази. (відомо, що вона не перевищує ).


Технічні умови.

Вхідний файл robot.dat містить деяку кількість рядків, що визначають програму робота (не більше 1000 рядків). Кожен рядок складається з однієї літери, що визначає напрямок руху робота (N – на північ, E – на схід, S – на південь, W – на захід) та натуральне число m– кількість метрів, які повинен пройти робот у даному напрямку 1≤m≤1000.

Вихiдний файл robot.sol повинен містити єдине натуральне число – площу бази в квадратних метрах.

Вказівки до розв’язування.

Представимо дані традиційним способом – у вигляді прямокутного масиву. На мал. 3 програма обходу периметра виглядатиме так (таблиця1):

таблиця 1

N

E

N

E

S

E

S

E

S

W

S

E

S

W

N

W

S

W

5

1

2

1

1

3

2

3

2

2

1

1

1

4

2

1

2

2

Отже, паркан повністю поміщається в прямокутнику розмірами 7×8, тому можна використати робочий прямокутний масив A[0..7, 0..8] of integer. Якщо на координатній площині за початкову точку обходу взяти (0, 0), то розміри паркану у загальному випадку можна визначити з таблиці 2:

таблиця 2

x

0

0

1

1

2

2

5

5

8

8

6

6

7

7

3

3

2

2

0

y

0

5

5

7

7

6

6

4

4

2

2

1

1

0

0

2

2

0

0

Тобто, протяжність дослідницької бази по горизонталі дорівнюватиме Maxx ─ Minx, а її протяжність по вертикалі Maxy ─ Miny. Отже необхідний прямокутний масив у загальному випадку матиме формат:

A[0 .. Maxy ─ Miny, 0 .. Maxx ─ Minx] of integer.

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

Для визначення площі дослідницької бази залишається залишається циклічно обійти масив А, підрахувавши по горизонталях клітинки, заповнені нулями, якщо вони лежать між двома одиницями, як показано на мал. 3. Слід звернути увагу на те, що у рядку може бути не дві одиниці, тому слід враховувати, що в площу входять лише ті “відрізки“, які закінчуються непарними, якщо рахувати зліва направо одиницями.

Для обчислення площі подібного контура (підрахунку клітинок, які знаходяться всередині нього, закраски контура існує інший спосіб, рекурсивний):

алг ЗАПОВНЕННЯ_КОНТУРА(арг ціл n, арг рез ціл таб A[1:n, 1:n])

поч ціл x, y

¦ В_КОНТУР(n, A, x, y); ЗАПОВНИТИ_КОНТУР(n, x, y, A)

кін

алг В_КОНТУР (арг ціл n, арг рез ціл таб A[1:n, 1:n], рез ціл i, j)

поч ціл k, j1

¦ k:=0; i:=1

¦ пц поки i2

¦ ¦ j1:=1

¦ ¦ пц поки j1

¦ ¦ ¦ якщо A[i,j1]=1 то k:=k+1 все

¦ ¦ ¦ якщо k<2 то j1:=j1+1 інакше j:=j1; j1:=n все

¦ ¦ кц

¦ ¦ i:=i+1

¦ кц

кін

алг ЗАПОВНИТИ_КОНТУР (арг ціл n,l,p, арг рез ціл таб A[1:n, 1:n])

поч ціл i, j

¦ i:=l; j:=p

¦ якщо A[i, j]=0

¦ ¦то A[i, j]:=1

¦ ¦ i:=i -1; Заповнити_Контур(n, i, j, A); i:=i+1

¦ ¦ j:=j -1; Заповнити_Контур(n, i, j, A); j:=j+1

¦ ¦ i:=i+1; Заповнити_Контур(n, i, j, A); i:=i -1

¦ ¦ j:=j+1; Заповнити_Контур(n, i, j, A); j:=j -1

¦ все

кін

Для логічного завершення розгляду задачі 4 пропонуємо програму її розв’язання мовою Turbo Pascal:

program Fill_Contour;

type bin = array[1..10, 1..10] of 0..1;

var A : bin; N, x, y : byte;

procedure Inp;{-----------------------------------------------}

var i, j : integer;

begin

assign(input, 'Mas.dat'); reset(input);

N:=1;

while not EoLn do begin

read(A[1,N]); inc(N) end;

dec(N);

for i:=2 to N do

for j:=1 to N do

read(input, A[i,j]);

close(input);

end;{-------------------------------------------------------------}

procedure Outp;

var i, j : integer;

begin

assign(output, 'Mas.res'); rewrite(output);

for i:=1 to N do begin

for j:=1 to N do

write(output, A[i,j], ' ');

writeln(output) end;

close(output);

end;{-------------------------------------------------------------}

procedure In_Cont(A : bin; N : byte; var k,l : byte);

var i, j : integer;

begin

for i:=1 to N do

for j:=1 to N do

if A[i,j] = 1 then begin

k:=i+1; l:=j+1; i:=N; j:=N end;

end;{--------------------------------------------------------------}

procedure Fill_Cont(N, k, l : byte; var A : bin);

var i, j : integer;

begin

i:=k; j:=l;

if A[i,j] = 0 then begin

A[i,j]:=1;

i:=i-1; Fill_Cont(N, i, j, A); i:=i+1;

j:=j+1; Fill_Cont(N, i, j, A); j:=j-1;

i:=i+1; Fill_Cont(N, i, j, A); i:=i-1;

j:=j-1; Fill_Cont(N, i, j, A); j:=j+1 end;

end;{--------------------------------------------------------}

begin

Inp;

In_Cont(A, N, x, y);

Fill_Cont(N, x, y, A);

Outp;

end.

Програма Fill_Contour зчитує вхідні дані з файлу Mas.dat, зразок якого наведено нижче, а виводить результуючий масив, що відображає заповнений контур у вихідний файл Mas.res.

Зразок вхідного файлу Mas.dat: 0 0 0 0 1 1 1 0 0 0

0 1 1 1 1 0 1 0 0 0

0 1 0 0 0 0 1 1 1 0

0 1 1 1 0 0 0 0 1 0

0 0 0 1 1 0 0 0 1 0

0 0 0 0 1 0 0 1 1 0

0 0 0 0 1 0 0 1 0 0

1 1 1 1 1 0 1 1 0 0

1 0 0 0 0 0 1 0 0 0

1 1 1 1 1 1 1 0 0 0


Оцінка тестів до задачі Robot

robot.dat

1

2

3

4

5

robot.sol

1

3

5

10

11




Похожие:

Вказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики iconКвнз «Харківська академія неперервної освіти» рекомендації щодо проведення ІІ етапу Всеукраїнської учнівської олімпіади з інформатики у 2012/2013 навчальному році
Аналіз виконання завдань учасниками ІІІ (обласного) етапу Всеукраїнської учнівської олімпіади з інформатики 2011/2012 н р
Вказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики iconКвнз «Харківська академія неперервної освіти» Рекомендації щодо підготовки та проведення ІІ етапу всеукраїнської учнівської олімпіади з історії у 2012/2013 н р
Аналіз виконання завдань учасниками ІІІ (обласного) етапу Всеукраїнської учнівської олімпіади з історії у 2011/2012 н р
Вказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики iconКвнз «Харківська академія неперервної освіти» Рекомендації щодо проведення ІІ етапу Всеукраїнської учнівської олімпіади з біології у 2012/2013 навчальному році
Аналіз виконання завдань учасниками ІІІ (обласного) етапу Всеукраїнської учнівської олімпіади з біології у 2011/2012 н р
Вказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики iconКвнз «Харківська академія неперервної освіти» Рекомендації щодо проведення ІІ етапу Всеукраїнської учнівської олімпіади з економіки у 2012/2013 навчальному році
Аналіз виконання завдань учасниками ІІІ (обласного) етапу Всеукраїнської учнівської олімпіади з економіки у 2011/2012 н р
Вказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики iconКвнз «Харківська академія неперервної освіти» Рекомендації щодо проведення ІІ етапу Всеукраїнської учнівської олімпіади з екології у 2012/2013 навчальному році
Аналіз виконання завдань учасниками ІІІ (обласного) етапу Всеукраїнської учнівської олімпіади з екології у 2011/2012 н р
Вказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики iconКвнз «Харківська академія неперервної освіти» рекомендації щодо проведення ІІ етапу Всеукраїнської учнівської олімпіади з астрономії у 2012/2013 навчальному році
Аналіз виконання завдань учасниками ІІІ (обласного) етапу Всеукраїнської учнівської олімпіади з астрономії у 2011/2012 н р
Вказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики iconКвнз «Харківська академія неперервної освіти» рекомендації щодо проведення ІІ етапу всеукраїнської учнівської олімпіади з правознавства у 2012/2013 навчальному році
Аналіз виконання завдань учасниками ІІІ (обласного) етапу Всеукраїнської учнівської олімпіади з правознавства у 2011/2012 н р
Вказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики iconКвнз «Харківська академія неперервної освіти» рекомендації щодо проведення ІІ етапу Всеукраїнської учнівської олімпіади з фізики у 2012/2013 навчальному році
Аналіз виконання завдань учасниками ІІІ (обласного) етапу Всеукраїнської учнівської олімпіади з фізики у 2011/2012 н р
Вказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики iconКвнз «Харківська академія неперервної освіти» рекомендації щодо проведення ІІ етапу Всеукраїнської учнівської олімпіади з інформаційних технологій у 2012/2013 навчальному році
Аналіз виконання завдань учасниками ІІІ (обласного) етапу Всеукраїнської учнівської олімпіади з інформаційних технологій у 2011/2012...
Вказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики iconКвнз «Харківська академія неперервної освіти» рекомендації щодо проведення ІІ етапу всеукраїнської учнівської олімпіади з іноземних мов у 2012/2013 навчальному році
Аналіз виконання завдань учасниками ІІІ (обласного) етапу Всеукраїнської учнівської олімпіади з іноземних мов у 2011/2012 н р
Вказівки щодо розв’язування завдань ІІ етапу Всеукраїнської учнівської олімпіади з інформатики iconКвнз «Харківська академія неперервної освіти» Рекомендації щодо організації та проведення ІІ етапу Всеукраїнської учнівської олімпіади з української мови та літератури у 2012/2013 навчальному році
Аналіз виконання завдань учасниками ІІІ (обласного) етапу Всеукраїнської учнівської олімпіади з української мови та літератури
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©cl.rushkolnik.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы