Loading...
BozhidarKlouchek avatar BozhidarKlouchek 24 Точки

Roxettes

Опитвам се от както е пуснат JA да я реша тази задача, но все ми дава 50/100.
Дава ми една червена звездичка - "грешка при изпълнението", погледнах и явно може да означава един куп неща. Също така програмата ми взима около 6.79 МБ, като лимитът е 2, искам да питам какво реално би ми помогнало да намаля количеството памет и каква може да е тази грешка при изпълнението?

Кодче: https://pastebin.com/2gKC05zP

Кодът е голям и грозен, но честно съм се отчаял вече. Направих я поне по 3 начина вече и все имам грешка.

 

Всичко най-хубаво!

Божко

Тагове:
0
C++ Fundamentals
galin_kostadinov avatar galin_kostadinov 166 Точки
Best Answer

Привет!

Разгледах подробно кода ти.

Като цяло програмата ти работи вярно, но тъй като основно се изисква да е бързо и да заема малко памет, то ти минават само 50% от тестовете.

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

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

Според мен трябва да се изполва XOR (^) както съм написал в предния коментар. Ако има различен подход ще ми е интересно да споделите.

2. Направи си функция която ще чете от конзолата по 5 символа. След това тази група от символи или ако искаш си го превърни в десетично число, го сравняваш с result;

std::vector<char>currArray;

Първоначално int result = 0;

result = result ^ currNumber;

currNumber - това в случая е десетично число, може да го преобразуваш по подобен начин на твоя *16... от currArray

Другия вариант е без преобразуване и да сравняваш символ със символ.

i=0-4;

result = result[i] ^ currArray[i];

currArray - това е текущия вектор със символи, който си прочел.

3. Ако използваш result = result[i] ^ currArray[i];  то дирекно печаташ на конзолата с обходане на вектора елемен по елемент.

Ако ще е десетично числото, то или трябва да го преобразуваш по твоя начин или да използваш наготово функция за това.

Тази библиотека ще ти даде възможност да манимурираш входния и изходния поток от данни:
#include<iomanip>
std::cout << std::hex << result << std::endl; - ако използваш само това ще ти излезе без водещи нули отпред примерно ако резултата ти е 1 ще ти излезе 1, а не както очаква Judge 00001;
std::cout << std::setfill('0') << std::setw(5) << std::hex << result << std::endl; Това ще ти сетне потока да ти печата с поне 5 символа.

4. Друг вариант за следните проверки, за да не търсиш на коя позиция се съответоно число от http://www.asciitable.com/

input[str+4]>=97&&input[str+4]<=102

input[str+4]>='a' && input[str+4]<='f'

или

isdigit(input[str+4]); Намира се в (#include<cctype>) Ако е цифра ти връща true;

firstDigit=(int)input[str+4]-87;
firstDigit= input[str+4] - 'a' + 10;

firstDigit=input[str+4]-48;
firstDigit= input[str+4] - '0';

Като тази т.4 ти е нужна само ако ще го преобразуваш в детесично число.

Ако имаш конкретни въпроси, моля питай...

Поздрави!

 

 

 

 

 

3
BozhidarKlouchek avatar BozhidarKlouchek 24 Точки

Благодаря ти много! 
Бях чувал за XOR преди, но съвсем бях изключил да го ползвам, а библиотеката iomanip е изключително полезна!

 

1
daisy_c avatar daisy_c 3 Точки

Добре, аз разбрах как работят тези подходи, но всъщност не разбирам как ако пазя currentDNA и го сравнявам с всяко следващо ДНК, което идва от конзолата, ще разбера дали е уникално или не. Аз например пазя справка с уникалните (досега въведени от конзолата) и неуникалните и променям тезисправки, според новот което идва и така в крайна сметка в уникалните остава само едно. Но не знам как мога да сложа подхода с XOR за да реша задачата по-лесно. Може ли някаква идея?

0
galin_kostadinov avatar galin_kostadinov 166 Точки

Привет!

Идеята на подхода с XOR не е да пазиш всяка DNA, а да пазиш само един резултат.

Ако работиш с превръщане в десетично число на всяка група от по 5 символа(hex числото),

пробвай следното(Има го и в другия ми коментар):

Имаш едно число 7, което в бинарен вид изглежда 0111(отпред може да има още 0-ли, в зависимост в какво го пазиш в 32 бита, т.е. 32 клетки, в които има 0 или 1), ако на това число приложиш XOR със същата стойност 0111^0111 резултата е 0000.

Ако приложиш оператора с числата 0 и 7 -> 0000^0111 резулатат е 0111, т.е. 7.

Пробвай да разгледаш редицата от операции с четен брой елементи и един нечетен, независимо дали двата еднакви елемента са в един след друг или са по натам в редицата от числа и ще разбереш какво се случва.

1) 0111,0111, 0001 0001, 0010 -> 0010

2) 0111, 0001, 0001, 0010, 0111 -> 0010

 

1)0111^0111 = 0000 ->0000 ^0001 = 0001 -> 0001^0001 = 0000-> 0000^0010  = 0010 ;

пробвай с тази редица: 2) ...

https://hi-static.z-dn.net/files/d11/54d142caf81f51f4ade11e2cf42322fd.jpg

 

Подхода ти може да е верен, но отнема доста време и памет, понеже постоянно добавяш и триеш от до колкото разбира 2 списъка. Трябда да имаш само един елемент, ако го пазиш като 5 символа, то масив от 5 символа, които се променят всеки път, както съм описал в предния коменар result[i]= result[i] ^ currNumber[i]; а ако е десетично число result = result ^ currNumber;

Поздрави!

 

1
dmartinov avatar dmartinov 37 Точки

Нямам достъп до компютър в момента, за да разгледам кода ти, а от телефона не е много удобно, но в темата за задачата Bus, един беше пуснал неговото решение на тази задача. Може да го разгледаш тук и да направиш съпоставка с твоето решение: https://pastebin.com/CFC8uvTS

0
galin_kostadinov avatar galin_kostadinov 166 Точки

Привет!

Интересен подход за решаването на тази задача е чрез оператора XOR -> " ^ ".

Как работи той:

XOR (^)

a b a^b
0 0 0
0 1 1
1 0 1
1 1 0

Това е бинарен оператор, той сравнява съответстващите битове на всяко едно от числата. Когато двата бита са еднакви, примерно 0 и 0, или 1 и 1, тогава резултата е 0.

Примерно ако сравнямаме числото 7 със 7, това ще сравни тяхното бинарно предстявяне 0111 и 0111. Като резултат ще върне 0000 (В зависимост как си нагласиш да го принтираш, може да е с различен брой символа, но по подразбиране за int или char ще ти принтира просто 0 в случая)

(Това колко бита ще сравнява зависи от това в какво сме запазили числото, ако е запазен в char това са 8 бита, ако е int са 32, като зависи дали е знаково число, т.е. дали първия бит пази знак или стойност...)

Какво е важното в случая - това, че когато имаме в една редица две по две еднакви числа резултата от тази операция ще е 0.

result = result ^ currNumber;

0111 0111 0001 0001 -> 0000

0111 0111 0001 0001 1000 -> 1000 

(0000) ^ 1000 -> 1000

...

 

 

2
MartinBG avatar MartinBG 4803 Точки

Това е една от най-забавните задачи, на които съм попадал в курсовете на СофтУни! :)

Освен с XOR (решение с буфериран вход и микрооптимизации минава за 0.1 секунда и ползва 1.84MB), може да се реши и с bitset (0.68s, 1.94MB). 

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