Професионална програма
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
daisy_c avatar daisy_c 3 Точки

Мисля, че разбрах горе-долу идеята. Реално начинът, по който работи XOR е, че "пази спомен" за нещо, докато не дойде това нещо още веднъж. И така всички неща, които срещне четен брой пъти, че ги "забрави" и единственото нечетен брой пъти срещано нещо, ще остане.

1
03/10/2019 16:01:26
miroslav_krajcir avatar miroslav_krajcir 1 Точки

Hallo Galin, yes there is another way to approach this problem than XOR. I understand the idea with XOR, which works fine. But i came up with another solution using just strings (no conversion to/from hex needed) and unordered_set. It seems, it passed all the tests in Judge...

M.


#include <iostream>
#include <string>
#include <unordered_set>

int main() {
	std::cin.sync_with_stdio(false);
	std::cout.sync_with_stdio(false);

	std::string			roxette = "00000";
	std::unordered_set<std::string>	roxettes;

	while (true) {
		//	read the first digit
		std::cin >> roxette[0];
		if (roxette[0] == '.')
			break;

		//	read the rest of the digits...
		std::cin >> roxette[1] >> roxette[2] >> roxette[3] >> roxette[4];

		auto it = roxettes.find(roxette);

		//	if roxette is not found in set, include the roxette
		if (it == roxettes.end())
			roxettes.insert(roxette);
		//	if already included, erase the roxette
		else
			roxettes.erase(roxette);
	}

	//	print the result
	for (auto& r : roxettes)
		std::cout << r;
}

https://pastebin.com/9HTiJ1Xv

0
02/06/2021 21:57:27