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