Професионална програма
Loading...
+ Нов въпрос
MartinBG avatar MartinBG 3992 Точки
Best Answer

За тази задача в Judge има доста стегнат лимит по време, който е много лесно да бъде превишен с Java решение.

На мен ми се наложи да направя три версии с оптимизации, докато стигна от 80 до 100%, все заради забявяне с тестове 3 и 10.

Ето финалното ми решение: http://pastebin.com/FEpBP0wP 

То е с около 4 пъти по-бързо от стандартното (0.077s срещу 0.305s), като основното ускорение идва от (пре)използването на char array за стринговете, в който променям само по една буква на итерация. По-малко ускорение има от изнасянето на проверката за валидност на текущия символ преди следващия вложен цикъл, което спестява малко време (не се въртят долните цикли, ако ще получим невалиден стринг на края). 

С тези оптимизации кодът е с една идея по-трудно четим, но и Judge-a иска жертви :)

0
22/02/2017 12:26:46
Martin.T avatar Martin.T 35 Точки

С първото решение си на прав път използвай continue за да пропуснеш когато "b" е в играта :)

0
yanmark avatar yanmark 19 Точки

Вместо:

Scanner scan = new Scanner(System.in);

може да използвате:

BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

BufferedReader е доста  по бърз от Scanner

става въпрос за Java

 

0
yanmark avatar yanmark 19 Точки

Ето моето решение

http://pastebin.com/aaNN3ZjH

-1
staho avatar staho 8 Точки

И аз достигнах до тази задача, със същите проблеми на 3-ти и 10-ти тест. Бързото решениетo при мен беше да се махне print от цикъла и да се постави след края на всички цикли. За целта използвах StringBulider.

При стандартно решение с printf в последният цикъл, времената на 3-ти и 10-ти тест са: 0.314s  и 0.178s, докато със StringBuilder времената са:  0.028s и 0.023s

https://pastebin.com/X99Yam3H

0
01/05/2017 14:46:43
DilyanaGeorgieva avatar DilyanaGeorgieva 81 Точки

Колеги, аз с помощ от приятел,стигнах до следното решение, за 100/100:

https://pastebin.com/euiX2JKd

0
01/05/2017 15:18:05