2017-11-30
1296
В некотором городе К-ске имеется свояподземная дорога. Администрация города решила построить новую кольцевую линию. "Центром" этого кольца должна стать одна из станций, при этом "радиус" такого кольца - минимальное кол-во станций, которое надо проехать, чтобы достичь кольцевой линии. То есть если радиус равен R - то кольцевая линия должна строиться на тех станциях, до которых можно добраться как минимум через R станций. Кольцо должно иметь как минимум две станции. Программа должна вывести все станции, через которые надо провести новую линию, или 0, если кольцо нельзяпостроить.
Формат входных данных
Первая строка содержит число N - количество станций метро (1<=N<=150) и число K. В следующих K строках содержится информация, описывающая схему. Сначала в строке идёт D - номер станции, затем число M, а далее - M чисел, которые показывают, с какими станциями соединена станция D.
В предпоследней строке - станция, которая будет "центром" станции, а в последней – радиус
кольца.
|
|
|
Формат выходных данных
На экран вывести номера искомых станций (в любом порядке). Если кольцо нельзя построить -
вывести 0.
Пример:
| input.txt | output.txt |
| 9 5 3 3 1 4 6 2 2 1 4 7 2 1 9 5 3 1 8 6 4 2 8 9 | 2 3 5 7 |
Графическоепредставлениепримера:
Решение: при помощи поиска в ширину (BFS) на k-ой итерации цикла мы будем находить все станции, до которых можно добраться как минимум через k станций. Сделав ограничение по R и записывая "уровень" каждой станции, мы определим все такие станции.
Код программы:
const MaxN = 100;
type Matrix = array [1..MaxN,1..MaxN] of boolean; //типматрицысмежности. M[i,j] = true, если станции i и j соединены.
Var
A: Matrix;
i, j, N, k, aa, bb, S, R, c: integer;
procedure BFS(A: Matrix; N, V, R: integer); //обход в ширину (V - корневаявершина)
var i, ps, pe: integer;
visited: array [1..MaxN] of boolean; //массивпосещённостивершинq: array [1..MaxN] of integer; //"очередь" вершин
ql: array [1..MaxN] of integer; //и ихуровней.
begin //в качестве списка очередных вершин будем использовать структуру "очередь"
ps:= 1; //начало очереди
pe:= 1; //конец очереди
q[pe]:= v; //в очередь помещается исходная вершина. На каждом шаге в очередь будем заносить всех преемников данной вершины (назовём их 1-го уровня, т.е. до которых можно дойти напрямую). Затем просматриваем в очереди занесённые ранее вершины 1-го уровня и добавляем в конец очереди вершины 2-го уровня и так далее до опустошенияочереди.
visited[v]:= TRUE; //вершина V посещена
ql[ps]:= 0; //сама вершина - нулевой уровень
while (ps<= pe) and (ql[ps] <R) do //пока очередь не пуста или не достигли необходимого уровня R
Begin
for i:= 1 to n do if (A[v, i]) and (not visited[i]) then
//перебираем все связные с V вершины
Begin
inc(pe); //и добавляем в очередь q[pe]:= i;
|
|
|
ql[pe]:= ql[ps] + 1; //отмечаем новый уровень преемника.
visited[i]:= true; //отмечаем вершину I пройденной
end;
inc(ps); //переходим к следующей вершине в очереди v:= q[ps]; //и делаем её корневой
end;
while (ql[ps] = R) and (ps<= pe) do //после работы цикла в очереди останутся только вершины, имеющие уровень R и более.
Begin
write(q[ps],' '); inc(ps);
end; end;
BEGIN
assign(input,'input.txt');
reset(input);
readln(input, N,c);
for i:=1 to c do begin
read(input, aa, k);
for j:=1 to k do begin
read(input, bb); A[aa, bb]:=true;
A[bb, aa]:= true;
end; readln(input);
end;
readln(input, S); readln(input, R); close(input); BFS(A, N, S, R);
END.
Задача1
Для заданной строки символов проверить, является ли она симметричной или нет. (Симметричной считается строка, которая одинаково читается слева направо и справа налево).
Проще всего в этой задаче определить длину строки n, организовать цикл по номеру символа в строке и сравнивать попарно первый символ с последним, второй - с предпоследним и т.д. Если хотя бы одна пара различна, то строка не симметричная. Так как просматривается сразу пара символов, то в цикле будет m = n div 2 повторений. Для запоминания результата просмотра введем переменную k (k будет равна 0, если строка симметрична и 1 иначе).
Программа, решающая эту задачу, будет иметь вид:
var s:string;
i,k,n,m:integer;
begin
readln(s);
n:=length(s);
k:=0;
m:=n div 2;
for i:=1 to m do
if s[i]<>s[n-i+1] then k:=1;
if k=0 then writeln('Строка симметрична')
else writeln('Строка несимметрична');
end.
Задача 2
Для заданной строки символов вычислить произведение входящих в эту строку целых чисел (без учета их знаков). Например, для строки "kjjjkkj 2. 5 jkjn,,,hfd 45 jgfvjlkfdii 10, 2 hfhg" произведение 2*5*45*10*2=9000.
Пусть s - строка. Обозначим длину строки - l. Организуем цикл, в котором будем проверять, является ли очередной символ цифрой, если да, то организуем новый цикл, в котором будем формировать строку sn, состоящую из цифр (очередное целое число). Потом преобразуем sn в число и вычислим произведение. Программа на Паскале, реализующая данный алгоритм, будет иметь следующий вид (переменная p в этой программе используется для накапливания значения произведения, переменная kod - для хранения кода результата преобразования строки в число):
var sn,s:string;
l,k,kod:integer;
v,p:real;
begin
writeln('Введите строку');
readln(s);
l:=length(s);
p:=1; k:=1;
repeat
sn:='';
while (s[k]>='0')and(s[k]<='9')and(k<=l) do
begin
sn:=sn+s[k];
k:=k+1;
end;
if sn<>'' then
begin
val(sn,v,kod);
p:=p*v;
end;
k:=k+1;
until k>l;
writeln(' p=',p);
end.
Задача 3
Задана строка символов, содержащая два или более слов, разделенных пробелами. Написать программу, меняющую местами все четные и нечетные слова в строке, предполагая, что за один раз можно менять местами не более двух символов.
Решение
Имеется несколько путей решения этой задачи. Для упрощения предположим, что строка не начинается и не заканчивается пробелом и что между словами в строке стоит ровно по одному пробелу. Пусть известна пара слов, которую необходимо переставить, и - номера первой и последней букв в первом слове, и - номера первой и последней букв во втором слове. Рассмотрим способ, в котором для перестановки слов будем использовать следующий алгоритм:
Запишем буквы первого слова в обратном порядке (поменяв первую с последней, вторую с предпоследней и т.д.).
Например, из строки 
получим dcba efghi.
Потом аналогичным образом переставим буквы второго слова:
из строки 
получим dcba ihgfe.
Для получения окончательного результата необходимо записать буквы полученного словосочетания в обратном порядке:
Из строки 
получим efghi abcd (что и требовалось получить).
Таким образом, для перестановки двух слов достаточно написать подпрограмму, которая меняет в заданной строке порядок букв на противоположный (инвертирует строку), и вызвать эту подпрограмму для первого слова, второго слова и всего словосочетания.
Обозначим invert(k,l) - процедуру, которая записывает в заданной строке s символы с k-того по l-й в обратном порядке, тогда программа, решающая задачу, будет иметь вид:
|
|
|
var s:string;
i,n,m1,m2,l1,l2:byte;
procedure invert(k,l:byte);
var i:byte;
ch:char;
begin
for i:=k to ((l+k) div 2) do
begin
ch:=s[i];
s[i]:=s[l+k-i];
s[l+k-i]:=ch;
end;
end;
begin
writeln('Введите строку'); readln(s);
i:=0; n:=0;
m1:=1;m2:=1;l1:=1;l2:=1;
while i<length(s) do
begin
i:=i+1;
if (s[i]=' ')or(i=length(s)) then
begin
n:=n+1;
if n=1 then
begin
m2:=i-1;
l1:=i+1
end
else
begin
n:=0;
if i=length(s) then l2:=i else l2:=i-1;
invert(m1,m2);invert(l1,l2);invert(m1,l2);
m1:=i+1
end
end
end;
writeln(s)
end.
Лифт
Ограничения: время – 200мc, память - 64МБ
Петру необходимо попасть с этажа A на этаж B. Для вызова лифта на всех этажах офисного здания, кроме первого и последнего, есть две кнопки — для перемещения вниз и перемещения вверх. В тот момент, когда Петр нажал нужную кнопку вызова, лифт находился на этаже C и вез одного пассажира на этаж D. Если лифт проезжает мимо этажа, на котором нажата кнопка вызова, и лифт движется в подходящем направлении, то лифт останавливается, чтобы посадить дополнительного пассажира. Лифт перемещается между соседними этажами за одну единицу времени, также одну единицу времени занимает остановка лифта на этаже для высадки или посадки пассажиров.
Напишите программу, вычисляющую, через сколько времени Петр доберется до этажа B, при условии, что никто больше не будет вызвать лифт.
Первая строка ввода содержит четыре целых числа A, B, C и D, разделенных одним пробелом (1 ≤ A, B, C, D ≤20, A≠B, C≠D, A≠C).
Вывести одно целое число — количество единиц времени от момента вызова лифта до момента, когда Петр выйдет из лифта на этаже B.
Пример ввода 1 Пример вывода 1
3 9 2 5 10
Пример ввода 2 Пример вывода 2
3 9 5 2 13
Пояснение к примеру 1
Лифт за 1 единицу времени доедет до 3-го этажа, остановится на 1 единицу времени, чтобы Петр сел в лифт, затем через 2 единицы времени доедет до 5-го этажа и остановится на 1 единицу времени для высадки предыдущего пассажира, через 4 единицы времени лифт довезет Петра до 9-го этажа, и через 1 единицу времени Петр выйдет из лифта.
Решение
Нужно рассмотреть, движется ли лифт в том направлении, куда нужно Петру, будет ли он или пассажир лифта сходить на промежуточном этаже, и вывести формулы для этих вариантов.
|
|
|
Существует 4 варианта:
1) пассажир едет на этаж, где находится Петр;
2) Петр едет в том же направлении, что и лифт, и лифт может посадить его по пути, Петр выходит раньше или одновременно с пассажиром лифта;
3) тоже что и 2, но пассажир выходит раньше Петра;
4) лифт сначала отвозит пассажира, затем отвозит Петра.
Пример реализации:
uses math;
var a,b,c,d:integer;
begin
read(a,b,c,d);
if d=a then
writeln(abs(c-d)+1+abs(a-b)+1)
else if not((a<b)xor(c<d)) and (a>=min(c,d)) and (a<=max(c,d)) then
begin
if (b>=min(c,d)) and (b<=max(c,d)) then
writeln(abs(c-a)+1+abs(a-b)+1)
else
writeln(abs(c-a)+1+abs(a-d)+1+abs(d-b)+1);
end
else
writeln(abs(c-d)+1+abs(d-a)+1+abs(a-b)+1);
end.
Задача
Для любого целого числа N>7 найти все такие пары целых чисел x и y, что 3x+5y=N.
Разделим N нацело на 5 и получим k - максимальное значение для y (т.е. 0<=y<=k). Организуем цикл по переменной y, и будем рассматривать значения разности N-5y. Если это число делится нацело на 3, то полученное частное и есть соответствующее значение x.
Решение
var x,y,n,k:integer;
begin
writeln('Введите N');
readln(n);
k:=n div 5;
for y:=0 to k do
if (N-5*y) mod 3=0 then
begin
x:=(N-5*y) div 3;
writeln('x=',x,' y=',y);
end;
end.
Задача REBUS
Составить программу REBUS, которая определяет все 4-значные числа на интервале [M, N], удовлетворяющие условиям:
a) abcd - 4-значное число;
b) a, b, c, d - разные цифры;
c) ad - cd = a + b + c + d;
и подсчитывает общее количество этих чисел.
Во входном файле REBUS.DAT в 1-й и 2-й строчках находятся два числа M и N. В файле REBUS.SOL выводятся числа, удовлетворяющие условиям а)-с), и их количество.
| файл REBUS.DAT | файл REBUS.SOL |
Решение
program REBUS;
var a,b,c,d,m,n,k,i:integer; f:text;
begin
assign (f,'rebus.dat');
reset(f);
readln(f,m,n);
close(f);
assign(f,'rebus.sol');
rewrite(f);
for i:=m to n do
begin
a:=i div 1000;
b:=i mod 1000 div 100;
c:=i mod 100 div 10;
d:=i mod 10;
if (a <> b) and (a <> c) and (a <> d) and (b <> c) and (b <> d) and (c <> d) and (a*d-c*d=a+b+c+d) then
begin
k:=k+1;
append(f);
writeln(f,i);
end;
end;
append(f);
writeln(f,k);
close(f)
end.
Задача “Эчпочмаки”
С приближением холодов любимая крыса Василия Федоровича решила готовить запасы на зиму. На ее радость, Василий Федорович неожиданно решил продемонстрировать свое кулинарное мастерство и приготовил N эчпочмаков, оставив их на некоторое время без присмотра.
В системе жизненных ценностей крысы эчпочмак определяется как треугольник, заданный длинами своих сторон (ввиду отсутствия кулинарного мастерства у Василия Федоровича эчпочмаки получались в виде произвольных невырожденных треугольников). Основное качество эчпочмака по логике крысы — это его площадь (чем больше площадь, тем более ценен эчпочмак).
Крыса была бы рада утащить себе в гнездо, свитое в полости дивана, самый ценный эчпочмак целиком, но прогрызенная ею щель имеет ограниченные размеры, и туда могут пролезть не все эчпочмаки. Щель задается своей шириной D (вещественное число) в сантиметрах. Эчпочмак может быть ориентирован произвольно в плоскости отверстия, и если хотя бы в одном положении он проходит в щель, то он считается подходящим.
Необходимо найти номер наиболее ценного эчпочмака, который проходит в отверстие.
