II тур олимпиады по программированию, 2015-2016 уч. год

II Тур олимпиады по программированию, 2015-2016 уч. год

, 10 класс,

образовательное учреждение: 452558, РБ Мечетлинский район, с. Алегазово, ул. Советская, 4, МОБУ СОШ с. Алегазово. e-mail - *****@***ru

Язык Pascal, выполнено в Lazarus IDE v1.2.4 Консольное приложение.

Задание 1. Разработайте программу, которая формирует таблицу 10 на 10, заполняет ее случайными числами и сортирует по строкам.

Решение: Сортировка Шелла.

program

const N=10; M=10;

var

v: array[1..N,1..M] of integer;

d: integer;

j, i, t: integer;

k: boolean;

begin

randomize;

writeln('Do sortirovki: ');

for i := 1 to N do begin

for j := 1 to M do

begin

v[i, j] := -100 + random(201);

write(v[i, j]:4);

end;

writeln;

end; write('Posle sortirovki: ');

for i := 1 to N do begin

d := M div 2;

while(d > 0) do

begin

k := true;

while k do

begin

k := false;

j:= 1;

for j := 1 to M - d do

begin

if(v[i, j] > v[i, j + d]) then

begin

t := v[i, j];

v[i, j] := v[i, j + d];

v[i, j + d] := t;

k := true;

end;

d := d div 2;

end;

writeln;

for j:= 1 to M do

write(v[i, j]:4);

end;

writeln; readln;readln;

end.

В разделе констант задаём количество элементов массива (N-строк, M-столбцов).

В разделе объявления переменных формируем матрицу размером N x M,

d - шаг сортировки Шелла,

i, j – счётчики строки и столбца в цикле,

t –вспомогательная переменная, используемая при обмене двух элементов массива,

k –признак перестановки.

Чтобы каждый раз генерировались новые числа.

Заполнение матрицы случайными

числами из интервала [-100; 100].

Начало сортировки матрицы в цикле (построчно).

Шаг сортировки изначально равен половине длины строки исходной матрицы.

Пока (while) строка не отсортирована.

Пока (while) есть перестановки в строке.

Сравнение элементов на интервале d.

Переставляем местами элементы v[i, j] и v[i, j + d], если условие v[i, j] > v[i, j + d соблюдается.

Сокращаем шаг сортировки в 2 раза.

Выводим в цикле по j построчно отсортированную матрицу внутри цикла по i.

Результат выполнения программы:

НЕ нашли? Не то? Что вы ищете?

Задание 2

Разработайте программу, которая формирует таблицу 10 на 10, заполняет ее случайными числами и сортирует по столбцам.

Решение:

const N=10; M=10;

var

v: array[1..N,1..M] of integer;

d: integer;

j, i, t: integer;

k: boolean;

begin

randomize;

writeln('Do sortirovki: ');

for i := 1 to N do begin

for j := 1 to M do

begin

v[i, j] := -100 + random(201);

write(v[i, j]:4);

end; writeln;

end;

write('Posle sortirovki: ');

for j := 1 to M do begin

d := N div 2;

while(d > 0) do

begin

k := true;

while k do

begin

k := false;

i:= 1;

for i := 1 to N - d do

begin

if(v[i, j] > v[i + d, j]) then

begin

t := v[i, j];

v[i, j] := v[i + d, j];

v[i + d, j] := t;

k := true;

end;

d := d div 2;

end;

writeln;

for i:= 1 to N do begin

for j:= 1 to M do

write(v[i, j]:4);

writeln;

end;

readln;readln;

end.

Объявление матрицы,

описание переменных

и ввод элементов матрицы

происходит как и в 1-й задаче.

В отличие от 1-й задачи изменение происходит с этого места: меняются местами циклы по i и j. И сравниваем v[i, j] > v[i + d, j], меняя местами элементы столбца v[i, j] и v[i + d, j]. Т. о. происходит сортировка уже по столбцам методом Шелла.

Вывод новой матрицы осуществляется отдельно.

Результат выполнения программы:

Задание 3

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

Решение:

const N=10; M=10;

var

v: array[1..N,1..M] of integer;

j, i,max: integer;

begin

randomize;

writeln('Pervona4alnaja matritsa: ');

for i := 1 to N do begin

for j := 1 to M do

begin

v[i, j] := -100 + random(201);

write(v[i, j]:4);

end; writeln;

end;

writeln;

write('Massiv iz naibolshih 4etnih zna4enii kajdogo stolbtsa: '); writeln;

for j := 1 to M do begin

max:= -100;

for i := 1 to N do

begin

if (v[i, j] > max) and (v[i, j] mod 2=0) then max:= v[i, j];

end; write(max:4);

end;

readln;readln;

end.

max – наибольший элемент

Ввод элементов матрицы.

Как и в задаче 2 для работы со столбцами массива осуществляем цикл по i внутри цикла по j,

где проверяем выполнение сложного условия

(v[i, j] > max) and (v[i, j] mod 2=0).

Где условие v[i, j] > max –нахождение наибольшего элемента в столбце,

а v[i, j] mod 2=0 – проверка чётности этого элемента.

Результат выполнения программы:

Задание 4

Разработайте программу для кодирования последовательности из N символов, которая использует неравномерный минимальный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность.

Решение:

Неравномерный двоичный код - это когда символы имеют коды разной длины. Чтобы однозначно декодировать полученную последовательность достаточно выполнения условия Фано: ни одно из кодовых слов не является началом другого годового слова. Дэвид Хаффман разработал алгоритм кодирования. Следую его принципам, надо:

определить, сколько раз встречается в тексте каждая буква; часто встречающиеся буквы закодировать кодом короче, а реже встречающиеся – кодом длиннее, а длину кода определять из дерева:

Рассмотрим фразу из 10 символов и 4-х разных букв: ABAACDADBA.

Надо её закодировать минимальным кодом. Определяем, что А встречается в тексте 5 раз, В – 2 раза, С – 1 раз и D – 2 раза. Поэтому закодируем эти буквы так:

А – 0, В -10, С – 111, D – 110.

Исходный код программы.

const z=4;

q=10;

var

s, s1:string;

a, n,d, i,t:integer;

k:array[1..z] of integer;

w:array[1..z] of integer;

u:array[1..q] of string;

x:array [1..q] of integer;

e:boolean;

begin

assign(input, 'input. txt'); reset(input);

assign(output, 'output. txt'); rewrite(output);

read(s);

k[1]:=0; s1:=s;

x[1]:=1;

for i:=1 to q do begin

while Length(s1)>0 do begin

a:=Pos('A',s1);

if a<>0 then begin

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

k[1]:=k[1]+1;

Delete(s1,1,a);

end

else break;

end;

k[2]:=0; s1:=s;

while Length(s1)>0 do begin

a:=Pos('B',s1);

if a<>0 then begin

k[2]:=k[2]+1;

Delete(s1,1,a);

end

else break;

end;

k[3]:=0; s1:=s;

while Length(s1)>0 do begin

a:=Pos('C',s1);

if a<>0 then begin

k[3]:=k[3]+1;

Delete(s1,1,a);

end

else break;

end;

k[4]:=0; s1:=s;

while Length(s1)>0 do begin

a:=Pos('D',s1);

if a<>0 then begin

k[4]:=k[4]+1;

Delete(s1,1,a);

end

else break;

end;

for i:=1 to z do begin

w[i]:=k[i];

end;

d := z div 2;

while(d > 0) do

end;

begin

e := true;

while e do

begin

e := false;

i := 1;

for i := 1 to z - d do

begin

if(k[i] > k[i + d]) then

begin

t := k[i];

k[i] := k[i + d];

k[i + d] := t;

e := true;

end;

d := d div 2;

end;

for i:=1 to q do begin

u[i]:=Copy(s,1,1);

Delete(s,1,1);

end;

for i:=z downto 1 do begin

if k[i]=w[1] then 'A':='1';

case k[i] of

w[1]: 'A':='1';

w[2]: 'B':='00';

w[3]: 'C':='011';

w[4]: 'D':='010';

end;

for i:=1 to q do write(u[i]);

close(input); close(output);

end.

s-строка исходного слова

Считываем исходное слово из входного файла. Чтобы не потерять исходную строку s, вводим новую строку s1 и s1:=s.

Определяем, сколько раз в тексте встречается буква ‘А’. Для этого определяем позицию когда этот символ встречается в тексте 1 раз, фиксируем встречу в k[1]:=k[1]+1, обрезаем строку вместе с первым встреченным символом, далее опять ищем где встречается этот символ, фиксируем встречу и опять обрезаем строку и т. д.

Аналогично подсчитываем сколько раз встречаются и другие символы в строке.

Определяем, сколько раз в тексте встречается буква ‘В’.

Определяем, сколько раз в тексте встречается буква ‘С’.

Определяем, сколько раз в тексте встречается буква ‘D’.

В процедуре эту операцию выполнить не удалось, т. к. a:=Pos('D',s1) выполняет только так с конкретным символом.

Далее, сформированную матрицу k[i] сортируем методом Шелла по возрастанию.

Далее пыталась заменить символы на соответствующий код, но довести выполнение программы до конца не удалось, времени не хватило.

Результат выполнения программы:

input. txt

output. txt

ABAACDADBA

010001111100110100

так должно было получиться.

Задание 5

Разработайте программу, которая по четырехбайтовому IP-адресу узла и IP-адресу маски подсети вычисляет сетевой адрес.

Решение:

Пусть IP-адрес узла и IP-адрес маски записаны во входном файле в виде двух строк, н-р, 207.130.129.192

255.255.224.0

Математическая модель задачи.

нужно помнить, что каждая часть в IP-адресе (и в маске) – восьмибитное двоичное число, то есть десятичное число от 0 до 255 (поэтому каждую часть адреса и маски называют октетом) поскольку 255 = 111111112, то все части IP-адреса узла, для которых маска равна 255, входят в IP-адрес сети без изменений (они полностью относятся к адресу сети) поскольку 0 = 000000002, то все части IP-адреса узла, для которых маска равна 0, в IP-адресе сети заменяются нулями (они полностью относятся к адресу узла в сети) таким образом, мы почти определили адрес сети, он равен 207.130.X.0, где X придется определять дополнительно переведем в двоичную систему третьи части IP-адресов узла и маски

Адрес: 129 = 100000012

Маска: 224 = 111000002

(Т. к. в маске сначала идет цепочка единиц, а потом до конца – цепочка нулей, то это правильно. Число, где цепочка единиц начинается не с левого края (не со старшего, 8-ого бита) или внутри встречаются нули, не может быть маской. Поэтому есть всего несколько допустимых чисел для последней части маски (все предыдущие должны быть равны 255):

100000002 = 128

110000002 = 192

111000002 = 224

111100002 = 240

111110002 = 248

111111002 = 252

111111102 = 254

111111112 = 255)

выполним между этими числами поразрядную конъюнкцию – логическую операцию «И»; маска 224 = 111000002 говорит о том, что первые 3 бита соответствующего числа в IP-адресе относятся к адресу сети, а оставшиеся 5 – к адресу узла:

129 = 100000012

224 = 111000002

поэтому третья часть адреса сети – это 128 = 100000002.

таким образом, полный адрес сети – 207.130.128.0

Другой пример: IP-адрес: 10.8.248.131 Маска: 255.255.224.0

Задача отличается только тем, что не все числа трёхзначные. Но суть не изменилась и полный адрес сети – 10.8.224.0.

В третьем примере IP-адрес: 146.212.200.55 Маска: 255.255.240.0

Или IP-адрес: 217.9.142.131 Маска: 255.255.192.0

Суть и в этих случаях сохраняется.

Поэтому задача состоит:

1) в выделении из обеих литерных строк 207.130.129.192

255.255.224.0

третьего байта; совершения поразрядной конъюнкции и перевода полученного двоичного числа в десятичный аналог X; выписывании в полный адрес сети первых двух байтов из IP-адреса узла, дописывании в третий байт полученного числа X, дописывании в четвёртый байт нуля, т. е., н-р, 207.130.X.0;

ориентирами в строках 207.130.129.192

255.255.224.0

нам будут служить точки.

Перевод целого числа n0 (0..255) в 8-битный двоичный код имеет вид:

var m:array[1..8] of integer;

i, k,n0:integer;

begin

read(n0);

i:=1;

k:=128;

while k>0 do begin

m[i]:=n0 div k; write(m[i]:3);

n0:=n0 mod k;

k:=k div 2; i:=i+1;

end;

end.

н-р, 124=01111100 129=10000001 224 = 11100000

Программа решения задачи.

const a=8;

var m:array[1..a] of integer; {массив для работы в процедуре}

v:array[1..a] of integer; {для записи восьмиричного кода 3-го байта в IP-адресе узла }

t:array[1..a] of integer; {для записи восьмиричного кода 3-го байта в IP-адресе маски }

q:array[1..a] of integer; {для записи восьмиричного кода 3-го байта в IP-адресе сети }

b:array[1..a] of integer; {для записи десятичных числ из IP-адреса узла }

c:array[1..a] of integer; {для записи десятичных числ из IP-адреса маски }

i, n,d, y,sum:integer;

s1,s2,s3:string;

{процедура перевода десятичного числа в двоичный код}

procedure perevodBin(n:integer);

var k, n0:integer;

begin

i:=1;

k:=128; n0:=n;

while k>0 do begin

m[i]:=n0 div k;

n0:=n0 mod k;

k:=k div 2; i:=i+1;

end;

{основная программа}

begin

assign(input,'input. txt');reset(input);

assign(output,'output. txt');rewrite(output);

readln(s1); readln(s2); {ввод строк с IP-адресами узла и маски из входного файла}

{заполнение массива b[i] числами IP-адреса узла}

for i:=1 to 3 do begin { цикл 3 раза, т. к. символов ‘.’ в строке s1 только три}

d:=Pos('.',s1); {определение №-ра позиции символа ‘.’}

s3:= Copy(s1,1,d-1); {копирование в строку s3 содержимого строки s1, стоящего слева до первой точки }

Val(s3,y); {перевод символьной строки s3 в числовую y }

b[i]:=y; {занесение полученного числа строки s3 в числовую в массив b[i] }

Delete(s1,1,d); {удаление из строки s1 d символов слева, включая точку}

end;

{занесение в массив b[i] четвёртого числа из строки s1}

d:=Pos(' ',s1); {определение, есть ли пробел в конце строки s1}

if d<>0 then s3:= Copy(s1,1,d-1) else s3:=s1; {исключение пробела, если он есть, из конца строки s1 и копирование содержимого строки s1в строку s3}

Val(s3,y); {перевод символьной строки s3 в числовую y }

b[4]:=y;

{заполнение массива с[i] числами IP-адреса маски производится аналогично}

for i:=1 to 3 do begin

d:=Pos('.',s2);

s3:= Copy(s2,1,d-1); Val(s3,y);

c[i]:=y;

Delete(s2,1,d);

end;

d:=Pos(' ',s2); if d<>0 then s3:= Copy(s2,1,d-1) else s3:=s2;

Val(s3,y);

c[4]:=y;

{передаём в процедуру третий байт IP-адреса узла и получаем его двоичный код}

perevodBin(b[3]);

for i:=1 to a do v[i]:=m[i];

{передаём в процедуру третий байт IP-адреса маски и получаем его двоичный код}

perevodBin(c[3]);

for i:=1 to a do t[i]:=m[i];

{выполним между этими двоичными числами поразрядную конъюнкцию }

for i:=1 to a do

if (v[i]=1) and (t[i]=1) then q[i]:=1 else q[i]:=0;

{выполним перевод полученного двоичного числа в десятичный код }

sum:=0; d:=1;

for i:=a downto 1 do begin

sum:=sum+q[i]*d;

d:=d*2 ;

end;

{сформируем искомый адрес сети и передадим его в выходной файл}

write(b[1],'.',b[2],'.',sum,'.',c[4]);

close(input);close(output);

end.

input. txt	output. txt
1	207.130.129.192 255.255.224.0	207.130.128.0
2	10.8.248.131 255.255.224.0	10.8.224.0
3	217.9.142.131 255.255.192.0	217.9.128.0

Для решения этой задачи можно организовать форму. Программа имеет вид:

unit Unit1;

{$mode objfpc}{$H+}

interface

uses

Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls;

type

{ TForm1 }

TForm1 = class(TForm)

Button1: TButton;

Edit1: TEdit;

Edit2: TEdit;

Edit3: TEdit;

Edit4: TEdit;

Edit5: TEdit;

Edit6: TEdit;

Edit7: TEdit;

Edit8: TEdit;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

procedure Button1Click(Sender: TObject);

private

{ private declarations }

public

{ public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.lfm}

{ TForm1 }

procedure TForm1.Button1Click(Sender: TObject);

const a=8;

var m:array[1..a] of integer; {массив для работы в процедуре}

v:array[1..a] of integer; {для записи восьмиричного кода 3-го байта в IP-адресе узла }

t:array[1..a] of integer; {для записи восьмиричного кода 3-го байта в IP-адресе маски }

q:array[1..a] of integer; {для записи восьмиричного кода 3-го байта в IP-адресе сети }

i, n,d, sum:integer;

b1,b2,b3,b4,c1,c2,c3,c4:integer;

{процедура перевода десятичного числа в двоичный код}

procedure perevodBin(n:integer);

var k, n0:integer;

begin

i:=1;

k:=128; n0:=n;

while k>0 do begin

m[i]:=n0 div k;

n0:=n0 mod k;

k:=k div 2; i:=i+1;

end;

begin

{считываем из окон данные адресов узла и маски}

b1:=StrToInt(Edit1.Text);

b2:=StrToInt(Edit2.Text);

b3:=StrToInt(Edit3.Text);

b4:=StrToInt(Edit4.Text);

c1:=StrToInt(Edit5.Text);

c2:=StrToInt(Edit6.Text);

c3:=StrToInt(Edit7.Text);

c4:=StrToInt(Edit8.Text);

{передаём в процедуру третий байт IP-адреса узла и получаем его двоичный код}

perevodBin(b3);

for i:=1 to a do v[i]:=m[i];

{передаём в процедуру третий байт IP-адреса маски и получаем его двоичный код}

perevodBin(c3);

for i:=1 to a do t[i]:=m[i];

{выполним между этими двоичными числами поразрядную конъюнкцию }

for i:=1 to a do

if (v[i]=1) and (t[i]=1) then q[i]:=1 else q[i]:=0;

{выполним перевод полученного двоичного числа в десятичный код }

sum:=0; d:=1;

for i:=a downto 1 do begin

sum:=sum+q[i]*d;

d:=d*2 ;

end;

{сформируем искомый адрес сети и передадим его в выходной файл}

Label4.Caption:=IntToStr(b1)+'.'+IntToStr(b2)+'.'+IntToStr(sum)+'.'+IntToStr(c4);

end;

end.

Задание 6

Разработайте программу для выдачи денег банкоматом по заданной клиентом сумме денег M кратной 50 рублям и наличию в банкомате X1 купюр по 50 рублей, X2 купюр по 100 рублей, X3 купюр по 1000 рублей, X4 купюр по 5000 рублей. Известно, что максимальная сумма для выдачи M не превышает 50000 рублей, минимальная сумма выдачи денег 50 рублей. После каждой выдачи денег, программа подсчитывает минимально возможные количества купюр X1, X2, X3, X4 и выдает сообщение "Банкомат временно не работает" в случае нехватки купюр для следующей выдачи денег по указанным условиям. Программа выполняет сначала учет ввода денег в банкомат для выдачи, а затем выдачу произвольных сумм клиентам банка.

Программа решения задачи имеет вид.

program Project1;

var M, x1,x2,x3,x4,a, b,c, d:integer;

begin

writeln('Vvedite kolichestvo kupur po 50 rub');

read(x1);

writeln('Vvedite kolichestvo kupur po 100 rub');

read(x2);

writeln('Vvedite kolichestvo kupur po 1000 rub');

read(x3);

writeln('Vvedite kolichestvo kupur po 5000 rub');

read(x4);

while (x1>0)or(x2>0)or(x3>0)or(x4>0) do begin

writeln('Vvedite summu: ');

read(M);

a:=M div 5000;

if x4<a then a:=x4;

M:=M-a*5000;

b:=M div 1000;

if x3<b then b:=x3;

M:=M-b*1000;

c:=M div 100;

if x2<c then c:=x2;

M:=M-c*100;

d:=M div 50;

if x1<d then writeln('Bankomat vremenno ne rabotaet')

else begin

writeln(a,' kupur po 5000 ', b,' kupur po 1000 ', c,' kupur po 100 ', d,' kupur po 50 ');

x4:=x4-a; x3:=x3-b; x2:=x2-c; x1:=x1-d;

end;

writeln('V bankomate zakonchilis dengi');

readln;readln;

end.

Загрузка в банкомат купюр.

Запрос на ввод запрашиваемой суммы.

Анализ банкоматом, есть ли возможность сформировать нужную сумму.

Сообщение клиенту, что нужную суммы выдать банкомат не может.

Выдача нужной суммы.

Сообщение, что деньги закончились, появляется только тогда, когда все купюры заканчиваются.

Пыталась составить к этой задаче форму, но что-то не додумываю до конца.

procedure TForm1.Button1Click(Sender: TObject);

var M, x1,x2,x3,x4,a, b,c, d:integer;

begin

x1:=StrToInt(Edit1.Text);

x2:=StrToInt(Edit2.Text);

x3:=StrToInt(Edit3.Text);

x4:=StrToInt(Edit4.Text);

M:=StrToInt(Edit5.Text);

while (x1>0)or(x2>0)or(x3>0)or(x4>0) do begin

a:=M div 5000;

if x4<a then a:=x4;

M:=M-a*5000;

b:=M div 1000;

if x3<b then b:=x3;

M:=M-b*1000;

c:=M div 100;

if x2<c then c:=x2;

M:=M-c*100;

d:=M div 50;

if x1<d then Label9.Caption:='Bankomat vremenno ne rabotaet'

else begin

Label9.Caption:=IntToStr(a)+' po 5000 '+IntToStr(b)+' po 1000 '+IntToStr(c)+' 100 '+IntToStr(d)+' po 50 ';

x4:=x4-a; x3:=x3-b; x2:=x2-c; x1:=x1-d;

end;

Label9.Caption:='V bankomate zakonchilis dengi';

end;

end.

Задание 7

Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте.

Исходные данные

В первой строке находится целое число N (1 ≤ N ≤ 65535). В i-й из N последующих строк записано целое число Ki — номер позиции в последовательности (1 ≤ Ki ≤ 231 − 1).

Результат

Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki.

Пример

исходные данные

результат

0 0 1 0

Программа решения задачи имеет вид.

var

v: array of integer;

a: array of integer;

k: array of integer;

i, j,N, w,m, h: integer;

begin

assign(input,'input. txt');reset(input);

assign(output,'output. txt');rewrite(output);

readln(N);SetLength(k, N-1);

for i:=0 to N-1 do

readln(k[i]);

close(input);

SetLength(v, N+1); m:=0;

for i:=0 to N do

m:=m+i+1;

SetLength(a, m);

v[0]:=1;

a[0]:=v[0]; j:=1;

for i:=1 to N do begin

v[i]:= 10*v[i-1];

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

for w:=1 to i do begin

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

end; w:=0;

end;

for i:=0 to N-1 do begin

for h:=0 to Length(a)-1 do begin

if k[i]=h then

write(a[h-1]); end; end;

close(output);

end.

В массив v помещаем последовательность возрастающих степеней десятки.

В массив a помещаем разбитые на цифры возрастающие степени десятки.

В массив k помещаем последовательность N чисел Ki, считанных из входного файла.

-Открываем входной файл и считываем из него входные данные: причём вначале считываем N,

затем устанавливаем длину динамического массива k, а уж потом считываем значения Ki из N последующих строк.

Закрываем входной файл.

Устанавливаем длину динамического массива v.

В цикле определяем длину массива a, значение которой зависит от N.

Устанавливаем длину массива a.

Задаём первый член массивов v и a, а также начальное значение счётчика для массива a.

В цикле задаём формулой степени

десятки и разбиваем их на цифры.

w:=0 - обнуляем счётчик перед

очередным входом в цикл для

записи нулей.

Во вложенном цикле проверяем условие Ki =номеру элемента массива a. При выполнении этого условия выводим цифры, находящиеся в массиве а на позиции с номером Ki.

Входной и выходной файлы.

input. txt

output. txt

0 0 1 0

Задание 8

Условие этой задачи очень простое: вам всего лишь надо определить, сколько клеток находится под боем шахматного коня, одиноко стоящего на шахматной доске. На всякий случай напомним, что конь ходит буквой «Г» — на две клетки по горизонтали или вертикали в любом направлении, и потом на одну клетку в направлении, перпендикулярном первоначальному.

Исходные данные

В первой строке находится единственное число N, 1 ≤ N ≤ 100 — количество тестов. В каждой из последующих Nстрок содержится очередной тест: два символа (маленькая латинская буква от 'a' до 'h' и цифра от 1 до 8) — стандартное шахматное обозначение клетки, на которой стоит конь. При этом буква обозначает вертикаль, а цифра — горизонталь.

Результат

Выведите N строк: в каждой из них должно находиться единственное число — количество клеток шахматной доски, находящихся под боем коня.

Пример

исходные данные

результат

Решение: 1)

Если конь (красная звёздочка) стоит где-то в центральной области шахматного поля 8х8, то под боем у него находится 8 клеток (синие звёздочки). В этом положении коню не трудно определять нужные клетки.

В этом случае объявление массива имеет вид:

const n=8;

var p:array[1..n,1..n] of integer;

Если же конь будет стоять вблизи границы поля (у самой «стены» или на расстоянии одной клетки от «стены»), то при определении нужных клеток, которые могут находиться и за пределами «стены», конь будет разбиваться о «стену». А, значит, программа будет выдавать ошибку.

Чтобы избежать разбивания коня о «стены» надо поле на две клетки расширить во все стороны, размер поля будет 12х12.

Тогда объявление массива имеет вид:

const n=8;

var p:array[-1..n+2,-1..n+2] of integer;

Но в этом случае надо работать только с внутренним полем 8х8, т. е. проверять нужные клетки только в пределах внутреннего поля. «Разбиваться» конь уже не будет, но нужные клетки за пределами внутреннего поля учитывать тоже не будет.

2) Заполняем внутреннее поле нулями (эту процедуру надо выполнять перед каждым новым тестом, поэтому этот цикл вложенный):

for r:=1 to n do

for v:=1 to n do p[r, v]:=0;

Внешний цикл будет исполняться m раз, т. е. по числу тестов

for i:=1 to m do begin

………..

end;

Если клетку, в которой стоит конь, обозначить координатами (x, y), то не трудно подсчитать координаты нужных клеток и в этих клетках заменить нули на единицы:

p[x+1,y-2]:=1;

p[x+2,y-1]:=1;

p[x+2,y+1]:=1;

p[x+1,y+2]:=1;

p[x-1,y+2]:=1;

p[x-2,y+1]:=1;

p[x-1,y-2]:=1;

p[x-2,y-1]:=1;

Затем можно легко подсчитать в цикле число этих единиц:

for r:=1 to n do begin

for v:=1 to n do

if p[r, v]=1 then inc(k);

end; writeln(k);

3) Т. к. из входного файла мы считываем координаты клеток, где может находиться конь, а таких клеток 64, то стринговый массив s зададим сразу размером 64. Считывая элементы этого массива в цикле

for i:=1 to m do begin readln(s[i]);

мы разделяем элементы s[i] на отдельные символы в стринговых переменных u и t:

u:=Copy(s[i],1,1);t:=Copy(s[i],2,1);

Затем величину t переводим в числовую y: Val(t, y).

Далее в операторе выбора case в переменной х заменяем буквы a, b,c, d,e, f,g, h на соответствующие их местам цифры:

case u of

'a': x:=1;

'b': x:=2;

'c': x:=3;

'd': x:=4;

'e': x:=5;

'f': x:=6;

'g': x:=7;

'h': x:=8

end;

Итак, программа данной задачи имеет вид:

const n=8;

var

p:array[-1..n+2,-1..n+2] of integer;

s:array[1..64] of string;

i, j,r, v:integer;

k, x,y, m:integer;

u, t:string;

begin

assign(input,'input. txt');reset(input);

assign(output,'output. txt');rewrite(output);

readln(m);

for i:=1 to m do begin

for r:=1 to n do

for v:=1 to n do p[r, v]:=0;

readln(s[i]);

u:=Copy(s[i],1,1);t:=Copy(s[i],2,1); Val(t, y);

case u of

'a': x:=1;

'b': x:=2;

'c': x:=3;

'd': x:=4;

'e': x:=5;

'f': x:=6;

'g': x:=7;

'h': x:=8

end;

p[x+1,y-2]:=1;

p[x+2,y-1]:=1;

p[x+2,y+1]:=1;

p[x+1,y+2]:=1;

p[x-1,y+2]:=1;

p[x-2,y+1]:=1;

p[x-1,y-2]:=1;

p[x-2,y-1]:=1;

k:=0;

for r:=1 to n do begin

for v:=1 to n do

if p[r, v]=1 then inc(k);

end; writeln(k);

end;

close(input); close(output);

end.

i, j,r, v - счётчики циклов

x, y - координаты коня

k - подсчитывает число клеток под боем коня

m - число тестов

Ввод числа тестов из входного файла.

Начало и конец внешнего цикла выделены жирным шрифтом.

Обнуление

шахматного поля

производится каждый раз для нового теста.

Подсчёт и вывод в выходной файл

количества клеток под боем коня.

Результат выполнения программы:

input. txt

output. txt

II тур олимпиады по программированию, 2015-2016 уч. год