[СофтУниада2017] Задачи, тестове, авторски решения
Колеги, материалите от състезателното програмиране от СофтУниада 2017 са качени:
Чувствайте се свободни да дискутирате задачите или решенията, както и да питате въпроси свързани с тях в тази тема.
Колеги, материалите от състезателното програмиране от СофтУниада 2017 са качени:
Чувствайте се свободни да дискутирате задачите или решенията, както и да питате въпроси свързани с тях в тази тема.
Здравейте, не съм сигурен, че темата все още се чете, но ще опитам.
Имам проблем със задача 6. Shop Keeper, чак започнах да имам известни съмнения за тест 10 (тестовете са публикувани по-горе в гитхъба). Реализирам доста прост алгоритъм, който хваща всички тестове, без 10-ти (реализацията е под 50 реда). На него, авторското решение дава: 1433 смени, а при мен са: 1431 (и в това се състои загадката, по-малко са, и в задачата се търсят най-малкото смени). Алгоритъма, който прилагам е, че при налагане на смяна, заменям стоката в магазина, която отсъства от бъдещи поръчки, ако такава няма със стоката с най-отдалечен индекс в поръчката. Часове не мога да си открия грешка в имплементацията.. Алгоритъма от авторското решение, ми идва малко трудно за разчитане (минава през няколко хеш сета). Възможно е моя алгоритъм да не е верен, или пък да имам грешка в имплементацията.
Ако някой му се занимава и може да открие проблема, ето решението: https://pastebin.com/x11wi0BZ
Ако искате да пробвате тестовете, хардкодвайте стинговете от входа, понеже са големи за конзолата.
P.S. Това, което забелязвам за входа на тест 10, е че при дистинкт дължината е с 1 по-малка, т.е. има един продукт който се повтаря, в условието не е споменто как се процедира при такъв случай, ако замениш първия, влияе ли на другата стока.
P.S.2 Това е бил проблема, като се дистинктне първия ред, входа за стоките в магазина, отговора излиза, просто не е упоменато в условието на задачата, което е некоректно според мен, понеже повторената стока по-скоро би трябвало да се разглежда като самостоятелна позиция в магазина.