Выведите одно натуральное число – номер ближайшего предка для двух видов

@IlushaMax · Регистрация: 09.04.2016

Author24 — интернет-сервис помощи студентам

Возможно как-то неправильно назвал тему, но вот суть:

Кликните здесь для просмотра всего текста

Во время исследований, посвященных появлению жизни на планете Олимпия, учеными было сделано несколько сенсационных открытий:

Все живые организмы планеты происходят от бактерии Bitozoria Programulis.
Эволюция происходила шаг за шагом (по предположению ученых – во время изменения климата на планете).
На каждом шаге эволюции из каждого вида образовывались ровно два подвида, а предыдущий вид исчезал.
Если считать появление бактерии Bitozoria Programulis первым шагом эволюции, то существующие сейчас живые организмы находятся на N-ом шаге.
Чтобы не придумывать названия во время исследований, ученые пронумеровали все виды организмов, которые когда-либо существовали на планете. Для этого они нарисовали дерево эволюции с корнем Bitozoria Programulis, которая получила номер 1. Далее нумеровали виды каждого шага эволюции слева направо. Таким образом непосредственные подвиды Bitozoria Programulis получили номера 2 и 3. Следующими были занумерованы виды третьего шага эволюции – подвиды вида 2 получили номера 4 и 5, а вида 3 – номера 6 и 7, и т.д.

Напишите программу, которая по номерам двух видов вычислит номер вида их ближайшего общего предка в дереве эволюции.

Входные данные

В первой строке входного файла INPUT.TXT записано целое число N (1 ≤ N ≤ 60) – количество этапов эволюции, которые произошли на планете Олимпия до текущего времени. Вторая и третья строки содержат по одному натуральному числу, которые представляют номера видов, для которых требуется найти номер их ближайшего общего предка.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно натуральное число – номер ближайшего предка для двух видов.

Условие

Кликните здесь для просмотра всего текста

Pascal

var n,a,b:longint;
begin
  readln(n,a,b);
  repeat
    a:=a div 2;
    b:=b div 2;
  until a=b;
  writeln(a);
end.

Как решил я
Подозреваю, что там длинная арифметика, но не на первом же тесте такие большие числа.
В чём еще может быть ошибка

ФедосеевПавел · 28.10.2016, 18:58

Если вы сдаёте на FreePascal, то в нём есть 64-битный типы - QWord, uint64 - в которые "поместятся" все числа 2⁶⁰.

И ещё, в условии нет указаний, что номера подвидов будут из одной эпохи (одного шага).

Может быть это поможет.

Добавлено через 1 минуту
Также, обращу внимание на

Сообщение от IlushaMax

В первой строке входного файла INPUT.TXT записано целое число N (1 ≤ N ≤ 60) – количество этапов эволюции, которые произошли на планете Олимпия до текущего времени. Вторая и третья строки содержат по одному натуральному числу, которые представляют номера видов, для которых требуется найти номер их ближайшего общего предка.

Т.е. предполагается три readln.

Добавлено через 6 минут
И ещё, полагаю, что есть смысл учесть случай с одинаковыми номерами видов на входе.

Добавлено через 8 минут
В общем, учёл все написанное - сдал на acmp с первой попытки:
1. Переменная N - не знаю для чего. В решении не учитывается.
2. Потенциально возможно, что на входе a=b.
3. Потенциально возможно, что a и b из разных шагов, и к общему предку путь от них - разной длины.
4. Нет длинной арифметики - всё умещается в uint64.

@IlushaMax · 28.10.2016, 19:10 **[ТС]**

Спасибо, сам додумался до мысли об эпохе. Получилось сдать, но число n оказалось бесполезным.

ФедосеевПавел · 28.10.2016, 19:14

Я так сделал

Pascal

program acmp_0784;
 
var
  N: integer;
  First, Second: uint64;
begin
  readln(N);
  readln(First);
  readln(Second);
  while First <> Second do
  begin
    while First > Second do
      First := First div 2;
    while Second > First do
      Second := Second div 2;
  end;
  writeln(First);
end.

@IlushaMax · 28.10.2016, 19:16 **[ТС]**

У меня в коде бардак, но идея точь-в-точь такая же

@bormant · 29.10.2016, 14:46

Сообщение от ФедосеевПавел

Т.е. предполагается три readln.

Из текста выше это не следует, совсем. Read при чтении числовых данных прекрасно перескакиевает через концы строк.
Вот если бы было 3 строки по нескольку чисел, но читать нужно было бы только первые в строке, тогда да, три ReadLn.

Добавлено через 2 минуты
А здесь -- любая комбинация Read/ReadLn годится (считаем, что ReadLn(a,..,b) тождественно Read(a); ...; ReadLn(b)).

ФедосеевПавел · 29.10.2016, 21:20

Спасибо. Я помню, но для ТС - чтобы не расслаблялся подчеркнул отдельно условие.
И вдобавок, когда неизвестно за что хвататься, начинаешь приводить в порядок формат ввода и вывода.

@Notoriously · 30.10.2016, 19:23

Сообщение от ФедосеевПавел

Я так сделал

А как его еще упростить?
Пользуясь вашим кодом, пытался склепать что-то по типу

Pascal

while ((son1 <> son2) and (son1>1) and (son2>1)) do 
    begin
        son1 = son1 div 2;
        son2 = son2 div 2;
    end;
    if (son1>son2) then
       writeln(son2)
    else
       writeln(son1);

То есть,чтобы выходить из цикла,как только один из потомков доходит до непосредственно самой бактерии и не ждать другого потомка,которому быть может,еще несколько итераций до нее.
Но получается, что пропускаю случай, когда у меня потомки равны допустим 18 и 46 или 4 и 10, то есть имеют общим предком непосредственно 2,а не 1.
Или просто сделать break на 1 в вашем условии и это будет максимальная оптимизация?

ФедосеевПавел · 31.10.2016, 09:58

Если уж хочется оптимального, тогда вариант - вывести оба числа на одну стадию, а потом синхронно делить пополам.

Или - попробовать аналитически решить эту задачу - прийти к формуле. Думаю, что это возможно.

@Notoriously · 06.11.2016, 13:09

Сообщение от ФедосеевПавел

Или - попробовать аналитически решить эту задачу - прийти к формуле. Думаю, что это возможно.

В графах есть какие-то специальные способы нахождения формул в подобных задачах? Или опять же,чистая математическая интуиция?
Пока ничего в голову не приходит. Думал как-то использовать эпоху каждого потомка, но так как чтобы их получить, сделал еще 2 цикла,то на оптимизацию это похоже слабовато.
Был бы благодарен,если бы подсказали,в какую сторону думать.

ФедосеевПавел · 06.11.2016, 16:46

Не знаю. Мы не изучали теорию графов, а то, что я знаю - нахватался на форуме.

Но рассуждая, прихожу к тому, что алгоритм и так быстрый, а с учётом замены деления на сдвиг, так совсем "летающий".
Сейчас я бы решил так

Pascal

program acmp_0784;
 
var
  N: integer;
  First, Second: uint64;
begin
  readln(N);
  readln(First);
  readln(Second);
  while First <> Second do
  begin
    if First > Second then
      First := First shr 1
    else
      Second := Second shr 1;
  end;
  writeln(First);
end.

Это, правда, без проверки на сайте.

Формулу можно вывести, но внутреннее ощущение, что придётся вычислять 2ⁿ при помощи умножения или сдвигов. Что, в общем-то, даст то же время исполнения.

@Cyborg Drone · 08.11.2016, 09:01

Сообщение от ФедосеевПавел

или сдвигов

Сдвига без применения цикла на какое-то количество разрядов (например, b shl 14) опасаться не следует: он выполняется за одну машинную инструкцию. Правда, компилятор норовит применять сдвиг не более, чем на 31 разряд (по умолчанию он с маниакальным упрямством использует 32-разрядную версию shl) но, с помощью некоторых ухищрений, можно его заставить сдвигать и до 63 разрядов.

"Нечестное" решение, без применения циклов, основанное на различных форматах машинного представления чисел:

Pascal

var f: extended;
    first: uint64 absolute f; //здесь порядок числа игнорируем
    s: extended;
    second: packed record m: uint64; p: word end absolute s; //а здесь будем использовать
begin
  readln; //"ввод" N
  readln(f); //в мантиссе получается "правильно сдвинутое" число
  readln(s); //(старший значащий разряд введённого числа оказывается в 63 разряде мантиссы
  second.m := second.m xor first; //получаем различающиеся разряды мантисс ("различие")
  s := second.m; //в порядке числа получается номер старшего разряда "различия" + 16383
  second.m := $8000000000000000 shr (16445 - second.p); //получаем степень двойки, большей "различия" (1 shl second.p - 16383 не катит)
  if second.m = 0 then writeln(f:0:0) else writeln(first div second.m)
end.

Ещё эффективнее будет с ассемблерными вставками, попробую написать, если дури хватит.

Добавлено через 5 часов 28 минут
Неверное решение получилось... Если один из номеров вида 1, а другой не степень двойки, чушь получается.

ФедосеевПавел · 08.11.2016, 09:07

Я так понимаю, что применение extended (полей этого типа) позволило взять log₂ без трудоёмких вычислений.

Хорошее осознание применяемого инструмента!

Спасибо!

Поставлю в план изучить этот формат по-лучше. И тогда ещё раз попробую осознать решение.

Добавлено через 2 минуты
Хотел добавить положительный отзыв, но форум утверждает, что нужно отправить его ещё кому-нибудь.

@Cyborg Drone · 08.11.2016, 10:29

Нашёл алгоритмическую ошибку. Теряется длина операндов. Переписал, теперь без ошибок работает:

Pascal

var f: extended;
    first: packed record m: uint64; p: smallint end absolute f;
    s: extended;
    second: packed record m: uint64; p: smallint end absolute s;
begin
  readln; //"ввод" N
  readln(f);
  readln(s);
  if first.p > second.p then first.p := second.p;
  first.p := 16446 - first.p;
  first.m := first.m shr first.p;
  second.m := second.m shr first.p;
  if first.m <> second.m
    then begin
      second.m := second.m xor first.m;
      s := second.m;
      first.m := first.m shr (second.p - 16382)
    end;
  writeln(first.m)
end.

@bormant · 08.11.2016, 10:47

Анонимные типы, конечно, неплохи, но обычно предпочитаю именованные:

Pascal

type
  ExtRec = packed record m: uint64; p: smallint end;
var
  f: extended; first: ExtRec absolute f;
  s: extended; second: ExtRec absolute s;

@Cyborg Drone · 08.11.2016, 10:55

bormant, согласен. Ко всему прочему, ещё и при множестве переменных писанины и ошибок меньше получается.

Выведите одно натуральное число – номер ближайшего предка для двух видов

Решение

Решение

ФедосеевПавел Модератор 8476 / 4335 / 1642 Регистрация: 01.02.2015 Сообщений: 13,461 Записей в блоге: 8
	28.10.2016, 18:58	2
	Сообщение было отмечено IlushaMax как решение Решение Если вы сдаёте на FreePascal, то в нём есть 64-битный типы - QWord, uint64 - в которые "поместятся" все числа 2⁶⁰. И ещё, в условии нет указаний, что номера подвидов будут из одной эпохи (одного шага). Может быть это поможет. Добавлено через 1 минуту Также, обращу внимание на Сообщение от IlushaMax В первой строке входного файла INPUT.TXT записано целое число N (1 ≤ N ≤ 60) – количество этапов эволюции, которые произошли на планете Олимпия до текущего времени. Вторая и третья строки содержат по одному натуральному числу, которые представляют номера видов, для которых требуется найти номер их ближайшего общего предка. Т.е. предполагается три readln. Добавлено через 6 минут И ещё, полагаю, что есть смысл учесть случай с одинаковыми номерами видов на входе. Добавлено через 8 минут В общем, учёл все написанное - сдал на acmp с первой попытки: 1. Переменная N - не знаю для чего. В решении не учитывается. 2. Потенциально возможно, что на входе a=b. 3. Потенциально возможно, что a и b из разных шагов, и к общему предку путь от них - разной длины. 4. Нет длинной арифметики - всё умещается в uint64. 2

@IlushaMax 0 / 0 / 4 Регистрация: 09.04.2016 Сообщений: 128
	28.10.2016, 19:10 [ТС]	3
	Сообщение было отмечено ФедосеевПавел как решение Решение Спасибо, сам додумался до мысли об эпохе. Получилось сдать, но число n оказалось бесполезным. 0

@IlushaMax 0 / 0 / 4 Регистрация: 09.04.2016 Сообщений: 128
	28.10.2016, 19:16 [ТС]	5
	У меня в коде бардак, но идея точь-в-точь такая же 0

@bormant Модератор 7771 / 4600 / 2824 Регистрация: 22.11.2013 Сообщений: 13,080 Записей в блоге: 1
	29.10.2016, 14:46	6
	Сообщение от ФедосеевПавел Т.е. предполагается три readln. Из текста выше это не следует, совсем. Read при чтении числовых данных прекрасно перескакиевает через концы строк. Вот если бы было 3 строки по нескольку чисел, но читать нужно было бы только первые в строке, тогда да, три ReadLn. Добавлено через 2 минуты А здесь -- любая комбинация Read/ReadLn годится (считаем, что ReadLn(a,..,b) тождественно Read(a); ...; ReadLn(b)). 1

ФедосеевПавел Модератор 8476 / 4335 / 1642 Регистрация: 01.02.2015 Сообщений: 13,461 Записей в блоге: 8
	29.10.2016, 21:20	7
	Спасибо. Я помню, но для ТС - чтобы не расслаблялся подчеркнул отдельно условие. И вдобавок, когда неизвестно за что хвататься, начинаешь приводить в порядок формат ввода и вывода. 0

ФедосеевПавел Модератор 8476 / 4335 / 1642 Регистрация: 01.02.2015 Сообщений: 13,461 Записей в блоге: 8
	31.10.2016, 09:58	9
	Если уж хочется оптимального, тогда вариант - вывести оба числа на одну стадию, а потом синхронно делить пополам. Или - попробовать аналитически решить эту задачу - прийти к формуле. Думаю, что это возможно. 1

@Notoriously 70 / 70 / 35 Регистрация: 06.07.2016 Сообщений: 415
	06.11.2016, 13:09	10
	Сообщение от ФедосеевПавел Или - попробовать аналитически решить эту задачу - прийти к формуле. Думаю, что это возможно. В графах есть какие-то специальные способы нахождения формул в подобных задачах? Или опять же,чистая математическая интуиция? Пока ничего в голову не приходит. Думал как-то использовать эпоху каждого потомка, но так как чтобы их получить, сделал еще 2 цикла,то на оптимизацию это похоже слабовато. Был бы благодарен,если бы подсказали,в какую сторону думать. 0

ФедосеевПавел Модератор 8476 / 4335 / 1642 Регистрация: 01.02.2015 Сообщений: 13,461 Записей в блоге: 8
	08.11.2016, 09:07	13
	Я так понимаю, что применение extended (полей этого типа) позволило взять log₂ без трудоёмких вычислений. Хорошее осознание применяемого инструмента! Спасибо! Поставлю в план изучить этот формат по-лучше. И тогда ещё раз попробую осознать решение. Добавлено через 2 минуты Хотел добавить положительный отзыв, но форум утверждает, что нужно отправить его ещё кому-нибудь. 1

@Cyborg Drone Модератор 9871 / 5239 / 3306 Регистрация: 17.08.2012 Сообщений: 16,007
	08.11.2016, 10:55	16
	bormant, согласен. Ко всему прочему, ещё и при множестве переменных писанины и ошибок меньше получается. 0