[Exam Problems] C# Basics Problem{4} Longest Alphabetical Word

nick.genov 104 Точки

[Exam Problems] C# Basics Problem{4} Longest Alphabetical Word

Здравейте.

Имам съмнение, че има грешка в тест 7 в Judge системата за тази задача.

В тест 7 входът е:

wafibcnopqdeklrxjstghuvyzm
5

В резултат на това имаме матрица:

w a f i b
c n o p q
d e k l r
x j s t g
h u v y z

Според Judge системата, верният отговор е cnopq (вторият ред), а според мен верният отговор е deklr (третият ред). Ето теглото на двете думи (сумата от ASCII кодовете на всеки от символите в думата):

deklr = 100 + 101 + 107 + 108 + 114 = 530

cnopq = 99 + 110 + 111 + 112 + 113 = 545

В условието на задачата пише: "If more than one longest alphabetical words exist in the block, find the smallest of them in the standard lexicographical order". Теглото на символите в deklr е по-малко.

Пропускам ли нещо в тълкуванието на условието, или наистина има грешка?

Mod Edit: Моля, спазвайте правилата на форума при пускане на нова тема.

Тагове:

05/12/2014 16:56:15 Programming Basics 05/12/2014 19:35:09

Filkolev 4482 Точки

Best Answer

lexicographical order ще рече коя от думите е преди другата по азбучен ред, т.е. в случая "c" е преди "d" по лексикографска подредба и затова snopq е отговорът. Не се смятат сборове на кодове от ASCII.

05/12/2014 17:19:55

nick.genov 104 Точки

Извинявам се за пропуска при оформлението на темата.

Filkolev, благодаря!

05/12/2014 18:30:59 05/12/2014 22:17:19

nick.genov 104 Точки

Успешно получих 100 точки :) Ето и моето решение: http://pastebin.com/EBPiVDKp Не е толкова кратко като авторското, но поне за мен е по-лесно за разбиране какво става.

На кратко - правя матрица от символи (char[]) и я пълня с буквите на думата. След това проверявам четирите посоки с 4 блока код с вложени цикли. Изнесох проверката коя дума е по рано в лексикографската подредба в отделен метод, че щеше да стане 300 реда код :)

Поздрави :)

05/12/2014 22:11:58 05/12/2014 22:14:19

Filkolev 4482 Точки

Има готов метод, който връща кой от два стринга е пръв по лексикографска подредба:

if(String.Compare(str1,str2) < 0) - това е проверка дали str1 е преди str2.

Само това ако приложиш и махнеш ненужните методи ще смъкнеш 40 реда от кода.

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

05/12/2014 22:52:26

nick.genov 104 Точки

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

05/12/2014 23:01:21 05/12/2014 23:01:43

dim4o 288 Точки

Не се сещам как можеш да провериш и четирите посоки едновременно, но можеш да проверяваш само в с 2 посоки (например дясно и долу) и после да добавяш в списък всеки резултат - прав и обърнат. Пример: получил си стринг "abcd", добавяш "abcd" и "dcba", защото ако ходиш в четирите посоки така или иначе ще трябва да добавиш и "dcba". Така в този пример е излишно да проверяваш наляво и нагоре.

06/12/2014 10:26:11