Perisai Tentara Romawi

26

Pos kotak pasir (dihapus)

Formasi tentara Romawi kuno sangat terkenal di seluruh dunia. Dalam formasi-formasi ini legiun Romawi dikelompokkan dalam bentuk geometris (biasanya persegi panjang) melindungi sayap dan bagian superiornya menggunakan perisai mereka. Legionary di posisi interior menutupi bagian superior yang menempatkan perisai mereka di atas kepala mereka, legionary di sisi membawa 2 perisai: satu untuk melindungi bagian superior, dan satu atau lebih perisai untuk melindungi sisi (jika seseorang berada di sudut) dia punya 3 perisai, jika seseorang sendirian dalam formasi dia punya 5 perisai Ya, saya tahu tidak mungkin bagi manusia untuk membawa 5 perisai, tetapi entah bagaimana mereka melakukannya ). Dengan menggunakan formasi ini, semua legiun romawi melindungi diri mereka sendiri dan merupakan lawan tersulit pada saat itu.

Sejarah mengatakan ada seorang jenderal Romawi yang menyatakan bahwa bentuk formasi terbaik adalah kuadrat (jumlah legiun yang sama dalam baris dan kolom). Masalahnya adalah mencari tahu berapa banyak formasi (dan ukuran) yang harus dia pisahkan pasukannya untuk:

  • Jangan tinggalkan legiun dari formasi (meskipun ia mengakui formasi legiun tunggal)
  • Kurangi jumlah perisai yang diperlukan

Jenderal, setelah melakukan beberapa perhitungan dan matematika, ia menemukan bahwa cara terbaik untuk mencapai 2 kondisi ini adalah mulai dengan kotak terbesar yang mungkin, dan kemudian ulangi sampai tidak ada legiun yang tersisa .


Contoh:

Jika 35 legiun di pasukannya, formasi terdiri

  • Kotak 5x5 legiun (Ini adalah kotak terbesar yang mungkin).

Dengan legiun yang tersisa (10)

  • Kotak 3x3

Dengan legiun yang tersisa (1)

  • Persegi 1x1.

Pada akhirnya akan terlihat seperti ini:

   5x5      
* * * * *        3x3            
* * * * *       * * *      1x1  
* * * * *       * * *       *
* * * * *       * * *       
* * * * *               

Para legiun di posisi interior menutupi bagian superior yang menempatkan perisai mereka di atas kepala mereka . Mereka hanya membutuhkan 1 perisai.

* * * * *                   
* 1 1 1 *       * * *       
* 1 1 1 *       * 1 *       *
* 1 1 1 *       * * *       
* * * * *               

Legionaris di sayap membawa 2

* 2 2 2 *                   
2 1 1 1 2       * 2 *       
2 1 1 1 2       2 1 2       *
2 1 1 1 2       * 2 *       
* 2 2 2 *               

Jika seseorang berada di sudut dia punya 3 perisai

3 2 2 2 3               
2 1 1 1 2       3 2 3       
2 1 1 1 2       2 1 2       *
2 1 1 1 2       3 2 3       
3 2 2 2 3               

Jika seseorang sendirian dalam formasi dia memiliki 5 perisai

3 2 2 2 3               
2 1 1 1 2       3 2 3       
2 1 1 1 2       2 1 2       5
2 1 1 1 2       3 2 3       
3 2 2 2 3               

Formasi ini membutuhkan total 71 perisai.


Tantangan

  • Hitung jumlah perisai yang dibutuhkan untuk jumlah legiun X

Memasukkan

  • Jumlah legiun di tentara

Keluaran

  • Jumlah perisai yang dibutuhkan.

Uji Kasus

35 => 71
20 => 44
10 => 26
32 => 72

Luis felipe De jesus Munoz
sumber
11
Yah hasil google untuk "membawa 5 perisai" adalah Amazon.com : Best-selling Nipple Shield Carrying Case, Perfect...jadi saya kira saya tidak akan pernah benar-benar tahu. Apakah mereka benar-benar membawa 5 perisai - atau apakah ini membuat pertanyaan berhasil: P?
Magic Gurita Guci
1
@MagicOctopusUrn Saya cukup yakin Anda tahu jawabannya xD Saya tidak berpikir seseorang memiliki keberanian untuk pergi keluar dalam perkelahian dengan 5 perisai
Luis felipe De jesus Munoz
4
Saya tidak menghitung matematika dan perhitungan jenderal dengan tepat untuk menyimpulkan bahwa berulang kali mengambil kuadrat terbesar yang diperlukan meminimalkan perisai. Misalnya, 32 legiun dapat dibagi menjadi dua kotak 4 * 4 untuk 64 total perisai, daripada kotak 5 * 5 + 2 * 2 + 1 * 1 + 1 * 1 * 1 + 1 * 1 untuk 72 total perisai.
xnor
6
@ xnor Mungkin secara umum jendral tidak benar, tetapi jendral adalah jendral (walaupun kita tidak seharusnya menggeneralisasi).
pajonk
2
@AJFaraday Asterix dan musang tentara bayaran ?
Chris H

Jawaban:

14

Python 2 , 60 50 48 byte

def f(s):n=s**.5//1;return s and(n+4)*n+f(s-n*n)

Cobalah online!

Baru mengenal kode golf, tetapi memberikan ayunan terbaik saya!

Metode:

Jumlah di n^2 + 4nmana nmasing-masing angka kuadrat terbesar yang dijumlahkan ke input.

Edit 1

Dikurangi menjadi 50 byte berkat @Jonathan Frech!

Edit 2

Beralih int(s**.5)ke s**.5//1untuk menyimpan 2 byte berkat @ovs

Easton Bornemeier
sumber
8
Selamat datang di PPCG!
Luis felipe De jesus Munoz
2
Saya pikir n*nlebih pendek daripada n**2menghemat dua byte; lebih dari itu saya tidak bisa mengatakan karena saya tidak menulis python ...
Giuseppe
2
50 byte .
Jonathan Frech
2
int(s**.5)dapat disingkat menjadi s**.5//1.
Ovs
2
@mypetlion Ya. //adalah pembagian lantai di kedua Python 2 dan 3. 3**.5//1dievaluasi 1.0dalam kedua versi.
Ovs
11

R , 51 50 byte

f=function(x,y=x^.5%/%1)"if"(x,y^2+4*y+f(x-y^2),0)

Cobalah online!

Kuadrat dengan panjang sisi harus memiliki pelindung y 2 + 4 y . Kami mengurangi dengan kuadrat terbesar kurang dari atau sama dengan x sampai x adalah nol, mengumpulkan jumlah perisai saat kita pergi.yy2+4yxx

Bukti:

Dengan kuadrat sempurna dengan panjang sisi , kita perlu tepat 1 tameng untuk setiap anggota kuadrat. Selanjutnya, untuk setiap anggota di tepian, kita membutuhkan tameng tambahan. Ada ( y - 2 ) 2 anggota yang tidak ada di tepinya, jadi ada y 2 - ( y - 2 ) 2 anggota di tepinya. Akhirnya, untuk setiap sudut, kita membutuhkan perisai tambahan. Terlepas dari kasus di mana y = 1 , kita dapat menambahkan 4. Ini menyederhanakan ke y 2 + 4 y yang untungnya juga menghasilkan nilai yang benar dariy(y2)2y2(y2)2y=1y2+4y ketika y = 1 , memungkinkan kita untuk menggunakannya untuk semua y .5y=1y

Giuseppe
sumber
Anda dapat menyederhanakan penjelajahan banyak: setiap kotak atap perlu ditutup: , dan setiap kotak sisi perlu ditutup 4 y . Sekarang sudah jelas bahwa itu juga berfungsi dalam kasus prajurit tunggal. y24y
Todd Sewell
1
@ToddSewell yakin, itulah penjelasan Arnauld ini , dan itu adalah jauh lebih elegan, tapi ini adalah cara saya mendekati itu, jadi aku berpegang teguh pada itu! Untungnya, ini bukan pertanyaan bukti golf.
Giuseppe
10

JavaScript (ES7), 34 byte

f=n=>n&&(w=n**.5|0)*w+w*4+f(n-w*w)

Cobalah online!

Bagaimana?

Pada setiap iterasi, kami menghitung lebar dari kotak terbesar yang mungkin. Jumlah perisaiswuntuk kotak ini diberikan oleh:w=nsw

sw=w2+4w

Misalnya, untuk :w=3

(323212323)=(s3=21)(111111111)+(3²=9)(111000000)+(001001001)+(000000111)+(100100100)(4×3=12)

w=1s1=5

Arnauld
sumber
4

Julia 0,6 , 36 byte

!n=(s=isqrt(n))*s+4s+(n>0&&!(n-s*s))

Cobalah online!

n2+4n(n2)(n2)(n2)2n24(n-2)2perisai. Akhirnya, ada empat 3 di empat sudut, sehingga menambah 12 perisai.

(n-2)2+4(n-2)2+43=n2+4-4n+8n-16+12=n2+4n

Tidak Disatukan:

!n = begin       # Assign to ! operator to save bytes on function parantheses
  s = isqrt(n)   # Integer square root: the largest integer m such that m*m <= n
  s * s +
    4 * s +
      (n > 0 &&  # evaluates to false = 0 when n = 0, otherwise recurses
        !(n - s * s))
end

(Ini juga dapat dilakukan dalam 35 byte dengan n>0?(s=isqrt(n))*s+4s+f(n-s*s):0, tapi saya menulis ini untuk Julia 0.7 ingin menghindari peringatan penghinaan yang baru (membutuhkan ruang ?dan :).)

sundar - Pasang kembali Monica
sumber
Penjelasan lain yang terlalu rumit untuk jumlah perisai, lihat komentar saya pada jawaban @ Giuseppe.
Todd Sewell
2
@ToddSewell Ya, area + perimeter adalah cara yang lebih elegan untuk melihatnya. Namun saya tidak melakukannya, dan mirip dengan Giuseppe, maksud saya adalah untuk mendeskripsikan pendekatan saya daripada memberikan bukti formula yang paling rapi.
sundar - Reinstate Monica
3

Brachylog , 26 byte

0|⟧^₂ᵐ∋N&;N-ℕ↰R∧N√ȧ×₄;N,R+

Cobalah online!

0           % The output is 0 if input is 0
|           % Otherwise,
⟧           % Form decreasing range from input I to 0
^₂ᵐ         % Get the squares of each of those numbers
∋N          % There is a number N in that list
&;N-ℕ       % With I - N being a natural number >= 0 i.e. N <= I
            % Since we formed a decreasing range, this will find the largest such number
↰           % Call this predicate recursively with that difference I - N as the input
R           % Let the result of that be R
∧N√ȧ        % Get the positive square root of N
×₄          % Multiply by 4
;N,R+       % Add N and R to that
            % The result is the (implicit) output
sundar - Pasang kembali Monica
sumber
2

Retina 0.8.2 , 28 byte

.+
$*
(\G1|11\1)+
$&11$1$1
.

Cobalah online! Tautan termasuk kasus uji. Penjelasan:

.+
$*

Konversikan ke desimal.

(\G1|11\1)+

Cocokkan angka ganjil. Lulus pertama melalui grup, \1belum ada, jadi hanya \G1bisa cocok, yang cocok 1. Pertandingan berikutnya tidak dapat cocok \G1karena \Ghanya cocok di awal pertandingan, jadi alih-alih kami harus mencocokkan11\1 yang 2 lebih dari pertandingan sebelumnya. Kami mencocokkan angka ganjil sebanyak yang kami bisa, dan karenanya total pertandingan adalah angka kuadrat, sedangkan tangkapan terakhir adalah satu kurang dari dua kali lipat sisinya.

$&11$1$1

Tambahkan perisai samping untuk setiap pertandingan. $&aku sn2dan $1adalah2n-1 selagi kita membutuhkan n2+4n=n2+2+2(2n-1).

.

Jumlahkan dan konversikan ke desimal.

Neil
sumber
2

05AB1E , 17 byte

[Ð_#tïÐns4*+Šn-}O

Cobalah secara online atau verifikasi semua kasus uji .

Berfungsi karena ΔDtïÐns4*+Šn-}O( 15 byte ) sepertinya tidak berfungsi .. Coba online dalam mode debug untuk melihat apa yang saya maksud. Saya akan mengharapkan untuk pergi dari [45,'35',25]ke [45,10]setelah -dan iterasi berikutnya Δ, tapi rupanya itu membersihkan tumpukan kecuali untuk nilai terakhir dan menjadi [10], yang mengakibatkan 0 di akhir .. Tidak yakin apakah ini adalah perilaku atau bug yang dimaksudkan .. (EDIT: Ini dimaksudkan, lihat bagian bawah.)

Penjelasan:

Juga menggunakan w2+4w dimana w adalah lebar dalam satu lingkaran seperti kebanyakan jawaban lainnya.

[        }     # Start an infinite loop:
 Ð             #  Triplicate the value at the top of the stack
  _#           #  If the top is 0: break the infinite loop
 t             #  Take the square-root of the value
               #   i.e. 35 → 5.916...
  ï            #  Remove any digits by casting it to an integer, so we have our width
               #   i.e. 5.916... → 5
   Ð           #  Triplicate that width
    n          #  Take the square of it
               #   i.e. 5 → 25
     s         #  Swap so the width is at the top again
      4*       #  Multiply the width by 4
               #   i.e. 5 → 20
        +      #  And sum them together
               #   i.e. 25 + 20 → 45
 Š             #  Triple-swap so the calculated value for the current width
               #  is now at the back of the stack
               #   i.e. [35,5,45] → [45,35,5]
  n            #  Take the square of the width again
               #   5 → 25
   -           #  Subtract the square of the width from the value for the next iteration
               #   i.e. 35 - 25 → 10
          O    # Take the sum of the stack
               #   i.e. [45,21,5,0,0] → 71

EDIT: Rupanya perilaku yang saya jelaskan di atas Δdimaksudkan. Berikut dua alternatif 17-byte yang disediakan oleh @ Mr.Xcoder yang digunakan Δdengan meletakkan nilai di global_array (with ^) dan mengambilnya kembali setelahnya (with ¯):

ΔЈtïnα}¯¥ÄDt··+O

Cobalah secara online atau verifikasi semua kasus uji .

ΔЈtïnα}¯¥ÄtD4+*O

Cobalah secara online atau verifikasi semua kasus uji .

Kevin Cruijssen
sumber
2

dc , 25 byte

d[dvddSa*-d0<MLa+]dsMx4*+

Cobalah online!

Hitung perisai sebagai sum(n^2)(nomor asli) ditambah 4*sum(n)dengan mendorong salinan setiap panjang sisi persegi ke dalam register tumpukan asaat berjalan, kemudian menambahkan semua nilai dari register asebagai rekursi "membuka gulungan".

Sophia Lechner
sumber
2

APL (Dyalog Unicode) , 31 30 byte

{⍵<2:⍵×5⋄(S×S+4)+∇⍵-×⍨S←⌊⍵*.5}

Cobalah online!

-1 byte terima kasih kepada @jslip

Zacharý
sumber
0,5 -> .5 untuk 1 byte
jslip
Wow, bagaimana saya melewatkan itu
Zacharý
1

PHP , 67 byte

<?for($n=$argv[1];$w=(int)sqrt($n);$n-=$w**2)$a+=$w**2+$w*4;echo$a;

Untuk menjalankannya:

php -n <filename> <n>

Contoh:

php -n roman_army_shields.php 35

Atau Coba online!


Menggunakan -Ropsi, versi ini adalah 60 byte :

for(;$w=(int)sqrt($argn);$argn-=$w**2)$a+=$w**2+$w*4;echo$a;

Contoh:

echo 35 | php -nR "for(;$w=(int)sqrt($argn);$argn-=$w**2)$a+=$w**2+$w*4;echo$a;"

(di Linux, ganti "dengan ')


Catatan: Ini menggunakan jawaban hebat rumus Arnauld , saya tidak dapat menemukan yang lebih pendek dari itu.

Night2
sumber
1

Pyth , 19 byte

Fungsi rekursif, yang harus disebut menggunakan y(lihat tautan).

L&b+*Ks@b2+4Ky-b^K2

Coba di sini!

Pyth , 21 byte

Riwayat revisi cukup lucu, tetapi pastikan untuk mengunjunginya jika Anda ingin versi yang jauh lebih cepat :)

sm*d+4deeDsI#I#@RL2./

Coba di sini!

Penjelasan

sm*d+4deeDsI#I#@RL2./ Program lengkap, mari kita panggil input Q.
                   ./ Partisi integer dari Q. Menghasilkan semua kombinasi positif
                          bilangan bulat yang menambahkan hingga Q.
               @ RL2 Ambil akar kuadrat dari semua bilangan bulat dari setiap partisi.
             Saya # Simpan hanya partisi-partisi yang invarian di bawah:
          sI # Membuang semua yang bukan bilangan bulat. Ini pada dasarnya hanya menyimpan
                          partisi yang terbentuk sepenuhnya dari kotak yang sempurna, tetapi
                          alih-alih memiliki kotak sendiri, kita memiliki akarnya.
       eeD Dapatkan partisi (katakanlah P) dengan maksimum tertinggi.
 m Untuk setiap d dalam P ...
  * d + 4d ... Hasil d * (d + 4) = d ^ 2 + 4d, rumus yang digunakan dalam semua jawaban.
s Jumlahkan hasil pemetaan ini dan secara implisit menghasilkan.
Tuan Xcoder
sumber
1

Swift 4 , 111 99 84 78 byte

func f(_ x:Int)->Int{var y=x;while y*y>x{y-=1};return x>0 ?(y+4)*y+f(x-y*y):0}

Cobalah online!

Itu terasa ketika menerapkan integer square root secara manual jauh lebih pendek daripada built-in ...

Tidak Dijelaskan dan Dijelaskan

// Define a function f that takes an integer, x, and returns another integer
// "_" is used here to make the parameter anonymous (f(x:...) -> f(...))
func f(_ x: Int) -> Int {

    // Assign a variable y to the value of x

    var y = x

    // While y squared is higher than x, decrement y.

    while y * y > x {
        y -= 1
    }

    // If x > 0, return (y + 4) * y + f(x - y * y), else 0.

    return x > 0 ? (y + 4) * y + f(x - y * y) : 0
}
Tuan Xcoder
sumber