Dzisiejszy konkurs z programowania C++ - Zadanie jakie dostaliśmy

pytanie zadane 24 maja 2016 w C i C++ przez Konrad Nabożny Stary wyjadacz (13,460 p.)

Witam. Brałem dzisiaj udział w konkursie z programowania w języku C++. Chciałem się z Wami podzielić zadaniami, może kogoś interesuje co dostaje przeciętny uczeń technikum/liceum.

Wyłożyłem się na zadaniu pierwszym za 25 punktów. Napisałem tylko wczytywanie danych z klawiatury do tablicy char opartej na wektorach (tak, musiałem się popisać ich znajomością, zawsze coś na plus ). Zadanie drugie, oraz trzecie były dla mnie dosyć dobrze zrozumiałe i poradziłem sobie bez większych problemów. Jeżeli ktoś z was, znalazłby kilka minut w ciągu dnia i zrobił zadanie pierwsze, którego nijak nie rozumiem, to byłbym wdzięczny. Pozdrawiam serdecznie :)

6 odpowiedzi

odpowiedź 24 maja 2016 przez Krzyko Początkujący (460 p.)
wybrane 24 maja 2016 przez Konrad Nabożny

Najlepsza

Całkiem inteligentne zadanie. Uprościłem nieco wczytując typ string, ale można to łatwo zmienić, liczy się sposób działania funkcji.

using namespace std;

void maxSequence(string a, string b)
{
	string max = "";
	string curr = "";
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < b.size(); j++)
		{
			if (a[i] == b[j]) 
			{
				curr += a[i];
				if (i + 1 < a.size())
					i++;
				else
					break;
			}
		}
		if (curr.size() > max.size())
		{
			max = curr;
			curr = "";
		}
	}
	cout << max.size() << endl << max << endl;
}

komentarz 21 sierpnia 2016 przez manjaro Nałogowiec (37,390 p.)
edycja 21 sierpnia 2016 przez manjaro

To nie jest prawidłowy algorytm. Zaimplementuj to do przykładu który podałem na spoju i się przekonasz.

Wczytaj słowa "deskorolka" oraz "stokrotka" i sprawdź co dostaniesz na wyjściu. Twój algorytm daje podciąg 3 znaków "oko" A powinno być
deskorolka
--sk-ro-ka

stokrotka
s--kro-ka

odpowiedź 24 maja 2016 przez Porcupine Nałogowiec (31,560 p.)

Ogólnie to dość znany problem w informatyce, który nosi nazwę LCS (Longest Common Subsequence) i możesz o nim sporo poczytać / pooglądać jeśli będziesz szukał pod tą nazwą. Oczekiwane, najefektywniejsze rozwiązanie stosuje programowanie dynamiczne, które daje całkiem niezłą złożoność O(n * m). Gdzie n i m to długości wczytanych ciągów.

Pozdrawiam,

komentarz 24 maja 2016 przez Konrad Nabożny Stary wyjadacz (13,460 p.)

O dzięki, z pewnością coś o tym poczytam :)

odpowiedź 21 sierpnia 2016 przez manjaro Nałogowiec (37,390 p.)

odpowiedź 24 maja 2016 przez Patrycjerz Mędrzec (192,320 p.)

Zadanie dość skomplikowane, ale sądzę, że niezłym sposobem jest ciągłe wyznaczanie podciągów jednego ciągu (zaczynając od największego) i równoczesne sprawdzanie, czy istnieje takowy w drugim ciągu.

Czyli usuwasz najpierw jedną literę i sprawdzasz, potem drugą i sprawdzasz, trzecią i sprawdzasz... później dwie naraz i sprawdzasz... aż nie dojdziemy do momentu, gdy znajdziemy wspólny podciąg lub aż zlikwidujemy wszystkie znaki w ciągu.

Oczywiście podciągi będą mogły się powtarzać, ale nie jest to ważne w odniesieniu do tego zadania.

A tak z ciekawości - ile trwał ten konkurs?

komentarz 24 maja 2016 przez Konrad Nabożny Stary wyjadacz (13,460 p.)

Na wszystko mieliśmy 1,5 godziny, lub dwie. Sam nie wiem, w ogniu walki z kodem całkiem wyleciało mi to z głowy :)

odpowiedź 24 maja 2016 przez Tomatosoup Pasjonat (18,530 p.)

Zadania nie są wcale jakieś tragiczne, wystarczy trochę pomyśleć, ale nie wątpię że w "ogniu walki" można nie wpaść na coś takiego :)

Polecam natomiasto obejrzeć zadania z olimpiady informatycznej, właśnie dla szkół średnich:

http://www.oi.edu.pl/static/attachment/20160524/blue_1.pdf

Tam to jest masakra czasami

komentarz 24 maja 2016 przez Konrad Nabożny Stary wyjadacz (13,460 p.)

Oczywiście, nigdzie nie pisałem że są tragiczne. Niemniej jednak nigdy w szkole nie miałem najmniejszej styczności z C++, a jedyna co potrafię to to z filmów Pana Mirosława, oraz z tego co wyczytam tutaj - czytając komentarze :)

EDIT: No, jeszcze przerobiłem kawałek książki, ale wiele nowego z tego nie wyniosłem.

komentarz 21 sierpnia 2016 przez CharlieGG Użytkownik (900 p.)

Przerabianie niebieskiej książeczki bez dobrej znajomości C++ i algorytmiki to masochizm, który na dodatek nie przynosi zbyt wielu korzyści. Znacznie lepiej jest próbować robić zadanie ze SPOJa/MAINa, a dopiero potem zabrać się za zadania z OIa itp.