Variant 2 HW - Problem 5 - Lines


1

Не мога да разбера къде бъркам. Минавам само 3/10 теста в BGCoder, като останалите 7 са с грешен отговор.

Ето кода: http://pastebin.com/gJB93zN8 (неактивен линк)

Ето условието:

Problem 5 – Lines

You are given a list of 8 bytes (positive integers in the range [0…255]) n0, n1, …, n7.

These numbers represent a square grid consisting of 8 lines and 8 columns.

Each cell of the grid could either be empty or full. The first line is represented by the bits of n0, the second – by the bits of n1 and so on, and the last line is represented by the bits of n7.

Each bit with value 1 denotes a full cell and each bit with value 0 denotes an empty cell.

The lines are numbered from the first (top) to the last (bottom) with the numbers 0, 1, …, 7.

The columns are numbered from right to left with the indices 0, 1, …, 7.

The figure shows a sample square grid and its representation by a sequence of 8 numbers n0, n1, …, n7:

 

7

6

5

4

3

2

1

0

 

0

 

 

 

 

 

 

 

n0 = 8

1

 

 

 

 

 

 

n1 = 72

2

 

 

 

 

 

 

 

n2 = 8

3

 

 

 

 

 

 

 

n3 = 8

4

 

 

 

 

 

 

 

n4 = 16

5

 

 

 

 

 

n5 = 28

6

 

 

 

 

n6 = 240

7

 

 

 

 

 

 

 

 

n7 = 0

 

A line is any sequence of full cells staying on the same row or column.

At the figure above we have two lines of 4 cells and two lines of 3 cells and one line of 1 cell.

You need to create a program that finds the longest line in the grid and the number of lines with the longest length.

At the figure we have two largest lines with length of 4 cells.

 




Отговори



1

Като за начало (не съм гледал напред) този код:

 

for (int i = 0; i < 8; i++)
            {
                int j = 7;
                while (bytes[i] != 0)
                {
                    bitMap[i, j] = bytes[i];
                    bytes[i] /= 2;
                    j--;
                }
            }
 
Не връща битове, а връща числа. За битове трябва да използваш % и остатъка от делението на 2, за да бъде 0 или 1. Пробвай да си изведеш на конзолата цялата матрима bitMap при въведени някакви стойности. Примерно за вход 1, 2, 3, 4, 5, 6, 7, 8, матрицата има вида:
 
00000001
00000012
00000013
00000124
00000125
00000136
00000137
00001248
 
Този резултат въобще не те устройва за целта. Трябва да преправиш кода на:
 
for (int i = 0; i < 8; i++)
            {
                int j = 7;
                while (bytes[i] != 0)
                {
                    bitMap[i, j] = bytes[i] % 2;
                    bytes[i] /= 2;
                    j--;
                }
            }
 
За напред не съм гледал, оправи го това и провери. :)
 
ЕДИТ: colBytes[j] += (int)Pow(2.0, i);
Този ред също дава грешка. Трябва да е Math.Pow.
 
ЕДИТ 2: Тествах ти задачата и в момента дава 80/100 след моята корекция. Това е така, защото ако имаш максимална линия от 1 "точка" програмата ти я изчислява два пъти в бройката (веднъж хоризонтално и веднъж вертикално), а трябва само 1 път. Това трябва да се съобрази и да се оправи. Успех :)

от ivaylo.kenov (30760 точки)


0
То може оттам да идва проблемът. Забравил съм да сложа % 2; Сега ще пробвам.

от denis.rizov (205 точки)

0
Аз съм си дефинирал моя функция Pow. Иначе го докарах до 8/10 като поправих генерирането на матрицата.

от denis.rizov (205 точки)



0

Колеги, мъча се с 5 задача Lines

Докарах я на 83 процента и се изчерпах от идеи. Дава грешки на 6 и 8 тест. Бихте ли помогнали.

http://pastebin.com/6BCFRq8W


от ivan.yosifov (679 точки)


0
Мога да ти кажа къде гърми, но ще трябва да го напишеш на ново, защото всички опити да ти го оправя само влошават положението. Просто е написано много по-сложно отколкото трябва да е. Гърми ако са само нули - дава 0 и 16, а трябва 0 и 0 Гърми ако имаш на 1 или 1 колона повече от 1 път максимум линията. Примерно ако макса ти е 2 и имаш 00110011 за този ред ти го брои само веднъж. Ако искаш мога да ти пратя вярно решение, но ще е друг алгоритъм. Твоето не многа да го измисля. Направих до 90 най-много :D


0
Колега аз видях на други колеги решенията. Бих погледнал и твоето, но искам да разбера как мога да го подобря. Как мога да преброя поредици от единици в един ред или една колона? Добре си ме насочил, че гърми когата има повече от една поредица в един ред или колона, но как да го натъманя да работи по моя начин?!

от ivan.yosifov (679 точки)



1

Здравей, Иване,

И аз преди малко решавах тази задача и сега хвърлих един поглед и на твоята. Можеш да разгледаш моята задача тук.

Сега да видим аз какво открих в твоята задача. Представи си, че имаш само следните линии:

1 1 0 0 1 1 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

Мисля, че няма смисъл да пиша 8 реда, да си представим, че всички надолу са нули и има само две линии на първия ред. Твоят алгоритъм започва с броене по редове и затова аз ще разгледам само за него, но е аналогично и за колоните. В този случай твоят алгоритъм тръгва и прави следното:

7бит = 1 -> lenght = 1, max = 1;    6бит = 1 -> lenght = 2, max = 2;

5бит = 0 - > lenght = 0, max = 2;   4бит = 0 -> lenght = 0, max = 2;

3бит = 1 -> lenght = 1, max = 2;    2бит = 1 -> lenght = 2, max = 2;

1бит = 0 - > lenght = 0, max = 2;   0бит = 0 ->lenght = 0, max = 2;

Излизаш от този цикъл и правиш score[max]++, което е равно на score[2] = 1 и също така topMax = 2. Сега най-дългата ти линия е записана в topMax с дължина две, но в score[2] е записана, че се среща само 1 път. Това не е вярно, нали? Как да го оправиш? Ами пробвай да вмъкнеш едно равенство между max и lenght където, ако пак попаднеш на линия с тази дължина да увеличаваш броя пъти, който се среща ; )

Успех!


от lostm1nd (846 точки)


1

http://pastebin.com/D0kimB1u.

Ето моето решение . В частният случай когато всички пълни клетки са с по 1 бит си признавам ,че погледнах от въпросните тестове ,които не излизаха и го правих.Иначе кода изкарваше 80 от100 .Сега е 100/100


от ivailoven (20 точки)


1
И аз така... и то бяха случайте когато най-дългата линия е 1 и я броеше 1 път като обхождам вертикално и 1 път като обхождам хоризонтално. ЗАщото видях че отговора е точно 2 пъти колкото трябва да бъде ... та if (maxLength == 1) { maxLineCounter /= 2:; }
го оправи :)

от vasil.subeff (80 точки)