Олимпийские виноградники выполняют свои упражнения на стандартных деревьях. В частности, Стандартное дерево nимеет вершины для 0сквозного прохождения n-1и ребра, связывающие каждую ненулевую вершину aс вершиной n % aпод ней. Так, например, Standard Tree 5 выглядит так:

3
|
2   4
 \ /
  1
  |
  0

потому что остаток, когда 5 делится на 3, равен 2, остаток, когда 5 делится на 2 или 4, равен 1, а остаток, когда 5 делится на 1, равен 0.

В этом году Тарзан будет защищать свое золото с помощью новых процедур, каждая из которых начинается в вершине n - 1, качается в вершину n - 2, продолжается в вершину n - 3и т. Д., Пока, наконец, он не спешится в вершину 0.

Балл за рутину - это сумма баллов за каждый свинг (включая демонтаж), а за свинг - это расстояние в дереве между его начальной и конечной точками. Таким образом, процедура Тарзана на Стандартном Дереве 5 имеет оценку 6:

• размах от 4до 3трех очков (вниз, вверх, вверх),
• свинг от 3до 2одно очка (вниз),
• свинг от 2до 1десятков в одной точке (вниз), и
• отсоединились от 1до 0одно очка (вниз).

Напишите программу или функцию, которая, учитывая положительное целое число n, вычисляет оценку рутины Тарзана на Стандартном дереве n. Образцы входов и выходов:

 1 ->  0
 2 ->  1
 3 ->  2
 4 ->  6
 5 ->  6
 6 -> 12
 7 -> 12
 8 -> 18
 9 -> 22
10 -> 32
11 -> 24
12 -> 34
13 -> 34
14 -> 36
15 -> 44
16 -> 58
17 -> 50
18 -> 64
19 -> 60
20 -> 66
21 -> 78
22 -> 88
23 -> 68
24 -> 82

Правила и оценка кода как обычно для код-гольфа .

C 98 97 байт

F(i){int c[i],t=i-2,n=0,p;for(;++n<i;)for(p=c[n]=n;p=i%p;c[p]=n)t+=c[p]<n-1;return i>2?t*2:i-1;}

Это вычисляет расстояние между каждой парой точек по следующей формуле:

• Добавьте расстояние от корня до узла A
• Добавьте расстояние от корня до узла B
• Вычтите 2 * длину общего корня из A и B

Это имеет то преимущество, что применительно ко всем парам это то же самое, что и:

• Добавьте 2 * расстояние от корня до каждого узла
• Вычтите 2 * длину общего корня каждой пары узлов
• Вычтите расстояние от корня до первого узла
• Вычтите расстояние от корня до последнего узла

Чтобы упростить логику, мы предполагаем, что мы идем от узла 0 к узлу n-1, а не от n-1 до 0, как указано в вопросе. Расстояние от корневого узла до узла 0, очевидно, равно 0 (они одинаковые). И мы можем видеть, что для (большинства) деревьев расстояние от последнего узла до корня равно 2:

                    n+1 % n = 1  for all n > 1
and:                  n % 1 = 0  for all n >= 0
therefore:  n % (n % (n-1)) = 0  for all n > 2

Это означает, что у нас есть некоторые особые случаи (n <2), но мы можем объяснить их достаточно легко.

Сломать:

F(i){                               // Types default to int
    int c[i],                       // Buffer for storing paths
        t=i-2,                      // Running total score
        n=0,                        // Loop index
        p;                          // Inner loop variable
    for(;++n<i;)                    // Loop through all node pairs (n-1, n)
        for(p=c[n]=n;p=i%p;c[p]=n)  //  Recurse from current node (n) to root
            t+=c[p]<n-1;            //   Increase total unless this is a common
                                    //   node with the previous path
    return i>2?   :i-1;             // Account for special cases at 1 and 2
               t*2                  // For non-special cases, multiply total by 2
}

_{Спасибо @feersum за 1 байт сохранен}

Бонус: деревья!

Я написал программу быстрого и грязного, чтобы увидеть, как эти деревья выглядят. Вот некоторые из результатов:

6:

5 4  
| |  
1 2 3
 \|/ 
  0  

8:

  5      
  |      
7 3   6  
|  \ /   
1   2   4
'--\|/--'
    0    

13:

   08              
    |              
11 05   10 09 07   
 |   \ /    |  |   
02   03    04 06 12
 '-----\  /---'--' 
        01         
         |         
        00         

19:

   12                       
    |                       
   07   14                  
     \ /                    
     05    15 11            
       \  /    |            
17      04    08 16 13 10   
 |       '-\  /--'   |  |   
02          03      06 09 18
 '---------\ |/-----'--'--' 
            01              
             |              
            00              

49:

                         31                                                    
                          |                                                    
           30            18   36                                               
            |              \ /                                                 
           19   38 27      13    39 29    32                                   
             \ /    |        \  /    |     |                                   
   26        11    22 44      10    20 40 17   34                              
    |         '-\  /--'        '-\  /--'    \ /                                
47 23   46       05               09        15    45 43 41 37 33 25    35 28   
 |   \ /          '--------------\ |/-------'-----'   |  |  |  |  |     |  |   
02   03                           04                 06 08 12 16 24 48 14 21 42
 '----'--------------------------\ |/----------------'--'--'--'--'--'    \ |/  
                                  01                                      07   
                                   '-----------------\  /-----------------'    
                                                      00                       

Python 2, 85 байт

def f(a,i=1):h=lambda n:n and{n}|h(a%n)or{0};return i<a and len(h(i)^h(i-1))+f(a,i+1)

Perl, 65 59 55 54 байта

Включает +2 для -ap

Запустите с размером дерева на STDIN:

for i in `seq 24`; do echo -n "$i: "; vines.pl <<< $i; echo; done

vines.pl:

#!/usr/bin/perl -ap
$_=map{${"-@F"%$_}|=$_=$$_|$"x$p++.1;/.\b/g}1-$_..-1

объяснение

Если переписать дерево

3
|
2   4
 \ /
  1
  |
  0

где каждый узел содержит множество всех своих предков и самого себя:

 {3}
  |
{2,3}   {4}
   \    /
    \  /
  {1,2,3,4}
      |
 {0,1,2,3,4}

Тогда мы можем описать, например, все узлы пути от 4 до 3 как:

• Все узлы, которые содержат 3, но не 4 (понижаясь от 3)
• Все узлы, которые содержат 4, но не 3 (понижаясь с 4)
• Самый высокий узел, который содержит 3 и 4 (соединение)

Количество ребер на единицу меньше количества узлов, поэтому мы можем использовать это для игнорирования точки соединения, поэтому число ребер на пути от 4 до 3 равно 3, потому что:

• Количество узлов, которые содержат 3, но не 4: 2 узла
• Количество узлов, которые содержат 4, но не 3: 1 узел

Обратите внимание, что это также работает для пути, который непосредственно идет к его цели, например, для пути от 3 до 2 число ребер равно 1, потому что:

• Количество узлов, которые содержат 2, но не 3: 0 узла
• Количество узлов, которые содержат 3, но не 2: 1 узел

Затем мы можем суммировать по всем этим комбинациям.

Если вместо этого вы посмотрите только на узел, например, на узел 2 с установленным предком {2,3}. Этот узел будет вносить один раз при обработке пути, 2 to 1потому что он содержит 2, а не 1. Он ничего не даст для пути, 3 to 2так как он имеет 2 и 3, но он будет вносить один раз при обработке пути, 4 to 3поскольку у него есть 3, но нет 4. Как правило, число в наборе предков узла будет содержать одно для каждого соседа (один ниже или выше), которого нет в наборе. За исключением максимального элемента (в данном случае 4), который вносит вклад только для нижнего соседа 3, так как нет пути5 to 4, Simular 0 является односторонним, но так как 0 всегда находится в корне дерева и содержит все числа (это конечное соединение, а мы не учитываем соединения), никогда не будет никакого вклада от 0, поэтому проще всего оставить узел 0 в целом.

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

Чтобы легко обрабатывать соседей, я собираюсь представить наборы предков в виде строки пробелов и единиц, где каждый 1 в позиции p обозначает, что n-1-p является предком. Так, например, в нашем случае n=51 в позиции 0 означает, что 4 является предком. Я оставлю в конце места. Итак, фактическое представление дерева, которое я построю, таково:

" 1"
  |
" 11"   "1"
   \    /
    \  /
   "1111"

Обратите внимание, что я пропустил узел 0, который будет представлен, "11111"потому что я собираюсь игнорировать узел 0 (он никогда не вносит свой вклад).

Предки без нижнего соседа теперь представлены концом последовательности 1. Предки без более высокого соседа теперь представлены началом последовательности 1, но мы должны игнорировать любое начало последовательности в начале строки, так как это будет представлять путь, 5 to 4который не существует. Эта комбинация точно соответствует регулярному выражению /.\b/.

Построение строк предков выполняется путем обработки всех узлов в указанном порядке n-1 .. 1и установки 1 в позицию для самого узла и выполнения «или» в потомке.

При этом программа достаточно проста для понимания:

-ap                                                  read STDIN into $_ and @F

   map{                                    }1-$_..-1 Process from n-1 to 1,
                                                     but use the negative
                                                     values so we can use a
                                                     perl sequence.
                                                     I will keep the current
                                                     ancestor for node $i in
                                                     global ${-$i} (another
                                                     reason to use negative
                                                     values since $1, $2 etc.
                                                     are read-only
                       $$_|$"x$p++.1                 "Or" the current node
                                                     position into its ancestor
                                                     accumulator
                    $_=                              Assign the ancestor string
                                                     to $_. This will overwrite
                                                     the current counter value
                                                     but that has no influence
                                                     on the following counter
                                                     values
       ${"-@F"%$_}|=                                 Merge the current node
                                                     ancestor string into the
                                                     successor
                                                     Notice that because this
                                                     is an |= the index
                                                     calculation was done
                                                     before the assignment
                                                     to $_ so $_ is still -i.
                                                     -n % -i = - (n % i), so
                                                     this is indeed the proper
                                                     index
                                     /.\b/g          As explained above this
                                                     gives the list of missing
                                                     higher and lower neighbours
                                                     but skips the start
$_=                                                  A map in scalar context
                                                     counts the number of
                                                     elements, so this assigns
                                                     the grand total to $_.
                                                     The -p implicitly prints

Обратите внимание, что замена /.\b/на /\b/решает версию этой проблемы в обе стороны, где Тарзан также берет путь0 to n-1

Некоторые примеры того, как выглядят строки предков (приведены по порядку n-1 .. 1):

n=23:
1
 1
  1
   1
    1
     1
      1
       1
        1
         1
          1
          11
         1  1
        1    1
       1      1
      11      11
     1          1
    11  1    1  11
   1              1
  1111  11  11  1111
 111111111  111111111
1111111111111111111111
edges=68

n=24:
1
 1
  1
   1
    1
     1
      1
       1
        1
         1
          1
           1
          1 1
         1   1
        1     1
       1       1
      1         1
     1  1     1  1
    1             1
   11    1   1    11
  1   1         1   1
 1        1 1        1
1                     1
edges=82

Mathematica, 113 103 102 байта

(r=Range[a=#-1];Length@Flatten[FindShortestPath[Graph[Thread[r<->Mod[a+1,r]]],#,#2]&@@{#,#-1}&/@r]-a)&

-10 байт благодаря @feersum; -1 байт благодаря @MartinEnder

Следующее выполняется намного быстрее (но, к сожалению, длиннее - 158 байт ):

(a=#;If[a<4,Part[-{1,1,1,-6},a],If[EvenQ@a,-2,1]]+a+4Total[Length@Complement[#,#2]&@@#&/@Partition[NestWhileList[Mod[a,#]&,#,#!=0&]&/@Range@Floor[a/2],2,1]])&

J 37 байт

[:+/2(-.+&#-.~)/\|:@(]|~^:(<@>:@[)i.)

Использование:

   f=.[:+/2(-.+&#-.~)/\|:@(]|~^:(<@>:@[)i.)
   f 10
32
   f every 1+i.20
0 1 2 6 6 12 12 18 22 32 24 34 34 36 44 58 50 64 60 66

Попробуйте это онлайн здесь.

JavaScript (ES6), 118 116 байт

n=>[...Array(n)].map(g=(_,i)=>i?[...g(_,n%i),i]:[],r=0).reduce(g=(x,y,i)=>x.map(e=>r+=!y.includes(e))&&i?g(y,x):x)|r

Отсутствие функции установки разницы действительно вредит, но некоторая креативная рекурсия немного уменьшает количество байтов. Редактировать: Сохранено 2 байта путем удаления ненужного параметра.