Виды гусей, известные как Алекс А , известны тем, что живут в треугольных сетках, состоящих из 64 ячеек:

^{(Фото взято из этой несвязанной проблемы Project Euler .)}

Мы будем маркировать каждую ячейку с номерами , 0чтобы 63начиная с верхнего ряда , а затем двигаясь слева направо в каждой строке ниже этого. Таким образом, верхняя ячейка 0и нижняя правая ячейка 63.

Каждая ячейка имеет три границы. Мы можем пометить каждую границу в форме, a,bгде aи bявляются номерами ячеек, которые разделяют эту границу. Например, граница между ячейкой 0и 2будет названа 0,2или 2,0(не имеет значения, в каком порядке вы их разместите).

Система маркировки границ на самом краю сетки различна, поскольку ячейки на краю сетки имеют границу, которую они не разделяют с другими ячейками. Если граница является только частью одной ячейки, мы будем использовать букву X. Например, три границы ячейки 0являются 0,2, 0,Xи 0,X.

Некоторые клетки содержат гусей . Тем не менее, эти гуси будут убиты злыми лисами (которые приходят из-за пределов сетки), если вы не защитите их. И если все гуси умрут, BrainSteel будет грустным. Поэтому мы напишем программу, которая строит заборы вокруг гусей, чтобы защитить их от лис. Гуси должны существовать в одном полностью огороженном многоугольнике. Наш бюджет заборов довольно низок, поэтому используйте как можно меньше заборов.

Описание входа

Список чисел, разделенных запятой, от 0до 63, представляющих ячейки, которые содержат гусей. Пример:

6,12

Описание выхода

Список границ, на которых должны быть построены заборы, чтобы успешно защитить гусей. Это должно быть наименьшее количество возможных заборов. Пример:

5,6 6,7 11,12 12,13 

C #, 530 байт

Завершить программу на C #, получить ввод в виде одной строки из STDIN и вывести одну строку в STDOUT с завершающим "".

Это довольно долго ... и имеет слишком много повторений x / y / z, но я не смог до сих пор свести его к чему-то разумному, и сдать экзамен через 2 часа может вернуться к этому завтра.

using Q=System.Console;class P{static void Main(){int q=9,w=0,e=9,r=0,t=9,u=0,i=0,x=0,y=0,z=0,p=0;System.Action V=()=>{z=(int)System.Math.Sqrt(i);p=(x=i-z*z)%2;x/=2;y=(++z*z--+~i)/2;},W=()=>{Q.Write(i+","+(x<0|y++<0|z>7?"X":""+(z*z+2*x+1-p))+" ");};foreach(var g in Q.ReadLine().Split(',')){i=int.Parse(g);V();q=q>x?x:q;w=w<x?x:w;e=e>y?y:e;r=r<y?y:r;t=t>z?z:t;u=u<z?z:u;}for(i=64;i-->0;){V();if(!(x<q|x>w|y<e|y>r|z<t|z>u))if(p>0){if(y==r)W();if(x++==w)W();x--;if(z--==t)W();}else{if(y--==e)W();if(x--==q)W();x++;if(z++==u)W();}}}}

Эта диаграмма объясняет большую часть того, что происходит.

Признайте, что из-за того, что у нас не может быть секций шириной 0, «шестиугольник» всегда будет самой дешевой формой (и он дает гусям максимум места для перемещения).

Программа работает, сначала переводя все индексы входных ячеек в координаты x / y / z и находя min / max каждого из x / y / z.

z = floor(root(i))
x = floor((i - z^2) / 2)
y = floor((z+1)^2 - i - 1) / 2)
p = (i - z^2) % 2

Затем он проходит через каждый индекс ячейки и проверяет, подходит ли он в границу «шестиугольника», которую мы описали. Если это так, то он проверяет, находится ли он на каком-либо из крайних ребер границ (т. Е. X = xmin или y = ymax), и добавляет соответствующие ребра, если это так. Он должен определить индекс края, с которым он рядом. Для x и z мы просто увеличиваем / уменьшаем их по своему усмотрению, а затем используем следующую формулу:

i = z^2 + 2*x + (1-p)

Обратите внимание, что «четность» всегда меняется, и что у не участвует. Для y нам не нужно ничего менять, но код немного беспорядочный, потому что он должен выполнять проверку границ "треугольника", чтобы определить, должна ли ячейка по соседству быть "X" или нет.

Пример решения (Клетки с гусями в трех углах):

Input
2,50,62

Output
62,63 61,X 59,X 57,X 55,X 53,X 51,X 50,49 48,X 36,X 35,X 25,X 24,X 16,X 15,X 9,X 8,X 4,X 3,X 2,0 1,X 

Код Tidier с комментариями:

using Q=System.Console;

class P
{
    static void Main()
    {
        int q=9,w=0,e=9,r=0,t=9,u=0, // min/max x/y/z/ (init min high, and max low)
        i=0, // index of cell we are looking at
        x=0,y=0,z=0,p=0; // x,y,z dimension

        System.Action V=()=>
            { // translates the index into x/y/z/p
                z=(int)System.Math.Sqrt(i);
                p=(x=i-z*z)%2; // 'parity'
                x/=2; // see p assignment
                y=(++z*z--+~i)/2; // ~i == -i - 1
            },
            W=()=>
            { // writes out the edge of i, and the cell described by x/z/inverse of p   (the inversion of p handles y +/-)
                Q.Write(i+","+ // write out the edge
                        (x<0|y++<0|z>7?"X":""+(z*z+2*x+1-p)) // either X (if we go out of 'trianlge' bounds), or we translate x/z/inverse of p into an index
                        +" "); // leaves a trailing space (as shown in example output)
            };

        foreach(var g in Q.ReadLine().Split(',')) // for each cell with geese
        {
            i=int.Parse(g); // grab index of cell
            V(); // compute x/y/z/p
            q=q>x?x:q; // sort out mins/maxes
            w=w<x?x:w;
            e=e>y?y:e;
            r=r<y?y:r;
            t=t>z?z:t;
            u=u<z?z:u;

            // code like the above suggests a solution with a couple of arrays would be better...
            // I've not had success with that yet, but maybe in a couple of days I will try again
        }

        for(i=64;i-->0;) // for each cell
        {
            V(); // compute x/y/z/p
            if(!(x<q|x>w|y<e|y>r|z<t|z>u)) // if we are inside the 'hex' bounds
                if(p>0)
                { // x max, y max, z min
                    // these checks check that we are on the extremes of the 'hex' bounds,
                    // and set up the appropriate vars for W calls to put the edges in
                    // must do y first, because W modifies it for us (saves 2 bytes in the next block)
                    if(y==r) // don't need the ++ (can't go out of 'trianlge' bounds)
                        W();
                    if(x++==w)
                        W();
                    x--;
                    if(z--==t)
                        W();
                    //z++; not used again
                }
                else
                { // x min, y min, z max
                    if(y--==e) // do need the -- (used for 'trianlge' bounds checking)
                        W();
                    // y is reset in W, as such
                    if(x--==q)
                        W();
                    x++;
                    if(z++==u)
                        W();
                    //z--; not used again
                }
        }
    }
}