Loading...
Innos avatar Innos 419 Точки

[СофтУниада2017] Задачи, тестове, авторски решения

Колеги, материалите от състезателното програмиране от СофтУниада 2017 са качени:

Чувствайте се свободни да дискутирате задачите или решенията, както и да питате въпроси свързани с тях в тази тема.

6
Events
willystyle avatar willystyle 2472 Точки

Струва ми се, че задача 1 (Sum to 13), може да стане доста по-интересна, ако броя на числата (a, b, c) не е фиксиран на 3,

а се въвежда от потребителя (n), съответно (n1, n2, n3, ...). Ако някой има интересно решение, ще ми е интересно да го видя, моето е чрез опашка.

https://pastebin.com/hhK9cg8G

1
MartinBG avatar MartinBG 4803 Точки

Решението ти с опашка е оригинално!  yes

Не се сещам за по-ефективен алгоритъм от О(2^N), т.е. за 3 числа имаме 2 * 2 * 2 = 8 цикъла, за 4 стават 16, за 5 - 32, а при N = 32 вариантите са над 4 милиарда, което не е никак добре.

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

 

И за да не ми е съвсем безполезен поста, ще си позволя и коментар по кода ти. smiley

Четенето от конзолата може да го направиш и на един ред:

var number = Console.ReadLine()?.Split(' ').Select(int.Parse).ToArray();

 

0
17/01/2018 01:18:16
willystyle avatar willystyle 2472 Точки

Мерси  за коментара, нямам точки за да гласувам, но е интересен и полезен.

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

контролната сума, което пък го няма като условие на задачата и както казва Седжуик, не си усложнявайте задачата и живота :)

0
qwertyto avatar qwertyto 15 Точки

Написах едно решение О(n*m) CPU и О(m) памет, където n са броя числа и m e сумата на абсолютните им стойности. За много и малки числа е супер, като станат сумите милиони обаче става бавничко. Това е, ако на някой му е интересно.

2
KeepCoding avatar KeepCoding 554 Точки

Уменията придобити от Basics и Programming Fundamentals (първа част на Tech Module) ще бъдат ли достатъчни за едно прилично представяне на СофтУниада 2018 (състезателното програмиране)?

0
17/01/2018 21:23:11
MartinBG avatar MartinBG 4803 Точки

Зависи от дефиницията ти за "прилично представяне". smiley

Задачите са с нарастваща сложност, като последните няма как да бъдат решени без познаването и използването на правилните алгоритми, а това не се учи в нито един от модулите на основните програми на СофтУни. Веднъж годишно има курсове по "Data Structures" и "Algorithms", които препоръчвам силно на всеки, който иска да разбере какво наистина е програмирането.

3
KeepCoding avatar KeepCoding 554 Точки

Прав си колега! Не един път съм чувал, че колкото и да се променят технологиите и езиците, алгоритмите си остават едни и същи и научиш ли ги ще са ти от полза през цялата кариера като програмист. Така че този курс със сигурност ще бъде записан. А относно Data Structures си нямам на понятие какво се преподава, даже и като гледам програма на минало издание, но съм сигурен че са важни работи щом ми ги препоръчваш. Благодаря!

1
JivkoJelev avatar JivkoJelev 235 Точки

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

1
20/01/2018 12:56:57
willystyle avatar willystyle 2472 Точки

Здравейте,

бих искал да споделя едно решение на задача 8 Color Coding. Бях зациклил до 30/100 алгоритъма за брутфорс ми куцаше, разговаряйки с приятел, ми вика, що не го направиш на 2 реда с регекс. И се получи (въпреки, че избягва алгоритмичния проблем, решението е любопитно): https://pastebin.com/ef9jWUzq

0
willystyle avatar willystyle 2472 Точки

Здравейте, не съм сигурен, че темата все още се чете, но ще опитам.

Имам проблем със задача 6. Shop Keeper, чак започнах да имам известни съмнения за тест 10 (тестовете са публикувани по-горе в гитхъба). Реализирам доста прост алгоритъм, който хваща всички тестове, без 10-ти (реализацията е под 50 реда). На него, авторското решение дава: 1433 смени, а при мен са: 1431 (и в това се състои загадката, по-малко са, и в задачата се търсят най-малкото смени). Алгоритъма, който прилагам е, че при налагане на смяна, заменям стоката в магазина, която отсъства от бъдещи поръчки, ако такава няма със стоката с най-отдалечен индекс в поръчката. Часове не мога да си открия грешка в имплементацията.. Алгоритъма от авторското решение, ми идва малко трудно за разчитане (минава през няколко хеш сета). Възможно е моя алгоритъм да не е верен, или пък да имам грешка в имплементацията. 

Ако някой му се занимава и може да открие проблема, ето решението: https://pastebin.com/x11wi0BZ

Ако искате да пробвате тестовете, хардкодвайте стинговете от входа, понеже са големи за конзолата.

P.S. Това, което забелязвам за входа на тест 10, е че при дистинкт дължината е с 1 по-малка, т.е. има един продукт който се повтаря, в условието не е споменто как се процедира при такъв случай, ако замениш първия, влияе ли на другата стока.

P.S.2 Това е бил проблема, като се дистинктне първия ред, входа за стоките в магазина, отговора излиза, просто не е упоменато в условието на задачата, което е некоректно според мен, понеже повторената стока по-скоро би трябвало да се разглежда като самостоятелна позиция в магазина.

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