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