Informatyka UJ forum

kap00ch

a ja sie juz cieszylem ze jest jedno nowe ;p [link widoczny dla zalogowanych]

kg86

nie wiem czy ja dobrze kumam tresc tego zadania, ale jesli mamy wyrazenie nawiasowe A, to np. k A -k tez jest poprawnym wyrazeniem nawiasowym i zawiera podciag A :P albo wstawic gdzies do srodka k -k i tez bedzie ok... wiec gdzie jest haczyk? :)

ostoj

kg86

no wlasnie to przeoczylem :P dzieki :)

Rogal

Zdecydowanie NALEŻY używać return. Dostałem za to 2 gwiazdki :D

mateo

@Rogal: zapodalbys binarke?

EDIT: juz nie trzeba... napisalem sobie symulator wyjscia i znalazlem blad.

przem

Czy mógłby ktoś napisać poprawne wyjście dla wejścia -1 1, jakoś nie mogę rozkminić tego zadania z góry dzięki!

mateo

Rogal

moja rada:
jeśli dla testu przykładowego dostajecie odpowiedź

1 2 1 -1 1 -1 -2 -1

to choć jest ona poprawna to jednak prawdopodobnie macie błąd

mateo

hansu

No to jest chyba raczej oczywiste ze dopisujemy do zaraz za otwierajacym - wtedy mamy pewnosc ze ten manewr w zaden sposob nie wplynie na reszte ciagu...

Rogal

dobra, zarzucę lepszym testem :D

mateo

Roxel

Nie zapomnijcie sobie o zerze na koncu wypisywanego wyrazenia 8)

Ethlinn

grrrr... bombka przez wypisywanie nierekurencyjne... nie ma to jak skomplikowac sobie zycie w najprostszych przypadkach :/... ale grunt, że przeszło... i to jeszcze przed imprezą urodzinkową Czarnej :D czyli jednak się nie spóźnię :D. Wheeeeee ^__^

Stasiu

właśnie wziąłem się za czytanie tego zadania i czegoś nie czaję...

czy dla przykładowych danych:

neino

Hej,

ktos ma pomysl...idee...dlaczego moze pojawiac sie ANS w 'idealnie dzialajacym programie' ? ;]
siedze nad kodem i nie wiem co jest nie tak... tablice sa na poczatku zerowane...wyniki wygladaja na poprawnie nawiasowane.

Pustoelementowe i jednoelementowe ciagi dzialaja mi poprawnie...no ale moze macie jakies swoje patologiczne przyklady ? (nawet na testerce mateo wszystko gra...)

dzieks

Azhag

Cos mi nie idzie to zadanie. czy ktos moglby troche opisac rozwiazywanie.

Sobek

exeman

Bylbym bardzo wdzieczny gdyby ktos podrzucil wypelniona macierz pierwsza i druga dla przykladowego testu.

Z gory dzieki wielkie.

Yoter

0 0 0 0 0 0 0
0 1 2 1 2 3 2
0 0 1 2 3 2 3
0 0 0 1 2 3 2
0 0 0 0 1 2 1
0 0 0 0 0 1 2
0 0 0 0 0 0 1

0 0 0 0 0 0 0
0 -1 -1 3 3 -1 3
0 0 -1 -1 -1 5 -1
0 0 0 0 0 0 0
0 0 0 0 -1 -1 6
0 0 0 0 0 0 0
0 0 0 0 0 0 0

pierwsza tablica: ilość nawiasów które trzeba dostawić żeby było ok
druga: -1 gdy nawias otwierający i trzeba dostawić
0 gdy nawias zamykający i trzeba dostawić
cokolwiek innego - indeks na którym znajduje się nawias zamykający do początkowego

jesli chcesz macierze z kolejnych iteracji pętli to pisz.

jak coś to pytać...

exeman

Chcialem publicznie podziekowac dzisiejszej ekipie supportowej, ktora przez pol dnia wspiewala mnie podczas mojej desperacji.

Podziekowania dla:
Lukasza Medrali (za znalezienie chlernych bledow)
Chlebka (za pozyczenie notatek oraz wytlumaczenie cholernego algorytmu oraz znalezienie cholernych bledow)
Piotra Mierzejewskiego (za wytlumaczenie cholernego zadania)
Yotera (za macierze)
Robsona (za wytlumaczenie cholernego zadania)
Wojciecha Kordeusza (za wytlumaczenie cholernego zadania)
Jagma (za wytlumaczenie cholernego algorytmu)
oraz wszystkim ktorzy w wiekszy lub mniejszy sposob przyczynili sie do przepchania przeze mnie tego cholernego zadania.

Mam nadzieje, ze Athina szybko wybuchnie.

cheater_

Niektórzy mówią że to zadanie jest takie samo jak C, ale prawda jesta taka, że nienawidzę go bardziej niż "magic 7". po prostu.

liffe

---
Niektórzy to mają szczęście do nieszczęścia. Kiedy myślałem, że program dobrze chodzi, okazało się co innego. Mam problem z wypisywaniem (albo z tworzeniem tablicy albo z jej odczytaniem przy wypisywaniu). Moglby mi ktos pomoc to ulozyc? :cry:

exeman

Co prawda juz spora wiekszosc zadanie zakodzila, ale moze nie wszyscy do konca rozumieja jak to zadanie dokladnie dziala, zatem wklejam lekkiego tutoriala, ktory powstal z tlumaczenia tego zadania na gg.

y = wiersz, x = kolmna
nawiasy[y] to rozpatrywany nawias,
tab[y, x] to dlugosc najkr. poprawnego ciagu nawiasow od y do x
Indeksujemy od zera.

wypelnilismy macierz dla ciagow jendoelementowych. (0, 0), (1, 1), (2, 2) , itd... na wartosc 2 - dlaczego? Poniwaz, w kazdym przypadku uzyskamy jakis jeden nawias, ktory trzeba domknac - zatem najkrotszy poprawny nadciag bedzie skladal sie z tego nawiasu oraz jego dopelnienia - razem 2 nawiasy. Przekatna drugiej macierzy ustawiamy na -1. -1 Bedzie oznaczac, ze dopisujemy nawias.

teraz bedziemy jechali pierwsza przekatna, czyli:
(0, 1), (1, 2), (2, 3), ..., (h, h + 1)
to sa takie ciagi podwojne
czyli to co poprzednio tylko dlugie na dwa
no i co z nimi robimy
rozpatrujemy nawiasy[wiersz], tak jak opisywalem wyzej, zatem dla pary (0, 1) patrzymy na pierwszy nawias z tej dwojki
z dwojki 0..1
sprawdzamy czy jest zamykajacy. jezeli jest zamykajacy, to wiemy, ze najkrotsza dlugosc uzupelnionego do poprawnego ciagu 0..1 bedzie:
to co dla elementu (1, 1), czyli dlugosc co wyliczalismy na poczatku na tej przekatnej, czyli dlugosc popranwgo ciagu powstalego z jednego elementu nawiasy[1] plus jeszcze 2. 2 sie bierze stad:
wiemy, ze pierwszy jest zamykajacy, czyli np. ")". O drugim nic nie wiemy, zatem mamy takie mozliwosci: ")(", "))", ")[", ")]" itp. Ale wiemy, ze one same sie nie domkna. Zawsze bedziemy musieli najpierw otworzyc tego pierwszego, a drugiego bedziemy musieli zamknac, poniewaz pierwszy jest zamykajacy, ale jest wczesniej.
Omawialismy zamykajacy
Mamy np. Pare "(]". Na poczatku przyjmujemy wariant pesymistyczny, czyli, ze nawiasy nie beda do siebie pasowac, czyli, ze trzeba bedzie tak jak poprzednio - dwa uzupelnic. Czyli do takiego: "()[]", w tym przypadku jest to optymalne i poprawne, ale wezmy sobie np. atki przyapdek:
Para "()". Robimy algorytmem. Ustawiamy najpierw najbardziej pesymistyczny wariant, czyli, ze trzeba bedzie dopelnic i jeden i drugi, czyli do takiego "()()", no ale widac, ze to bedzie zle, bo ciag juz od razu jest poprawny. Do tego wlasnie sluzy ta petla z minimami, zeby wykryc lepsze rozwiazanie, i dziala ona tak:
Jak mamy ciag "()", czyli np. pare (2, 3), czyli idac dalej nawiasy[2] = "(", nawiasy[3] = ")". No i teraz bedziemy szukac poczawszy od 2+1 do 3 w nawiasach, czy nie znajdziemy lepszego rozwiazania. 2 + 1, poniewaz pierwszy to wiemy, ze jest otwierajacy, a my wlasnie poszukujemy do niego zamkniecia. Jak dziala to wybieranie opisze teraz:
Szukamy pokolei, dla (x, y) od x+1..y w nawiasach takiego nawiasu, zeby nawias[k] (k to od x+1 do y) byl domknieciem pierwszego, czyli nawiasy[k] = -nawiasy[x] (nawiasy[x] to ten rozpatrywany otwierajacy) no i dodatkowym zalozeniem jest to, zeby wybrac takie rozwiazanie, aby bylo najlepsze i tutaj zaczynaja sie schody, bo trzeba policzyc taka sume:
Jak mamy z petli element w tablicy (x, y), (ten rozpatrywany otwierajacy to napisy[x]), to jedziemy k = x+1 .. y, wezmy zatem bardziej ogolny przyklad. x = 1, y = 4. Zatem mamy czteroelementowy ciag nawiasow od 1..4, oraz wiemy, ze pierwszy jest otwierajacy. Przyklad na ktorym bedziemy rozumowac to: "([))"
Wariant pesymistyczny, to jak juz pisalem jest 2 + tab[y + 1, x], czyli domkniecie pierwszego nawiasu - stad to 2, bo uzyskamy ciag () - plus to jaki dlugi jest ten ciag "[))", stad to tab[y + 1, x]
No to jak obliczylismy pesymistyczny wariant, to czas na sprawdzenie, czy nie ma lepszego. Aby lepiej liczyc rozpiszmy szybko ten przykladowy "([))" ile on by wynosil:
tab(0, 0) = "(" = 2
tab(1, 1) = "[" = 2
tab(2, 2) = ")" = 2
tab(3, 3) = ")" = 2

tab(0, 1) = "([" = 2 + tab(0 + 1, 1) = 4. Nie znajdziemy tutaj domykajacego, wiec mozemy pozostac na pesymiustycznym, ale za chwile go dokladnie omowimy.
tab(1, 2) = "[)" = 2 + tab(1 + 1, 2) = 4. Tak samo jak wyzej
tab(2, 3) = "))" = 2 + tab(2 + 1, 3) = 4.

tab(0, 2) = "([)" = ... Tutaj zaczynamy omawianie, bo pesymistyczny bedzie gorszy niz optymistyczny:

nawiasy[0] jest otwierajacy. Wyliczamy najpierw wariant pesymistyczny, czyli, ze tab(0, 2) = 2 + (0 + 1) + 2, czyli, ze jak mamy "([)", to wyjdzie nam "()" + dlugosc poprawnego zamkniecia "[)", a to wynosi 4, bo jest to tab(1, 2), ktore prowadzi do "[]()". Zatem pesymistycznie wyjdzie nam 6, a ciag postaci "()[]()", czyli beznadzieja, bo optymistycznie widac, ze z "([)" powinno byc np. "([])", Do tego wlasnie uzyjemy teraz wyszukiwanai wariantu optymistycznego, czyli jedziemy k, od y+1..x, czyli jak rozpatrujemy (0, 2) to analizujemy od (1..2) w poszukiwaniu naszego domykacza, dalej:

No i sprawdzamy nawiasy[1] = "[" wiec, nie pasuje, bo nie domyka "(", jedziemy dalej. nawiasy[2] = ")" domyka, czyli jest super. Sprawdzmy, czy oby napewno sie oplaca wybrac ten nawias, zeby to stwierdzic musimy sprawdzic, jakiej dlugosci bylby najkrotszy poprawny ciag, jesli skozystalibysmy z tego nawiasu. No wiec bedzie to tak: jak sparujemy te nawiasy ( oraz ) z konca, to dlugosc poprawnego bedzie dlugosc tych zewnetrznych (czyli 2) plus to pozostale, a pozostalo nam "[", ze srodka. Zatem bierzemy do sumy jego uzupelnienie, on sie uzupelni do "[]", wiemy to z wyliczania tab(1, 1) co podalem wczesniej. Czyli caly ciag wyjdzie nam dlugosci 6, bedzie on postaci "([])", jak przewidywalismy.

Ale wyprowadzmy wzor na ta dlugosc

Wezmy ogolny przypadek "(...)..." Czyli pierwszy sparowalismy z jakims w srodku naszego rozpatrywanego ciagu nawiasow od m..n - para (m, n). Zatem kosz to bedzie 2 (dlugosc tych nawiasow wyszcegolnionych w kropkach) oraz dlugosc pierwszych "..." - tych przed ")" oraz tych drugich "..." po ")".

Czyli wzor to bedzie: 2 + tab(m + 1, k - 1) + tab(k + 1, n).

... i tak wyliczamy te sumy i wybieramy takie k, ze bedzie ono dawalo najmniejsza sume (a ktora przed chwila wyprowadzilem). Pamietac trzeba, ze trzeba uwazac, aby suma byla tez mniejsza niz pesymistyczny wariant. Bo mozliwe, ze moze sie trafic, ze znajdziemy domykajacy nawias, ktory jednak da nam wieksza sume niz nasz wariant pesymistyczny, wtedy nie kozystamy z niego i pesymistycznie go domykamy mimo istnienia domykacza gdzies dalej. No ale jesli ten dobry domykajacy na k pozycji, to wtedy do drugiej macierzy wstawiamy wartosc "k". W kazdym innym przypadku wstawiamy -1. I to jest koniec zadania. Jeszcze tylko wypisywanie...

edit:

...Wypisywanie to prosta rekurencja. Jej prototyp to funkcja(int x, int y). Gdzie x to poczatek, a y to koniec ciagu. Startujemy zatem z calym ciagiem funkcja(0, dlugosc - 1).

Funkcja rekurencyjna dziala tak, ze jesli druga tablica zawiera pod wspolrzednymi (x, y) to wtedy wiemy, ze musimy dopisac nawias do a. Tlumaczylem przedtem, ze jesli domykamy ten pierwszy rozpatrywany, czyli nawiasy[wiersz] == nawiasy[x] w naszym przypadku (tu troche kolizja oznaczen, te x i y to nie lacza sie z tymi z poprzedniego tlumaczenia) i chcemy dopisac drugi nawias ktory by go domykal to wstaiwamy -1

Tak samo w wersji pesymisgtycznej przy otwierajacym nawiasie tez wstawialismy -1, bo nie znajdywalismy domykajacego gdzies tam dalej, wiec chcielismyy go wstawic.

Stad wniosek, ze jesli mamy -1 to wstpawiamy dodatkowo cos o przecienym znaku

w zaleznosci od znaku w nawiasie[k] to bedzie to albo przed tym albo po ze znakiem przeciwnym

Jesli tabela2[x, y] = -1 to dopisujemy. Pytanie - co? Zamykajacy czy otwierajacy. No jesli nawiasy[x] > 0 no to znaczy, ze musimy dopisac do niego (ktory jest otwierajacy) jego domkniecie. Wiec wypisujemy najpierw otwarcie, a potem domkniecie: printf("%d %d", mem[x], -mem[x]).

A jesli mem[x] < 0, to najpierw wypisujemy -mem[x], a potem mem[x]

No ale wtedy dopiero mamy zalatwiony pierwszy rozpatrywany, czyli nawiasy[x], a mamy jeszcze od x+1..y, z ktorymi nic nie zrobilismy, ale do tego odpalamy poprostu dalej rekurencje, czyli wykonujemy potem funkcja(x + 1, y);

No a jesli ta tablica2[x] jest rozna od -1, to wiemy, ze:
1. Nawias nawiasy[x] jest otwierajacy
2. Gdzies pomiedzy x, a y jest jego domkniecie
3. Domkniecie jest na pozycji tablica2[x], ktora wlasnie zbadalismy, ze jest rozna od -1
Zatem co musimy zrobic. Wypisujemy to otwarcie, czyli to napisy[x], potem odpalamy rekurencje do tych trzech kropek, pozniej wypisujemy domkniecie z pozycji napisy[k], a potem jedziemy rekurencje dla drugich trzech kropek -> (...)...

Bedzie to zatem dzialac tak:
1. wypisz napisy[x]
2. (x+1, tablica2[x][y] - 1), poniewaz nie chcemy aby nasz domykajacy nawias wpadal w kolejna rekurencje, tylko same kropki
3. wypisz -napisy[x] (lub napisy[tablica[x][y]], zeby bylo bardziej intuicyjnie, ale to na to samo wychodzi)
4. funkcja(tablica[x][y] + 1, y)

Na koniec nalezy pamitac, aby na poczatek funkcji rekurencyjnej dac warunek na jej przerwanie:
if (x > y) return 0;