Имеется железнодорожная сеть (набор станций и линий).
Линии – одноколейные, но позволяющие движение в обе стороны. Между собой линии не пересекаются (кроме как на станциях).
Длины линий — целые числа. Станции идентифицируются номерами. Сеть
задаётся тройками — ID станции, ID станции, Длина линии.
Одновременно с равными постоянными скоростями стартуют по
заданным маршрутам несколько паровозиков. Маршрут каждого паровозика задаётся последовательностью номеров проходимых станций.
Требуется определить, не сталкиваются ли какие-то паровозики.
Столкновением считается ситуация, когда два паровозика одновременно находятся в одной точке:
— на одной линии, следуя в противоположные стороны,
— на одной станции.
Здравствуйте, ANMNS, Вы писали:
ANM>У кого-нибудь есть решение?
Прошу прощения за резкость — а работать Вы так же собираетесь? Публиковать в форуме ТЗ и спрашивать "у кого-нибудь есть реализация?" Или просто хотите сравнить свое решение с чьим-либо еще?
[ posted via RSDN@Home 1.1.4 stable SR1 r568, accompanied by Sodom — Fields Of Honour ]
Здравствуйте, ANMNS, Вы писали:
ANM>У кого-нибудь есть решение?
Чначало выборуой сортируем порядок посещения станций. Получаем один список, где записаны прибытия и отбытия, упорядоченный по времени, при равном времение — сначала прибытия, потом отбытия. Потом эмулируем движение. Шаг эмуляции — отправление/прибытия поезда на станцию. При выезде со станции помечаем для нее, что с нее едет поезд в направлении такой-то станции и вычеркиваем его из списка находящихся на станции. По прибытии вычеркиваем из списка находящихся в пути для предыдущей, на той, куда прибыли, записываем в список находящихся на станции. Проверяем по списку, нет ли на станции еще паровозов и не едет ли в данный момент поезд с этой станции туда, откуда мы выехали.
Примерно так.
PS. "Список находящихся на станции" состоит из не более одного элемента
Здравствуйте, ANMNS, Вы писали:
ANM>Всем привет! ANM>Описание тестового задания:
ANM>Имеется железнодорожная сеть (набор станций и линий). ANM>Линии – одноколейные, но позволяющие движение в обе стороны. Между собой линии не пересекаются (кроме как на станциях). ANM>Длины линий — целые числа. Станции идентифицируются номерами. Сеть ANM>задаётся тройками — ID станции, ID станции, Длина линии. ANM>Одновременно с равными постоянными скоростями стартуют по ANM>заданным маршрутам несколько паровозиков. Маршрут каждого паровозика задаётся последовательностью номеров проходимых станций. ANM>Требуется определить, не сталкиваются ли какие-то паровозики. ANM>Столкновением считается ситуация, когда два паровозика одновременно находятся в одной точке: ANM>- на одной линии, следуя в противоположные стороны, ANM>- на одной станции.
Здравствуйте, ANMNS, Вы писали:
ANM>Описание тестового задания:
... ANM>Использовать C++. ANM>У кого-нибудь есть решение?
А вам не приходило в голову, что тестовое задание дается для того, чтобы вы его решили сами?
И если вы не можете его решить, значит ваш уровень слишком низкий для работы в этой фирме.
Да забей
Всё равно ему решения сюда никто не напишет.
А вопросов типа "а у кого есть реализация" или "как мне сделать то-то и то-то" в этом форуме навалом, кстати.
Хотя чувак конечно всех переплюнул Думаю, если тот работодатель, кто дал ему задание, читает этот форум — работы чуваку не видать.
"SchweinDeBurg" <10117@users.rsdn.ru> wrote in message news:1476406@news.rsdn.ru... > Здравствуйте, ANMNS, Вы писали: > > ANM>У кого-нибудь есть решение? > > Прошу прощения за резкость — а работать Вы так же собираетесь? Публиковать в форуме ТЗ и спрашивать "у кого-нибудь есть реализация?" Или просто хотите сравнить свое решение с чьим-либо еще?
Ха-ха!
Эт тебе че, в аккорд-софте дали? судя по рассказам в этом форуме — как раз их специализация
"ANMNS" <47897@users.rsdn.ru> wrote in message news:1476391@news.rsdn.ru... > Всем привет! > Описание тестового задания: > > Имеется железнодорожная сеть (набор станций и линий). > Линии – одноколейные, но позволяющие движение в обе стороны. Между собой линии не пересекаются (кроме как на станциях). > Длины линий — целые числа. Станции идентифицируются номерами. Сеть > задаётся тройками — ID станции, ID станции, Длина линии. > Одновременно с равными постоянными скоростями стартуют по > заданным маршрутам несколько паровозиков. Маршрут каждого паровозика задаётся последовательностью номеров проходимых станций. > Требуется определить, не сталкиваются ли какие-то паровозики. > Столкновением считается ситуация, когда два паровозика одновременно находятся в одной точке: > — на одной линии, следуя в противоположные стороны, > — на одной станции. > > Использовать C++. > > У кого-нибудь есть решение? > > ANMNS
Встречал я как-то это тестовое задание.
А вакансия эта предлагалась через RSDN.
Так что, вероятность, что ваше сообщение будет прочитано тем, кто предложил задание весьма велика
Если вам в голову не приходит ни одного варианта решения этой задачи, то идти туда работать наверное не стоит.
ANM>У кого-нибудь есть решение?
Хех.
Да он даж язык вон в просьбе написал.
То есть ему нужно ужо всё написанное. А не ввиде примерных набросков на естественном языке.
"mihoshi" <14832@users.rsdn.ru> wrote in message news:1476461@news.rsdn.ru... > Здравствуйте, vs_, Вы писали: > > vs_>Да забей > vs_>Всё равно ему решения сюда никто не напишет. > Упс. Рефлекс
Есть математики, есть програмисты. Первые специализируются на решении математических задач (в том числе и численными методами). Вторые умеют правильно закодировать алгоритм, чтобы "компьютер" смог решать задачу.
Вот что мне непонятно, зачем тратить время программиста на решение математических задач. Что, C++ даёт преимущества перед другими языками с точки зрения решения данной задачи???
Единственное объяснение (не оправдание!) — это то, что компании требуются математики-програмисты. Хотя и это странно, поскольку если компания занимается решением такого рода задач, то должен быть специализированный математик.
Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая такие задания?
Здравствуйте, Spidola, Вы писали:
S>ИМХО: странная компания Поясню.
S>Есть математики, есть програмисты. Первые специализируются на решении математических задач (в том числе и численными методами). Вторые умеют правильно закодировать алгоритм, чтобы "компьютер" смог решать задачу.
S>Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая такие задания?
Проверка, может ли кандидат мыслить и находить решения.
ИМХО, программист должен не только уметь кодировать готовый алгоритм, но и придумать свой (по крайней мере для таких простых случаев).
И я бы не сказал, что это математическая задачка.
Здравствуйте, valmond, Вы писали:
S>>Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая такие задания?
V>Ну можен хочет понять общую эрудированность и сообразительность? V>типа как перевести эту задачу на мат язык, найти алгориты и реализовать.
V>я конечно в графах не силен, но что-то мне подсказывает, что есть готовые кирпичики из которых решение этой задачи складывается достаточно просто.
Конечно есть кирпичики Открывается учебник, смотрится алгоритм и алгоритмизируется. В чём смысл заставлять человека решать задачу, которая уже оптимально решена математиками? Единственное объяснение, которое я вижу, это посмотреть, насколько быстро человек НАЙДЁТ решение задачи, а не придумает его (ведь работодателю, по большому счёту, наплевать, как будет решена задача — главное, чтобы она была решена корректно, в нужный срок и заминимальную стоимость).
В свете этого пост автора можно рассматривать как шаг правильный и корректный
S>Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая такие задания?
Соображалку проверить? Все не хуже, чем задача про открытый холодильник в ABBYY?
Здравствуйте, olen33, Вы писали:
O>Здравствуйте, Spidola, Вы писали:
S>>ИМХО: странная компания Поясню.
S>>Есть математики, есть програмисты. Первые специализируются на решении математических задач (в том числе и численными методами). Вторые умеют правильно закодировать алгоритм, чтобы "компьютер" смог решать задачу.
S>>Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая такие задания?
O>Проверка, может ли кандидат мыслить и находить решения. O>ИМХО, программист должен не только уметь кодировать готовый алгоритм, но и придумать свой (по крайней мере для таких простых случаев). O>И я бы не сказал, что это математическая задачка.
Зачем??? Зачем придумывать свой алгоритм??? Есть проверенные и выверенные алгоритмы, и навык их поиска и использования на порядок важнее, нежели умение придумывать свои, которые будут содержать потенциальные ошибки, будут неоптимальны и т.п.
Здравствуйте, Spidola, Вы писали:
S>Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая такие задания?
имхо Вы неправы. Задание нормальное, и с его помощью работодатель может очень многое узнать о человеке. Конечно, разработка новых алгоритмов работы на графах — не задание тестового уровня. Но такого задания никто и не давал, ведь скорее всего соответствующие алгоритмы уже изобретены, и от программиста требуется только найти адекватный алгоритм и правильно его применить.
Работодатель в этом случае видит многое — понимает ли тестируемый сложность задачи, видит предложенный способ решения (если изобретается очередной "brute force" велосипед, скорее всего тестируемый плохо знаком с алгоритмами). Плюс, культура кодирования, владение конкретным языком. Может С++ и не дает преимуществ, но компании нужны С++ программисты — так что давать задание на Паскале?
+, каждый уважающий себя программист должен быть знаком с теоретической частью, не зря же будущим программистам преподают теорию вероятности, графов, комбинаторику и т.д., хотя они и не собираются стать теоретиками?
Или просто хотите сравнить свое решение с чьим-либо еще?
