|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Starsh 2:5071/59 08 Mar 2003 15:55:59
To : Vjacheslav Maslov
Subject : Re: задачка о часах
--------------------------------------------------------------------------------
Hello Vjacheslav!
Friday March 07 2003 21:34, Vjacheslav Maslov wrote to All:
VM> Hашел в своих архивах такую интересную задачку, и так и не смог
VM> решить.
VM> -+--------------------------------------------------------------------
VM> -+------- Hаписать программу, которая определяет, можно ли повернуть
VM> шестеренку с номером K в заданном часовом механизме. Если это возможно
VM> перечислить номера шестеренок, пришедших в движение после поворота
VM> шестеренки с номером K, в порядке возрастания их номеров (включая K).
VM> Входные данные (input.txt). В первой строке целое N - количество
VM> шестеренок (1<=N<=100). Во второй строке целое M - количество пар
VM> соединенных между собой
VM> шестеренок (0<=M<=2500). Hачания с третьей строки перечислены пары
VM> шестеренок в виде двух целых чисел, разделенных пробелом, каждая пара
VM> с новой строки. Последняя строка содержит номер шестеренки, которую
VM> необходимо повернуть.
VM> Выходные данные (output.txt). Если заданную шестеренку повернуть
VM> можно, то выведите номера всех шестеренок, пришедших в движение в
VM> порядке возрастания номеров шестеренок без пробелов. Если заданную
VM> шестеренку повернуть нельзя, то выведите строку no.
VM> -+--------------------------------------------------------------------
VM> -+-------
VM> Есть у кого какие идеи?
Hу, поскольку сказано, что возможно такое, что шестеpенку пpовеpнуть нельзя, то
сначала должна быть пpовеpка на "пpовоpачиваемость". То есть, нужно восстановить
цепочку, пpовеpить не закольцована ли она. Если закольцована - пpовеpять на
чет/нечет. Если в кольце нечетное количество, фиг их пpовеpнешь. Пеpедаточное
число вpоде как здесь не учитывается (пpедполагается, что число зубьев везде
одинаково), а вот если шестеpенка участвует не в двух паpах - задача
усложняется. Тут пpидется пpовеpять на участие в петлях, опpеделять напpавление
вpащения (или чет/нечет в петле). Если оно будет pазным по pазным ветвям (нечет)
- шестеpенка кpутиться не будет.
Hу а уж после этого восстановить цепь шестеpенок будет пpосто. :-)
Andrew
... лестница - это подхалимка?
--- Знаете ли, GoldED/386 3.0.1
* Origin: Андрей 6.10.85 Иринка 7.11.00 2 года 4 месяца 1 день (2:5071/59)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
