Професионална програма
Loading...
+ Нов въпрос
ArmenPotourlyan+deleted! avatar ArmenPotourlyan+deleted! 488 Точки

[Discussion][Exam Problems] Programming Basics Exam 26 April 2015 Morning - Problem{5} - Bits at Crossroads

Здравейте, колеги,

Струва ми се, че тест №7 за тази задача не е коректен. Ето линкове към условието и съдията: Условие / Judge.

In :

9
1 6
1 4
1 2
1 0
end

Out :

170
85
170
341
170
341
162
321
128
13

Битово представяне на изхода:

0‭ 1 0 1 0 1 0 1 0‬    // 3 кръстопътя
‭0 0 1 0 1 0 1 0 1‬    // 4 кръстопътя
0‭ 1 0 1 0 1 0 1 0‬    // 3 кръстопътя
‭1 0 1 0 1 0 1 0 1‬ ‬   // 2 кръстопътя
0‭ 1 0 1 0 1 0 1 0‬ ‬   // 1 кръстопът
1 0 1 0 1 0 1 0 1‬ ‬   // 0 кръстопътя
0‭ 1 0 1 0 0 0 1 0‬ ‬   // 0 кръстопътя
1 0 1 0 0 0 0 0 1‬ ‬   // 1 кръстопът
0‭ 1 0 0 0 0 0 0 0‬ ‬   // 1 кръстопът

Със зелен фон са отбелязани кръстопътите, които са дадени от входните данни. Със сив фон са дадени кръстопътите, които отчита авторското решение. Моята програма отчита още два кръстопътя - тези с червен фон. Така, с тези два, броят става 15, а не 13, както е дадено в изхода на теста. Някой би ли ми обяснил каква е логиката последните два кръстопътя да не са валидни?

Тагове:
2
Programming Basics 23/04/2016 11:41:45
dim4o avatar dim4o 288 Точки
Best Answer

Представи си, че са ти дадени някакви точки и от тях тръгват прави, които са успоредни на осите на някаква двуизмерна координатна система. В случая е завъртяна на 45 градуса. Търсят се всички пресечни точки на тези прави. В този контекст червените единици са части от успоредни прави и затова не се броят за кръстопътища. Това мисля, че се подразбира от условието, защото ясно е показано как се констуира път. В случая ти създаваш нов път, който не съществува. Най-вероятно си конструирал и решението си като минаваш през всяка клетка и проверяваш двата и диагонала. По-скоро идеята е да почнеш да строиш пътища, тръгвайки от началните точки и когато срешнеш друг път да го броиш за кръстовище. Този алгоритъм ще ти намери всички пресечни точки.

2
ArmenPotourlyan+deleted! avatar ArmenPotourlyan+deleted! 488 Точки

Да, колега,

Някакси не го видях, не го разбрах от условието. Например, ако беше написано "Търсят се всички пресечни точки на тези прави", веднага щеше да ми светне. Или  "Търсят се всички пресечни точки на тези пътища". Помислих, че могат да се получат нови прави или пътища и съответно нови пресечни точки. Е, да разбереш условието също е част от играта, така че грешката е моя laugh

2
23/04/2016 12:49:33
dim4o avatar dim4o 288 Точки

Да, напълно си прав. Аз съм измислял задачата и не твърдя, че всичко е идеално. Просто идеята ми се стори доста интересна. Задачата е минала редакция и предполагам са отстранили някои неясноти по условието, но сега виждам, че в секцията Output е написано: "On the last line print the total count of all crossroads on the board", което е може да е подвеждащо наистина. В моя вариант на условието текста беше: "The last line is number of the all patches intersection(crossroads)", което според мен е по-ясно. Но въпреки това би трябвало да става ясно от дефиницията "A crossroad is an intersection between two roads."

По принцип при тези проблеми няма някаква рецепта за тълкуването на условието. Понякога спазването на буквата на му може да те подведе да мислиш в някакви извратени посоки, които са извън идеята на задачата, а в други случаи може да се окаже решаваща и да опрости много целия проблем. Аз също много пъти съм се обърквал по подобен начин. Ако имаш и най-малки съмнения и си на изпит е най-добре да питаш някой оторизиран да отговаря на такива въпоси.

3
24/04/2016 11:26:47
aanguelov avatar aanguelov 219 Точки

На отбелязаните с червено битове имаш два диагонала от горе дясно към долу ляво. За да са кръстопътища, ти трябват и съответните диагонали в обратната посока. Точно на дадената от теб схема се вижда ясно че не са кръстопътища.

0
ArmenPotourlyan+deleted! avatar ArmenPotourlyan+deleted! 488 Точки

Тоест вторичните пътища не се броят така ли да разбирам?! Гледат се само тези пътища, които са дадени като вход.

Би ли ми посочил къде в условието е казано, че вторично генерираните пътища не са валидни?

1
Nikola_Andreev avatar Nikola_Andreev 671 Точки

За пръв път разглеждам задачата и като прочета условието, оставам с впечатлението че тези позиции който са на крайните редове, не се броят. Ако трябва да се броят и те, значи в условието на фигура 2, на позиции (0,5) и (5,0) също трябва да има кръстопът.

 

 

1
ArmenPotourlyan+deleted! avatar ArmenPotourlyan+deleted! 488 Точки

За мен не е валиден този кръстопът, на който един от диагоналите не продължава до края с единици. Според колегата aanguelov, (и изглежда той е прав и така е замислена задачата), са валидни само кръстопътите, които са вследствие на пресичане на оригиналните пътища, зададени във входните данни.

1
23/04/2016 12:20:09
Nikola_Andreev avatar Nikola_Andreev 671 Точки

Да, явно е така.

1
vancho avatar vancho 430 Точки

Аз я реших от раз, ето линк, може да ти дойде нещо на ум. http://pastebin.com/uEb6gRsB Аз го реших като сумирам броя на пресечните точки на единиците и бройката на входните точни. wink

1
ArmenPotourlyan+deleted! avatar ArmenPotourlyan+deleted! 488 Точки

Търсиш дали вече не е единица въпросната позиция и ако е вдигаш броя на пресечните точки. Да, готино решение.

 

Но проблема в моя случай беше, че аз смятах, че първоначалните пътища могат да образуват вторични пътища - диагонали с единици открай до край, и съответно пресечните им точки с оригиналните пътища също съм ги смятал. Явно не съм прав.

1
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.