Roxettes

BozhidarKlouchek 24 Точки

Roxettes

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

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

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

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

Божко

Тагове:

29/09/2019 17:01:11 C++ Fundamentals

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 ти е нужна само ако ще го преобразуваш в детесично число.

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

Поздрави!

29/09/2019 22:48:30

BozhidarKlouchek 24 Точки

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

02/10/2019 17:31:47

daisy_c 3 Точки

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

03/10/2019 11:58:31

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;

Поздрави!

03/10/2019 12:37:09

Покажи всички коментари

dmartinov 37 Точки

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

29/09/2019 17:55:28

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

...

29/09/2019 19:43:17

MartinBG 4803 Точки

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

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

30/09/2019 04:20:57