Технический форум
Вернуться   Технический форум > Программирование > Форум программистов > Помощь студентам


Ответ
 
Опции темы Опции просмотра
Старый 13.11.2012, 08:57   #1 (permalink)
gazon
Member
 
Регистрация: 21.11.2011
Сообщений: 56
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию Домой на электричках

Помогите пожалуйста составить комментарии к коду

Одна из команд-участниц олимпиады решила вернуться домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут).
Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.
Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, когда ребята могут оказаться дома.

Ввод
Во входном файле записаны сначала числа N (2  N  100) и E (2  E  N). Затем записано число M (0  M  100), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа Ki (2  Ki  N) — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.

Вывод
В выходной файл выведите одно число — минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите –1.


Решение задачи
Эту задачу можно решать многими способами (как и любую другую), но я буду использовать далеко не самый эффективный, но укладывающийся в ограничения для этой задачи.
Заведем одномерный массив для станций - для каждой станции будем хранить текущее минимальное время, за которое на нее можно добраться. Сначала заполним все бесконечностью. Также заведем массив, в котором будем хранить информацию о поездах - во сколько на какую станцию прибывает, а также, в каком направлении идет.
Для определения направления достаточно сравнить две любые станции на пути электрички - если номера возрастают, то поезд идет от города, иначе - к городу.
Теперь начинается медленное и неэффективное решение:
Запустим цикл (i) от 1 до количества станций. Затем идем по всем станциям (j), начиная с первой. Затем идем по всем поездам и, если время отправления поезда с этой станции больше либо равно текущему времени, за которое можно добраться до этой станции, считаем что на этот поезд можно сесть - прогоняем цикл по всем станциям, на которых останавливается этот поезд, и, если текущее время на станции больше, чем время прибытия на эту станцию данного поезда, то заменяем его.
Если за весь шаг цикла по i не произошло ни одного обновления, то прерываем работу программы. Несмотря на крайнюю неэффективность алгоритма программа успевает пройти все тесты.


Вот сам код
const
maxn = 100;
maxt = 100;
inf = 2147483647 div 2;
type
station = record
ns:byte;
time:longint;
end;
train = record
n:byte;
st:array[1..maxn]of station;
end;

var
m,n,b,e:byte;
input,output: text;
tr:array[1..maxt]of train;
time:array[0..maxn]of longint;
ok:array[0..maxn]of boolean;

procedure readdata;
var
i,j:integer;
begin
assign(input,'is1131.in');
reset(input);
read(input,n,e,m);
b:=1;
for i:=1 to m do
begin
read(input,tr[i].n);
for j:=1 to tr[i].n do
read(input,tr[i].st[j].ns, tr[i].st[j].time);
end;
close(input);
end;

procedure writedata;
begin
assign(output,'is1131.out');
rewrite(output);
writeln(output,time[e]);
close(output);
end;

procedure update(st:byte);
var
i,j,k:byte;
begin
ok[st]:=true;
for i:=1 to m do
for j:=1 to tr[i].n do
if (tr[i].st[j].ns = st) and (tr[i].st[j].time >= time[st]) then
for k:= j+1 to tr[i].n do
if tr[i].st[k].time < time[tr[i].st[k].ns] then
time[tr[i].st[k].ns] := tr[i].st[k].time;

end;

procedure solve;
var
i,min:byte;
begin
for i:=0 to n do
begin
time[i] := inf;
ok[i] := false;
end;
time[b] := 0;
while not ok[e] do
begin
min :=0;
for i:=1 to n do
if not ok[i] then
if time[i] < time[min] then min := i;
if min < 1 then break;
update(min);
end;
if not ok[e] then time[e] := -1;

end;

begin
readdata;
solve;
writedata;
end.
gazon вне форума   Ответить с цитированием

Старый 13.11.2012, 08:57
Helpmaster
Member
 
Аватар для Helpmaster
 
Регистрация: 08.03.2016
Сообщений: 0

Люди уже создавали подобные топики на нашем форуме

SheepRun Lite - помоги семье овечек добраться домой
Experiment 13 - 3D головоломка. Помоги ученому вернуться домой
АС домой
Ваши действия по приходу домой

Старый 16.11.2012, 14:00   #2 (permalink)
gazon
Member
 
Регистрация: 21.11.2011
Сообщений: 56
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию

Помогите, пожалуйста
gazon вне форума   Ответить с цитированием
Старый 20.11.2012, 07:46   #3 (permalink)
gazon
Member
 
Регистрация: 21.11.2011
Сообщений: 56
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию

Помогите хотя-бы с двумя последними процедурами, пожалуйста
gazon вне форума   Ответить с цитированием
Старый 20.11.2012, 07:56   #4 (permalink)
gazon
Member
 
Регистрация: 21.11.2011
Сообщений: 56
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию

Почему в процедуре Solve цикл с 0 начинается, почему индексация time:array[0..maxn]of longint;
ok:array[0..maxn]of boolean; с 0
gazon вне форума   Ответить с цитированием
Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Выкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.




Часовой пояс GMT +4, время: 06:13.

Powered by vBulletin® Version 6.2.5.
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.