Если положительное целое число меньше 1000, отобразите все возможные прямоугольники с этой областью.

задача

Допустим, ввод равен 20. Мы можем сделать прямоугольник 20 × 1, 10 × 2 или 5 × 4, так что это правильный вывод:

********************

**********
**********

*****
*****
*****
*****

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

Прямоугольники могут появляться в любом порядке, ориентации или положении, но никакие два прямоугольника не могут пересекаться или касаться даже в углах. Следующее также верно:

********************

            ****
**********  ****
**********  ****
            ****
            ****

счет

Область ограничительной рамки (BBA) выходных данных - это область минимального прямоугольника, охватывающего все прямоугольники. В первом примере вывода размер равен 20 × 9, поэтому BBA равен 180. Во втором примере вывода размер равен 20 × 7, поэтому BBA составляет всего 140.

Найдите BBA выхода, когда входной сигнал равен 60, 111, 230, 400 и 480, и сложите их. Умножьте эту сумму на размер вашего кода в байтах. Результатом является ваш счет; выигрывает самый низкий балл.

правила

• Программа (или функция) должна выдавать правильные выходные данные для любого натурального числа ниже 1000.
• Вывод должен содержать только звездочки ( *), пробелы ( ) и переводы строк.
• Между прямоугольниками может быть любое пространство, но это имеет значение для BBA.
• Начальные или конечные строки или столбцы, если они имеют только пробелы, не учитываются в BBA.

Рубин, 228 байт * 21895 = 4992060

->n{a=(0..n*2).map{$b=' '*n}
g=0
m=n*2
(n**0.5).to_i.downto(1){|i|n%i<1&&(m=[m,n+h=n/i].min
g+=h+1
g<m+2?(a[g-h-1,1]=(1..h).map{?**i+$b}):(x=(m-h..m).map{|j|r=a[j].rindex(?*);r ?r:0}.max 
(m-h+1..m).each{|j|a[j][x+2]=?**i}))}
a}

Несколько изменений по сравнению с неоплаченным кодом. Самым большим является изменение значения переменнойm от высоты прямоугольника до высоты прямоугольника плюс n.

Тривиально, *40был изменен, *nчто означает много ненужных пробелов справа для большого n; и -2изменяется на то, 0что означает, что прямоугольники, нанесенные поперек нижней части, всегда пропускают первые два столбца (это приводит к ухудшению упаковки для чисел, чья единственная факторизация (n/2)*2)

объяснение

Я наконец нашел время, чтобы вернуться к этому.

Для данного nнаименьшего поля должно быть достаточно места как для самого длинного прямоугольника, так 1*nи для самого квадратного прямоугольника x*y. Должно быть очевидно, что наилучшая компоновка может быть достигнута, если оба прямоугольника имеют длинные стороны, ориентированные в одном направлении.

Игнорируя требование пробела между прямоугольниками, мы находим, что общая площадь равна (n+y)*x = (n+n/x)*xили n*(x+1). В любом случае, это оценивается как n*x + n. Включая пробельные символы, мы должны включить дополнительные, xесли мы помещаем прямоугольники вплотную или nразмещаем прямоугольники рядом. Поэтому первое предпочтительнее.

Это дает следующие нижние границы (n+y+1)*xдля области поля:

n     area
60    71*6=426
111  149*3=447
230  254*10=2540
400  421*20=8240
480  505*20=10100

Это предполагает следующий алгоритм:

Find the value (n+y+1) which shall be the field height
Iterate from the squarest rectangle to the longest one
  While there is space in the field height, draw each rectangle, one below the other, lined up on the left border.
  When there is no more space in the field height, draw the remaining rectangles, one beside the other, along the bottom border, taking care not to overlap any of the rectangles above.
  (Expand the field rightwards in the rare cases where this is necessary.)

На самом деле можно получить все прямоугольники для требуемых тестовых случаев в указанных выше нижних границах, за исключением 60, что дает следующий результат 71 * 8 = 568. Это можно немного улучшить до 60 * 9 = 540, переместив два самых тонких прямоугольника вправо на один квадрат, а затем вверх, но экономия минимальна, поэтому, вероятно, не стоит никакого дополнительного кода.

10
12
15
20
30
60
******
******
******
******
******
******
******
******
******
******

*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
       *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
       *
***    *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *

Это дает общую площадь 21895.

Код без правил

f=->n{
  a=(0..n*2).map{' '*40}                                      #Fill an array with strings of 40 spaces
  g=0                                                         #Total height of all rectangles
  m=n                                                         #Height of squarest rectangle (first guess is n) 
  (n**0.5).to_i.downto(1){|i|n%i<1&&(puts n/i                 #iterate through widths. Valid ones have n%i=0. Puts outputs heights for debugging.
    m=[m,h=n/i].min                                           #Calculate height of rectangle. On first calculation, m will be set to height of squarest rectangle.
    g+=h+1                                                    #Increment g
    g<n+m+2?                                                  #if the rectangle will fit beneath the last one, against the left margin
      (a[g-h-1,1]=(1..h).map{'*'*i+' '*40})                      #fill the region of the array with stars
    :                                                         #else  
      (x=(n+m-h..n+m).map{|j|r=a[j].rindex('* ');r ?r:-2}.max    #find the first clear column
      (n+m-h+1..n+m).each{|j|a[j][x+2]='*'*i}                    #and plot the rectangle along the bottom margin
    )
  )}
a}                                                            #return the array

puts f[gets.to_i]

CJam, 90385 * 31 байт = 2801935

q~:FmQ,:){F\%!},{F\/F'**/N*NN}/

Проверьте это здесь. Используйте этот скрипт для расчета BBAs.

Это просто наивное решение, чтобы начать работу.

Рубин, 56 байт

90385 * 56 = 5061560 при условии, что результат такой же, как у Мартина (я так думаю).

->n{1.upto(n){|i|i*i<=n&&n%i==0&&puts([?**(n/i)]*i,'')}}

Вот еще одна полезная функция, в полезной тестовой программе

f=->n{1.upto(n){|i|i*i<=n&&n%i==0&&print(n/i,"*",i,"\n")};puts}

f[60];f[111];f[230];f[400];f[480]

Который дает следующий вывод, для справки:

60*1
30*2
20*3
15*4
12*5
10*6

111*1
37*3

230*1
115*2
46*5
23*10

400*1
200*2
100*4
80*5
50*8
40*10
25*16
20*20

480*1
240*2
160*3
120*4
96*5
80*6
60*8
48*10
40*12
32*15
30*16
24*20