Задача 3 Цепочка слов

Имеется словарь из слов русского языка, набранных заглавными буквами. Метаграммой называется слово, которое получается заменой одной из букв данного слова на любую другую букву. Будем говорить, что одно слово преобразуется в другое, если существует такая цепочка слов из словаря, в которой первое совпадает с данным словом, последнее — с требуемым, а каждое следующее слово является метаграммой предыдущего. Например, слово ВОЛК преобразуется в слово КОЗА с помощью цепочки метаграмм:

ВОЛК   ПОЛК   ПОЛА   ПОЗА   КОЗА.

(Конечно, при условии, что все эти слова имеются в словаре.)

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

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

В первой строке входного файла Input.txt записано исходное слово. Во второй строке — слово, которое требуется получить. В каждой из последующих строк содержится по одному слову словаря. Длина слова не менее 1 и не более 20 символов. Словарь содержит не более 1 000 слов.

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

Выходной файл Output.txt содержит число 0, если первое слово нельзя преобразовать во второе с помощью цепочки метаграмм. Если требуемое преобразование возможно, выводится полученная цепочка слов, начиная с данного и заканчивая требуемым словом. Каждое слово цепочки записывается в отдельной строке.

Пример

Input.txt	Output.txt
VAL GOL MUXA VAL MUKA VOL RUKA GOL	VAL VOL GOL

program cepochka;

const nmax=1000;

var d,k,n,i,kol:integer;

a,b:array[1..nmax] of string[20]; ёмассив а – словарь, массив b – результирующая цепочка

used:array[1..nmax] of boolean; признак того, что слово использовано

s1,s2,s:string[20]; s1 – данное слово

procedure init; s2 – конечное слово

begin s – переменная для чтения слов из файла

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

readln(s1);

readln(s2);

d:=length(s1);

if d<>length(s2) then

begin write(0);halt end; если данные слова разной длины

n:=2; то выводим 0 и заканчиваем .

while not eof do читаем слова из файла и убираем лишние

begin

readln(s);

if (length(s)=d)and(s<>s1)and(s<>s2)

then

begin

a[n]:=s; помещаем слова в массив

inc(n); считаем слова

end;

end;

a[1]:=s1;a[n]:=s2; данное слово будет первым, конечное последним

b[1]:=s1; данное слово помещаем в результирующий

массив

fillchar(used,sizeof(used),false);

log[1]:=true; отмечаем данное слово как использованное

kol:=1; считаем его

close(input);

end;

function prov(x,y:string):boolean; функция проверки двух слов на метаграмму

var i,p:integer;

begin

p:=0;

prov:=false;

for i:=1 to d do

begin

if p>1 then exit;

if x[i]<>y[i] then inc(p);

end;

if p=1 then prov:=true; если не совпадает только одна буква то метаграмма

end;

procedure out; вывод результата

begin

for i:=1 to kol do writeln(b[i]);

close(output);

end;

procedure rec(k:integer); рекурсивная процедура

var i:integer;

begin

if b[k]=s2 если дошли до конечного слова, то выводим

then begin out;halt(0) end результат и заканчиваем

else

for i:=1 to n do перебираем все слова из словаря

if (prov(a[i],b[k]))and(not used[i]) находим метаграмму

then

begin

inc(kol); считаем найденное слово

b[k+1]:=a[i];used[i]:=true; заносим слово в массив b и отмечаем

как использованное

rec(k+1); рекурсивно вызываем процедуру rec

b[k+1]:=''; делаем откат назад, убирая слово из

массива b

end;

end;

begin

init;

rec(1);

out;

end.

переборзадачи

Задача 4 Полоска домино

Есть несколько косточек домино. Их надо выложить в полоску так, чтобы на руках осталось наибольшее количество очков. Получить это количество и последовательность выложенных домино.

Входные данные

В первой строке натуральное число N (1<=N<=30)

В последующих N строках по два натуральных числа – косточки домино

Выходные данные

В первой строке наибольшее количество очков.

В следующих строках по два числа –значения выбранных доминошек.

Задача решается перебором с возвратом.

type domino=record

p1,p2:integer;

end;

const maxn=36;

var

n:integer;

a:array[1..maxn] of domino;

used:array[1..maxn] of boolean;

ans:array[1..maxn] of boolean; массив,отмечающий доминошки,

дающие лучший результат

sum:longint;

res,now:longint;

function eq(p1,p2:integer):boolean; определяет есть ли еще

доминошки, которые можно поставить

var p:boolean;

i:integer;

begin

p:=false;

for i:=1 to n do

if not used[i] then

if (a[i].p1=p1)or(a[i].p1=p2)or(a[i].p2=p1)or(a[i].p2=p2)

then p:=true;

eq:=p;

end;

procedure rec(p1,p2:integer);

var i:integer;

begin

if sum-now<res then exit; если на руках осталось меньше лучшего

результата, то выход из процедуры

if not eq(p1,p2) then

begin

for i:=1 to n do ans[i]:=used[i];

res:=sum-now;

end;

for i:=1 to n do пробегаем ряд доминошек

if not used[i] then если не использовали

if (a[i].p1=p1)or(a[i].p1=p2)or

(a[i].p2=p1)or(a[i].p2=p2) и если ее можно поставить

Then

begin

used[i]:=true; отмечаем как использованную

now:=a[i].p1+a[i].p2+now; прибавляем ее очки

if a[i].p1=p1 then rec(a[i].p2,p2) и продолжаем рекурсию

else

if a[i].p1=p2 then rec(p1,a[i].p2) с новыми значениями p1 и p2

else

if a[i].p2=p1 then rec(a[i].p1,p2)

else

if a[i].p2=p2 then rec(p1,a[i].p1);

now:=now-a[i].p1-a[i].p2; возвращаем доминошку обратно,

(откат назад)

used[i]:=false;

end;

end;

procedure init;

var i:integer;

begin

sum:=0;res:=0;

assign(input,'input.txt');

reset(input);

read(n);

for i:=1 to n do

begin

read(a[i].p1,a[i].p2);

sum:=a[i].p1+a[i].p2+sum; находим сумму очков всех доминошек

end;

close(input);

end;

procedure solve;

var i:integer;

begin

for i:=1 to n do делаем начальной последовательно все

доминошки

begin

now:=a[i].p1+a[i].p2;

fillchar(used,sizeof(used),false); очищаем массив used

used[i]:=true; кладем первую доминошку

rec(a[i].p1,a[i].p2); запускаем рекурсию

end;

end;

procedure out; выводим результат

var i:integer;

begin

assign(output,'output.txt');

rewrite(output);

writeln(res);

for i:=1 to n do

if ans[i] then writeln(a[i].p1,' ',a[i].p2);

close(output);

end;

begin init; solve; out;end.

переборзадачи

Задача 5 Гангстеры N гангстеров собираются в ресторан. i-й гангстер приходит в момент времени T_i и имеет богатство P_i. Дверь ресторана имеет K + 1 степень открытости, они обозначаются целыми числами из интервала [0, K]. Степень открытости двери может изменяться на единицу в единицу времени, то есть дверь может открыться на единицу, закрыться на единицу или остаться в том же состоянии. В начальный момент времени дверь закрыта (степень открытости 0). i-й гангстер заходит в ресторан, только если дверь открыта специально для него, то есть когда степень открытости двери соответствует его полноте S_i. Если в момент, когда гангстер подходит к ресторану, степень открытости двери не соответствует его полноте, он уходит и больше не возвращается. Ресторан работает в интервале времени [0, T]. Требуется собрать гангстеров с максимальным суммарным богатством в ресторане, открывая и закрывая дверь

соответствующим образом. Ограничения: 1 <= N <= 100, 1 <= K <= 100, 1 <= T <= 30 000, 0 <= T_i <= T, 1 <= P_i <= 300, 1 <= S_i <= K, все числа целые, время 2 с. Входные данные

В первой строке файла input.txt находятся числа N, K, T, во второй - T₁, T₂, ..., T_N, в третьей - P₁, P₂, ..., P_N. в четвёртой - S₁, S₂, ..., S_N. Числа в строках

разделены пробелами.

Выходные данные

В файл output.txt вывести одно число - максимальное суммарное богатство гангстеров, попавших в ресторан. Если зайти не удалось никому, вывести 0. Примеры

Input.txt	Output.txt
4 10 20 10 16 8 16 10 11 15 1 10 7 1 8	26
2 17  100 5 0 50 33 6 1	0

const nmax=200;

var dt,h,j,n,m,i,k,t0,max:longint;

t,s,p,best:array[1..nmax] of longint;

procedure swap(var x,y:longint);

var pr:longint;

begin

pr:=x;

x:=y;

y:=pr;

end;

procedure init;

var

i,j:integer;

begin

assign(input,'gangster.in');

reset(input);

read(n,k,t0);

for i:=1 to n do

read(t[i]);

for i:=1 to n do

read(p[i]);

for i:=1 to n do

read(s[i]);

close(input);

for i:=1 to n-1 do сортируем по времени

for j:=i+1 to n do

begin

if t[i]>t[j] then

begin

swap(t[i],t[j]);

swap(p[i],p[j]);

swap(s[i],s[j]);

end;

max:=0;

end;

for i:=1 to n do если гангстер не успевает дойти,

то делаем его деньги=0

if (s[i]>t[i])or(s[i]>t0) then p[i]:=0;

end;

procedure out;

begin

assign(output,'output.txt');

rewrite(output);

write(max);

close(output);

end;

procedure solve;

begin

fillchar(best,sizeof(best),0);

for i:=1 to n do

begin

best[i]:=p[i]; временно берем лучший

результат=сумме денег

for j:=1 to i-1 do пробегаем всех предыдущих

гангстеров

if abs(s[j]-s[i])<=t[i]-t[j] then если i-й гангстер успевает

if best[j]+p[i]>best[i] then и выполняется условие, то

best[i]:=best[j]+p[i]; увеличиваем набранную сумму

end;

max:=0;

for i:=1 to n do

if max<best[i] then max:=best[i]; выбираем лучшую сумму.

end;

begin init; solve; out;end.

переборзадачи

Задача 6 Ковролин для минотавра

«Что за свинья прошла здесь - корова, что ли?»

Под дворцом царя Миноса размером NxM построен одноэтажный лабиринт размером NxMx1. Некоторые из кубов 1x1x1 в этом лабиринте пустые, а некоторые — гранитные (сквозь них ходить нельзя). Количество пустых кубов в лабиринте S. Минотавр, гуляя в этом лабиринте только по пустым кубам, может дойти от любого пустого куба до любого другого пустого.

К сожалению, минотавр очень громко топает, поэтому выбранная им жертва успевает испугаться и убежать. Для того, чтобы этого избежать, фирма «Минос, минотавр and Co» закупила ковролин, которым собирается застелить пол пустых кубов, чтобы минотавр мог подбираться к жертве бесшумно. Рулон ковролина имеет размеры 1хS.

Рабочие хотят застелить пол лабиринта, сделав как можно меньше разрезов ковролина (разрезы разрешается делать только параллельно стороне рулона, имеющей длину 1).

Напишите программу, вычисляющую это минимальное число разрезов.