Swingers anggur Olimpiade melakukan rutinitas mereka di pohon standar. Secara khusus, Pohon Standar nmemiliki simpul untuk 0naik n-1dan ujung-ujungnya menghubungkan setiap simpul bukan nol ake simpul n % adi bawahnya. Jadi, misalnya, Standard Tree 5 terlihat seperti ini:

3
|
2   4
 \ /
  1
  |
  0

karena sisa ketika 5 dibagi 3 adalah 2, sisanya ketika 5 dibagi 2 atau 4 adalah 1, dan sisanya ketika 5 dibagi 1 adalah 0.

Tahun ini, Tarzan akan mempertahankan emasnya dengan rutinitas baru, yang masing-masing dimulai pada titik n - 1, berayun ke titik n - 2, terus ke titik n - 3, dll, sampai akhirnya ia turun ke titik 0.

Skor untuk rutin adalah jumlah skor untuk setiap ayunan (termasuk turun), dan skor untuk ayunan adalah jarak di dalam pohon antara titik awal dan titik akhir. Dengan demikian, rutinitas Tarzan di Standard Tree 5 memiliki skor 6:

• ayunan dari 4ke 3skor tiga poin (bawah, atas, atas),
• ayunan dari 3ke 2skor satu poin (bawah),
• ayunan dari 2ke 1skor satu poin (bawah), dan
• turun dari 1ke 0skor satu poin (turun).

Tulis program atau fungsi yang, dengan bilangan bulat positif n, menghitung skor rutin Tarzan di Pohon Standar n. Input dan output sampel:

 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

Aturan dan penilaian kode seperti biasa untuk golf kode .

C, 98 97 byte

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;}

Ini menghitung jarak antara setiap pasangan poin dengan rumus berikut:

• Tambahkan jarak dari root ke simpul A
• Tambahkan jarak dari root ke simpul B
• Kurangi 2 * panjang akar umum A dan B

Ini memiliki keuntungan bahwa ketika diterapkan ke semua pasangan, itu sama dengan:

• Tambahkan 2 * jarak dari root ke setiap node
• Kurangi 2 * panjang akar umum dari setiap pasangan simpul
• Kurangi jarak dari root ke simpul pertama
• Kurangi jarak dari root ke node terakhir

Untuk membuat logikanya lebih sederhana, kita asumsikan kita beralih dari simpul 0 ke simpul n-1, daripada n-1 ke 0 seperti yang dinyatakan oleh pertanyaan. Jarak dari simpul akar ke simpul 0 jelas 0 (mereka sama). Dan kita dapat melihat bahwa untuk sebagian besar pohon, jarak dari simpul terakhir ke root adalah 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

Ini berarti kami memiliki beberapa kasus khusus (n <2) tetapi kami dapat menjelaskannya dengan cukup mudah.

Kerusakan:

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
}

_{Terima kasih @feersum untuk 1 byte disimpan}

Bonus: Pohon!

Saya menulis program cepat dan kotor untuk melihat seperti apa pohon-pohon ini. Inilah beberapa hasilnya:

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 byte

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 byte

Termasuk +2 untuk -ap

Jalankan dengan ukuran pohon di 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

Penjelasan

Jika Anda menulis ulang pohon itu

3
|
2   4
 \ /
  1
  |
  0

ke satu tempat setiap node berisi himpunan semua leluhur dan dirinya sendiri:

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

Kemudian kita bisa menggambarkan misalnya semua node path dari 4 ke 3 sebagai:

• Semua node yang berisi 3 tetapi tidak 4 (turun dari 3)
• Semua node yang berisi 4 tetapi tidak 3 (turun dari 4)
• Node tertinggi yang berisi 3 dan 4 (gabungan)

Jumlah tepi adalah satu kurang dari jumlah node sehingga kita dapat menggunakannya untuk mengabaikan titik bergabung, sehingga jumlah tepi pada jalur dari 4 ke 3 adalah 3 karena:

• Jumlah node yang berisi 3 tetapi tidak 4: 2 node
• Jumlah node yang berisi 4 tetapi tidak simpul 3: 1

Perhatikan bahwa ini juga berfungsi untuk jalur yang langsung turun ke targetnya, misalnya untuk jalur dari 3 ke 2 jumlah tepi adalah 1 karena:

• Jumlah node yang berisi 2 tetapi tidak 3: 0 node
• Jumlah node yang berisi 3 tetapi tidak 2: 1 node

Kami kemudian dapat menjumlahkan semua kombinasi ini.

Jika Anda melihat hanya sebuah simpul, misalnya simpul 2 dengan leluhur yang ditetapkan {2,3}. Node ini akan berkontribusi sekali ketika memproses path 2 to 1karena mengandung 2 tetapi tidak 1. Tidak akan memberikan kontribusi apa pun untuk path 3 to 2karena memiliki 2 dan 3, tetapi akan berkontribusi sekali ketika memproses path 4 to 3karena memiliki 3 tetapi no 4. Secara umum angka dalam set leluhur dari sebuah simpul akan berkontribusi satu untuk setiap tetangga (satu lebih rendah dari yang lebih tinggi) yang tidak ada dalam set. Kecuali untuk elemen maksimum (4 dalam hal ini) yang hanya berkontribusi untuk tetangga rendah 3 karena tidak ada jalan5 to 4. Simular 0 adalah satu sisi, tetapi karena 0 selalu di akar pohon dan berisi semua angka (itu adalah gabungan akhir dan kami tidak menghitung bergabung) tidak pernah ada kontribusi dari 0 sehingga lebih mudah untuk meninggalkan simpul 0 sama sekali.

Jadi kita juga bisa menyelesaikan masalah dengan melihat set leluhur untuk setiap node, menghitung kontribusi dan menjumlahkan semua node.

Untuk dengan mudah memproses tetangga saya akan mewakili set leluhur sebagai string ruang dan 1 di mana masing-masing 1 pada posisi p menyatakan bahwa n-1-p adalah leluhur. Jadi misalnya dalam kasus kami n=51 pada posisi 0 menunjukkan 4 adalah leluhur. Saya akan meninggalkan ruang trailing. Jadi representasi sebenarnya dari pohon yang akan saya bangun adalah:

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

Perhatikan bahwa saya meninggalkan simpul 0 yang akan diwakili oleh "11111"karena saya akan mengabaikan simpul 0 (tidak pernah berkontribusi).

Nenek moyang tanpa tetangga yang lebih rendah sekarang diwakili oleh akhir dari urutan 1. Nenek moyang tanpa tetangga yang lebih tinggi sekarang diwakili oleh permulaan urutan 1, tetapi kita harus mengabaikan permulaan urutan pada awal string karena ini akan mewakili jalur 5 to 4yang tidak ada. Kombinasi ini sangat cocok dengan regex /.\b/.

Membangun string leluhur dilakukan dengan memproses semua node dalam urutan n-1 .. 1dan ada yang menetapkan 1 di posisi untuk node itu sendiri dan melakukan "atau" ke dalam keturunan.

Dengan semua itu, program ini cukup mudah dimengerti:

-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

Perhatikan bahwa mengganti /.\b/dengan /\b/menyelesaikan versi bolak-balik dari masalah ini di mana tarzan juga mengambil jalannya0 to n-1

Beberapa contoh bagaimana string leluhur terlihat (diberikan secara berurutan 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 byte

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

-10 byte terima kasih kepada @feersum; -1 byte terima kasih kepada @MartinEnder

Berikut ini jauh lebih cepat (tapi lebih lama, sayangnya, pada 158 byte ):

(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 byte

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

Pemakaian:

   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

Cobalah online di sini.

JavaScript (ES6), 118 116 byte

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

Kurangnya fungsi perbedaan set benar-benar menyakitkan, tetapi beberapa rekursi kreatif mengurangi jumlah byte sedikit. Sunting: Disimpan 2 byte dengan menghapus parameter yang tidak perlu.