• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

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

Object Storage Arubacloud
+2 głosów
2,505 wizyt
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 laugh). 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

0 głosów
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;
}

 

1
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

 

+1 głos
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 :)
+1 głos
odpowiedź 21 sierpnia 2016 przez manjaro Nałogowiec (37,390 p.)
Niedawno to robiłem na SPOJu niemal identyczne http://pl.spoj.com/problems/LENLCS/

Powiem tak. Na sucho bez znajomości algorytmu LCS nikt tego nie rozwiąże w ciągu godziny.

Tutaj jest ładnie wyjaśnione na przykładzie jak to się liczy. http://informatyka.wroc.pl/node/627?page=0,5

Inna sprawa że startując w konkursach programistycznych trzeba być przygotowanym na różne takie algorytmy.
0 głosów
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 :)
0 głosów
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.
0 głosów
odpowiedź 21 sierpnia 2016 przez niezalogowany
bardzo podobne do tego pierwszego zadania widziałem na spoju.
komentarz 21 sierpnia 2016 przez iWantCode Bywalec (2,170 p.)
#Złote #Galoty #Za #Odkop
komentarz 21 sierpnia 2016 przez niezalogowany
dzięki, tyle, że to nie ja odkopałem, przewiń wyżej ;p

Podobne pytania

+4 głosów
0 odpowiedzi 174 wizyt
0 głosów
2 odpowiedzi 411 wizyt
0 głosów
0 odpowiedzi 233 wizyt
pytanie zadane 9 grudnia 2018 w Matematyka, fizyka, logika przez niezalogowany

92,661 zapytań

141,557 odpowiedzi

320,000 komentarzy

62,028 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...