На олимпиаде по информатике было 4 задачки:
1. Даны натуральные числа m и n. Найти такие числа m1 и n1, не имеющие общих делителей, что m1/n1=m/n. Числа m и n ввести с клавиатуры.
2. Дано натуральное число n. Напечатать в порядке возрастания все простые несократимые дроби, заключенные между 0 и 1, знаменатели которых не привышают n. Дроби выводить в формате p/q. Число n задать с клавиатуры.
3. Имеется прямоугольный лист бумаги, длина которого равна N см, а ширина M см. С листом можно производить следующие операции: сгибать лист вдвое, совмещая противоположные стороны; сгибать лист, совмещая одну сторону с параллельной ей линией сгиба; разгибать лист при этом оставляя на нем линию сгиба. Написать программу, которая определяет: можно ли его свернуть так, чтобы получился прямоугольник длиной P см и шириной Q см. В случае утвердительного ответа программа должна выдавать минимальное количество операций с листом, необходимых для этого.
N, M, P и Q - дробно-рациональные числа, каждое из которых задается своим числителем и знаменателем. Числа вводятся с клавиатуры в виде "p,q", где p - числитель, а q - знаменатель.
Если лист свернуть можно, то ответ должен содержать "ДА". В противном случае - "НЕТ".
4. Имеется некий лабиринт неизвестной структуры. По лабиринту движется робот. На каждом шагесвоего движения робот делает шаг вперед или разворачивается влево (вправо) на 90 градусов. Весь путь движения робота описывается символьной строкой длиной не более 80 символов. Символ F означает движение на шаг вперед, L, R - поворот на 90 градусов влево или вправо соответственно.
Есть предположение, что в процессе своего движения по лабиринту робот может ходить кругами, т. е. пересекать ранее пройденные точки, или поворачиваться в неправильную сторону (3 раза налево вместо 1 направо). Задача заключается в том, чтобы сократить маршрут движения робота, убрав из него все петли и лишние повороты. Входная строка, описывающая исходный маршрут движения, вводится пользов телем с экрана. На выход необходимо выдать строку, описывающую сокращенный маршрут движения.
Прошу написать варианты решений (кто как думает).

Это программка ко второй задаче

Мож кто придумает проще?)

M Pakshin A. S.

Не забываем выделять код специальными тегами!

Это сообщение отредактировал(а) Pakshin A. S. - 18.6.2007, 18:38

Для четвёртой, наверное, ввел бы систему координат и запоминал пройдённые точки, затем каждый раз проверял, была ли такая точка. Через дерево, наверное, тоже можно. Составить его маршрут в виде дерева: корень - конец марщрута, при составлении "взвешивать его", по завершению составления можно найти наикротчайший маршрут и получить нужную строку.

Добавлено @ 17:29

m1n=n1m, подбираем такие натуральные m1 и n1 и проверяем наличие общих делителей. По идее, не сложно, если не изощряться.

Добавлено @ 17:37

Сейчас думать некогда, но пришла такая идея. Подбором - слишком долго и просто. Есть 2 неизвестных, стало быть нужно получить >=2-х уравнений.

m div n = p div q
m mod n = p mod q

p = (m div n) * q
m mod n = ( (m div n) * q) mod q

Отсюда, по идее, можно выразить q.
А потом найти p.

Нужно проверить, не уверен, что пашет. Вечером или завтра код набью.

Это сообщение отредактировал(а) powerfox - 18.6.2007, 17:52

!  Pakshin A. S.

PIvO, не стоит создавать дубликаты темы; для решение проблем достаточно создать одну тему...

Как мне сказал Void, такое дерево зовётся графом. Точнее, это граф, а не дерево.

Имхо, первая задача - это, фактически, обычное сокращение дроби: нужно найти наибольший общий делитель m и n (например, алгоритмом Евклида) и разделить оба числа на него...

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

powerfox, сорри, можно чуть подробнее? Каким образом тогда сохранится пропорция?

SelenIT, 
допустип числа 11 и 7.
У них нет общего делителя.
11     22
---  =  ---             здесь нарушается условие, что числа не должны иметь делителя, а очевидно, что делитель 2. Но можно подобрать такие, что будет выполняться
7       14

Например, 33/21. 

Твоё решение будет работать, только если дробь будет сократима (как раз найти наибольший делитель и поделить на него).

powerfox, имхо, если дробь несократима, единственное решение задачи - сами m и n (по-моему, условие этого не запрещает). Любые другие пары чисел, удовлетворяющих пропорции, непременно будут иметь общий делитель. Разве не так?

Ты прав. Я не подумал, что 33 и 21 делятся на 3 
Действительно, просто алгоритм Евклида.

Вот какой ужас получился у меня для второй задачи (привожу решение на... Javascript, чтобы можно было протестить алгоритм прямо в браузере, не тратя время на компиляцию):

Полагаю, перевести логику на C++ не проблема, тем более синтаксис похож - у меня в MS VC++ 2005 заработало, хотя я вообще C++ не знаю... ;)

Зато, в отличие от варианта Melarosы, оно выводит дроби по возрастанию (в соответствии с ТЗ) и не оставляет вещей типа 4/6...

P.S. Небольшое пояснение: т.к. знаменатель по условию не может превосходить n, то разность соседних дробей p1/q1 - p0/q0 ≥ 1/(n*q0) ≥ 1/(n*(n-1)) > 1/n² (например, при n=9, первые дроби - 1/9 и 1/8 - различаются на 1/72). Алгоритм ищет минимальную разность (т.е. максимальный общий знаменатель), при котором следующая дробь сократима до подходящего (не превышающего n) знаменателя, перебирая потенциально допустимые общие знаменатели по убыванию. Чувствую, что его можно еще изрядно оптимизировать...

Это сообщение отредактировал(а) SelenIT - 2.7.2007, 02:11

К третьей задаче: насколько я понимаю, для получения ответа ДА должны выполняться условия:

или же

где x, y, m и n - натуральные числа. Соответственно, у решения будут 2 ветви, каждая из которых опять же сводится к сокращению 2-х дробей и проверке знаменателя на принадлежность к ряду степеней двойки (по идее, можно битовыми операциями).

Что же до минимально нужного числа шагов, по-видимому, оценка нижней границы равна m+n. Насколько реальное количество шагов больше (сколько раз придется разгибать) - видимо, нужно анализировать x и y... есть интуитивная пока непроверенная догадка, что нужно считать нули в их двоичной записи...

Это сообщение отредактировал(а) SelenIT - 24.6.2007, 19:17

Эту задачу можно решить безо всяких gcd и оптимизаций.
Гуглим по "ряд Фарея" - и будет вам алгоритм за линейное (относительно количества дробей в ответе) время.

Вообще, давать такие задачи на олимпиаде по программированию - плохой стиль. Кто-то, кто знает ряд Фарея или подобную систему Штерна-Броко, решит её за 5 минут, а другой может думать 2 часа и не придумать - это совсем не тривиальный алгоритм. (Если, конечно, там не маленькие ограничения на N были даны)

Это сообщение отредактировал(а) maxdiver - 20.12.2008, 09:45

для последней задачки