Tantangan dengan aturan sederhana tetapi algoritma non-sepele. :-)

Tugas

Ambil input dalam bentuk bilangan bulat yang dipisahkan oleh ruang:

N A B S

Di mana N adalah panjang sisi dari matriks persegi 2D yang diisi dengan angka unik (bilangan bulat) antara A dan B inklusif. Untuk setiap baris dan kolom dalam matriks ini, jumlah selalu sama: S. (Dengan kata lain, matriks adalah kuadrat semi-ajaib).

catatan:

Semua angka positif. Pengecualian adalah A, yang bisa 0.

Contohnya

Untuk

3 1 10000 2015

solusi yang valid adalah

Untuk

8 1 300 500

solusi yang valid adalah

Keluaran

Output Anda harus berupa tabel ASCII. Contoh untuk contoh pertama di atas:

 384  159 1472
1174  499  342
 457 1357  201

Bilangan bulat kanan diluruskan oleh spasi. Lebar setiap kolom adalah lebar bilangan bulat terbesar di kolom itu.

Mencetak gol

Ini adalah kode-golf , jadi kode terpendek dalam byte menang. Celah standar berlaku (terutama tentang built-in untuk mengatasi masalah ini). Anda tidak perlu peduli dengan input yang salah atau tidak mungkin (termasuk angka negatif). Harap berikan contoh keluaran dalam jawaban Anda (wajib) untuk contoh kedua di atas.

CJam, 119 91 byte

q~:M;),>:R;(:L{{R{ML)d/-Y#)mr}$L/L<2{{M1$:+-+}%z}*:U:+__O|=R*-}gU{:s_:,:e>f{Se[}}%zSf*N*}M?

Ini adalah pendekatan yang terbukti benar, non-deterministik.

Di desktop saya, test case kedua umumnya selesai dalam waktu kurang dari 10 menit.

Kasing pertama selesai secara instan. Cobalah online di juru bahasa CJam .

Contoh dijalankan

$ cjam grid.cjam <<< '8 1 300 500'
77  66  37 47  56  46 86  85
63 102  70 72  49  54 81   9
62  69  58 57  71  17 48 118
64  65  67 87  53  44 80  40
73  60  55 89  51  76 84  12
68  59  28 78  74  38 50 105
61  75  52 43 125  83 42  19
32   4 133 27  21 142 29 112

Ide

Tanpa batas waktu, kita bisa membuat kotak secara acak sampai menemukan kotak yang valid. Pendekatan ini dibangun di atas gagasan itu, menambahkan dua optimisasi:

• Alih-alih pseudo-acak menghasilkan persegi panjang sisi N , kami menghasilkan kuadrat panjang sisi N-1 , tambahkan satu kolom untuk membentuk persegi panjang N × (N-1) yang barisnya memiliki jumlah S , lalu satu baris untuk membentuk kuadrat dari sisi panjang N yang kolom memiliki sum S .

  Karena jumlah unsur semua kolom akan NS dan jumlah dari unsur-unsur yang pertama N-1 baris adalah (N-1) S , baris terakhir akan juga memiliki jumlah S .

  Namun, proses ini dapat menghasilkan matriks yang tidak valid, karena tidak ada jaminan bahwa semua elemen dari baris dan kolom terakhir akan unik atau termasuk dalam rentang [A ... B] .

• Memilih kuadrat bilangan bulat unik dalam [A ... B] dan panjang sisi N-1 secara seragam secara acak akan memakan waktu terlalu lama. Kami entah bagaimana harus memprioritaskan kotak yang memiliki peluang lebih tinggi untuk menghasilkan kuadrat panjang sisi N yang valid setelah menerapkan proses yang dirinci pada poin sebelumnya.

  Mengingat bahwa setiap baris dan kolom harus memiliki jumlah S , unsur-unsurnya memiliki rata-rata S / N . Jadi, memilih lebih banyak elemen yang mendekati rata-rata itu akan meningkatkan peluang kita.

  Untuk setiap I di [A ... B] , kami pseudo-secara acak memilih float antara 0 dan (I - S / N) ² + 1 dan mengurutkan elemen [A ... B] dengan mengapung yang dipilih. Kami menyimpan nomor N ² pertama dan menempatkannya dalam urutan membaca di kotak.

  Dengan asumsi distribusi yang seragam sempurna dari semua bilangan real antara 0 dan (I - S / N) ² +1 di setiap langkah, semua kotak memiliki probabilitas yang tidak nol untuk dipetik, yang berarti bahwa proses tersebut akan selesai pada akhirnya.

Kode

q~          e# Read all input from STDIN and evaluate it.
:M;         e# Save "S" in M and discard it from the stack.
),>:R;      e# Transform "A B" into [A ... B], save in R and discard.
(:L         e# Save "N - 1" in L and keep it on the stack.
{           e# If L is non-zero:
  {         e#   Do:
    R{      e#     For each I in R:
      ML)d/ e#       Compute M/Double(L+1).
      -Y#   e#       Subtract the result from I and square the difference.
      )mr   e#       Add 1 and pick a non-negative Double below the result.
    }$      e#     Sort the values of I according to the picks.
    L/      e#     Split the shuffled R into chunks of length L.
    L<      e#     Keep only the first L chunks.
    2{      e#     Do twice:
      {     e#       For each row of the  L x L array.
        M1$ e#       Push M and a copy of the row.
        :+- e#       Add the integers of the row and subtract their sum from M.
        +   e#       Append the difference to the row.
      }%    e#
      z     e#       Transpose rows and columns.
    }*      e#
    :U:+    e#     Save the result in U and concatenate its rows.
    __O|    e#     Push two copies. Deduplicate the second copy.
    =R*     e#     Push R if all elements are unique, an empty array otherwise.
    -       e#     Remove the result's elements from U's elements.
  }g        e#   If the resulting array is non-empty, repeat the loop.
  U{        e#   For each row in U:
    :s      e#     Convert its integers into strings.
    _:,     e#     Copy and replace each string with its length.
    :e>     e#     Compute the maximum length.
    f{      e#     For each integer, push the maximum length; then
      Se[   e#       Left-pad the integer with spaces to that length.
    }       e#
  }%        e#
  z         e#   Transpose rows with columns.
  Sf*N*     e#   Join columns by spaces, rows by linefeeds.
}M?         e# Else, push M.