eolymp
bolt
Try our new interface for solving problems
Məsələlər

Перестройка паутины

Перестройка паутины

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Старому пауку захотелось внести разнообразие в свою жизнь. Для этого он решил перестроить свою прямоугольную паутину. Изначально паутина представляет собой прямоугольник размером a×b. За одну секунду паук может сделать одну из следующих операций с паутиной x×y:

  1. Довязать к паутине полоску x×k так, что получится прямоугольник x×(y+k), для любого натурального ky, являющегося делителем числа y.

  2. Довязать к паутине полоску k×y так, что получится прямоугольник (x+k)×y, для любого натурального kx, являющегося делителем числа x.

  3. Отрезать от паутины полоску размером x×k так, что получится прямоугольник x×(y-k), для любого натурального k < y, являющегося делителем числа y.

  4. Отрезать от паутины полоску размером k×y так, что получится прямоугольник (x-k)×y, для любого натурального k < x, являющегося делителем числа x.

Вам известны начальные размеры паутины и размеры, которые хочет получить паук. Ваша задача вычислить, какое минимальное время ему для этого понадобится. Ориентация паутины не имеет значения (a×b и b×a – одинаковые паутины).

Giriş verilənləri

Четыре целых числа a, b, c, d (1a, b, c, d10^5).

Çıxış verilənləri

Единственное число – минимальное время в секундах, необходимое для перестройки паутины a×b в паутину c×d.

Nümunə

Giriş verilənləri #1
5 2 2 3
Çıxış verilənləri #1
2
Müəllif Andrej Selivanov
Mənbə "Five for week" 05 (2013-2014), Breadth First Search