Задача в неделю (стр. 5 )

Требуется написать программу, которая определит сколько монет было в сундуке в первый и во второй года, если в X-м году там оказалось ровно Y монет.

Пояснение: если в первый год положить 5 монет, а во второй год вынуть 3 монеты, то начиная с первого года в сундуке будет 5, 2, 7, 9, 16, 25, ... монет.

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

Ограничение по времени тестирования: по 3 секунды на один тест.

Формат входных данных:

Входной файл INPUT. TXT содержит числа X (3£X£20) и Y (1£Y£32767), записанные через пробел.

Формат выходных данных:

В выходной текстовый файл OUTPUT. TXT записываются через пробел количество монет в первый и второй года.

Пример файла входных данных:

6 25

Пример файла выходных данных (для приведенного выше входного файла):

5 2

Разбор задачи № E

Задача решается за два шага. Вначале обозначим количество монет в первый и второй года через a и b. Тогда в третий год будет a+b монет, в четвертый – a+2b, в пятый – 2a+3b и так далее. Легко заметить, что коэффициентами при a и b являются последовательные числа Фибоначчи. Вычислив их для x-го года, получим уравнение с двумя неизвестными a и b. Это уравнение решаем в целых числах перебором всех возможных вариантов.

 var

a, b, x, y, x1, x2, xx, i : integer;

begin

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

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

read(x, y);

x1:=0; x2:=1;

for i:=3 to x do

begin xx:=x1+x2; x1:=x2; x2:=xx end;

a:=y div x1; b:=0;

while x1*a+x2*b<>y do

begin

while x1*a+x2*b<y do b:=b+1;

if x1*a+x2*b<>y then begin a:=a-1; b:=0 end

end;

write(a,' ',b)

end.

Задача F. "Постоянная Капрекара" (20 баллов).

Возьмем четырехзначное число, в котором не все цифры одинаковы, например 6264. Расположим цифры сначала в порядке убывания - 6642; затем, переставив их в обратном порядке, получим 2466. Вычтем последнее число из 6642. На следующем шаге с полученной разностью проделаем тоже самое. Через несколько таких действий получится число, переходящее само в себя и называемое постоянной Капрекара.

Требуется написать программу, которая находит эту постоянную и количество шагов для ее получения из заданного четырехзначного числа.

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

Ограничение по времени тестирования: по 3 секунды на один тест.

Формат входных данных:

Входной файл INPUT. TXT содержит одну строку, в которой записано четырехзначное число.

Формат выходных данных:

В выходной текстовый файл OUTPUT. TXT записываются: в первой строке постоянная Капрекара, во второй – количество шагов для ее получения.

Пример файла входных данных:

1234

Пример файла выходных данных:

<постоянная Капрекара>

3

Разбор задачи № F

Для введенного числа находим его цифры и записываем в массив. Упорядочим массив по возрастанию, после чего находим число согласно условию задачи. Продолжаем до тех пор, пока числа не совпадут.

var

n, n1, c : integer;

function sled(n:integer): integer;

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

i, j, x : integer;

begin

for i:=1 to 4 do

begin

a[i]:=n mod 10;

n:=n div 10

end;

for i:=1 to 3 do

for j:=1 to 4-i do

if a[j]>a[j+1] then begin x:=a[j]; a[j]:=a[j+1]; a[j+1]:=x end;

sled:=(a[4]-a[1])*999+(a[3]-a[2])*90

end;

begin

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

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

read(n);

c:=0; n1:=sled(n);

while n<>n1 do

begin

c:=c+1;

n:=n1;

n1:=sled(n)

end;

writeln(n);

write(c)

end.

Задача G. "Шифровка" (20 баллов)

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

Например, для кодирования слова ПРОГРАММИРОВАНИЕ его записывают в прямоугольник высоты 4 следующим образом:

1 П Р И А

2 Р А Р Н

3 О М О И

4 Г М В Е

а затем, если выбрать порядок строк 3, 1, 2, 4, получают закодированное сообщение ОМОИПРИАРАРНГМВЕ.

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

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

Ограничение по времени тестирования: по 3 секунды на один тест.

Формат входных данных:

Входной файл INPUT. TXT содержит: в первой строке высоту прямоугольника (не больше 10), во второй – порядок прочтения строк (числа записаны через пробел), в третьей – закодированное сообщение, длина которого не превышает 200.

Формат выходных данных:

В выходной текстовый файл OUTPUT. TXT записывается декодированное сообщение.

Пример файла входных данных:

4

3 1 2 4

ОМОИПРИАРАРНГМВЕ

Пример файла выходных данных (для приведенного выше входного файла):

ПРОГРАММИРОВАНИЕ

Разбор задачи № G

В этой задаче необходимо было аккуратно запрограммировать работу со строками. Единственная трудность заключалась в случае неполного заполнения последнего столбца при шифровании. Как это преодолеть смотрите в программе.

 var

n, i, j, k1, k2, kk : integer;

a : array [1..10] of integer;

s : string;

t : array [1..10] of string;

begin

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

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

readln(n);

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

readln(s);

k1:=length(s) div n;

k2:=length(s)-k1*n;

for i:=1 to n do

begin

if a[i]>k2 then kk:=k1 else kk:=k1+1;

t[a[i]]:=copy(s,1,kk);

delete(s,1,kk)

end;

for i:=1 to k1 do for j:=1 to n do s:=s+t[j][i];

for j:=1 to k2 do s:=s+t[j][k1+1];

writeln(s)

end.

Задача H. "Нить Ариадны" (20 баллов)

Тезею из лабиринта Минотавра помог выйти клубок ниток. Вы можете вместо клубка использовать персональный компьютер.

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

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

Ограничение по времени тестирования: по 3 секунды на один тест.

Формат входных данных:

Входной файл INPUT. TXT содержит маршрут Тезея, который представлен строкой, состоящей из букв: N, S, W, E и длиной не более 200.

Буквы означают:

N - один "шаг" на север,

S - один "шаг" на юг,

W - один "шаг" на запад,

E - один "шаг" на восток.

Формат выходных данных:

В выходной текстовый файл OUTPUT. TXT записывается аналогично входному файлу найденный обратный путь.

Пример файла входных данных:

EENNESWSSWE

Пример файла выходных данных (для приведенного выше входного файла):

NWW

Разбор задачи № H

Представим, что движение осуществляется на квадратном клеточном поле с шагом 1 от точки (0, 0). В массиве будем хранить координаты посещенных точек (перед началом движения там всего одна нулевая точка). После каждого шага в одном из четырех направлений просмотром массива определяем: не были ли мы уже в этой точке. И если были, то удаляем из маршрута эту часть пути. Детали реализации алгоритма смотрите в программе.

var

s, t : string;

a : array [1..2,0..200] of integer;

i, j, k : integer;

begin

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

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

readln(s); t:='';

k:=0; a[1,k]:=0; a[2,k]:=0;

for i:=1 to length(s) do

begin

k:=k+1;

if s[i]='N' then begin a[1,k]:=a[1,k-1]; a[2,k]:=a[2,k-1]+1; t:=t+'S' end;

if s[i]='E' then begin a[1,k]:=a[1,k-1]+1; a[2,k]:=a[2,k-1]; t:=t+'W' end;

if s[i]='S' then begin a[1,k]:=a[1,k-1]; a[2,k]:=a[2,k-1]-1; t:=t+'N' end;

if s[i]='W' then begin a[1,k]:=a[1,k-1]-1; a[2,k]:=a[2,k-1]; t:=t+'E' end;

j:=0;

while (a[1,j]<>a[1,k]) or (a[2,j]<>a[2,k]) do j:=j+1;

if j<k then

begin

delete(t, j+1,k-j);

k:=j

end

end;

for i:=length(t) downto 1 do write(t[i])

end.

Задача I. "Сообщения" (20 баллов)

Для надежности некоторое сообщение было передано по линии связи трижды, но каждый раз ровно один символ был принят в искаженном виде.

Требуется написать программу, которая по трем полученным сообщениям восстановит исходное сообщение, или установит, что сделать это невозможно.

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

Ограничение по времени тестирования: по 3 секунды на один тест.

Формат входных данных:

Входной файл INPUT. TXT содержит три строки с тремя полученными сообщениями, которые представлены строками длиной не более 255.

Формат выходных данных:

В выходной текстовый файл OUTPUT. TXT записывается восстановленное сообщение или «NO», если сообщение невозможно восстановить.

Пример файла входных данных:

test

texs

eext

Пример файла выходных данных (для приведенного выше входного файла):

text

Разбор задачи № I

Эта задача была на одной из ленинградских олимпиад по информатике. Далее приводится решение Антона Суханова, победителя Всесоюзных и члена жюри Всероссийских олимпиад школьников по информатике.

Выпишем эти три текста в три строки друг под другом, как это сделано в примере.

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

а) 3 искаженных колонки. В каждой из искаженных колонок находится ровно один искаженный символ, который легко восстановить, ибо два других равны.