Czy ktoś może nakreślić sposób rozwiązania zadania Talerz z tegorocznej OIG?
Hey!
0
4
wypadałoby wkleić treść zadania i swój pomysł na rozwiązanie
Hey!
0
To zadanie pochodzi z 3 etapu. Niestety, nie każdy ma tyle umiejętności, aby brać udział
w zawodach na tym poziomie :-(
Dany jest prostokątny talerz o podanych wymiarach, na którym należy ułożyć zadany
wzór z kwadratowych ciastek opisany za pomocą znaków # i .
Krzyżyk oznacza miejsce gdzie musi leżeć kawałek ciastka, a kropka widoczną część talerza.
Należy obliczyć maksymalny rozmiar kwadratowego ciastka, z którego da się ułożyć zadany wzór.
Na przykład dla talerza o wymiarach 6 na 5 o następującym wzorze
##...
###..
.####
.####
####.
###..
prawidłową odpowiedzią jest 2.
Jak się do tego w ogóle zabrać? Na pewno można sprawdzić wszystkie możliwości, ale
takie rozwiązanie nie będzie optymalne. Macie jakiś pomysł?
0
A tu jest jakis haczyk? Nie wystarczy policzyć pola prostokąta a potem pola tego co mamy ułożyć w zależności od parametru 'x' ktorym jest rozmiar boku ciastka?
0
Hm zakładam że ciastko może "nakładać się na siebie" bo już w drugiej linijce mamy 3 kawałki ciastka koło siebie, czego z ciasta o boku 2 nigdy nie zrobimy. Tak więc być może starczy sprawdzić jaka jest minimalna ilość pół "ciastko" zarówno w poziomie jak i pionie.
edit: chyba że kawałek ciastka może zostać ucięty i położony gdzie indziej wtedy, można by policzyć pola z ciastkami, i poszukać największego dzielnika będącego kwadratem innej liczby (pierwiastek kwadratowy z niego to wspomniany bok ciastka)
0
Sposób z liczeniem "półciastek" w pionie i poziomie nie da dobrej odpowiedzi np. w takim przypadku
talerz 6 na 6
..##..
.####.
##..##
##..##
.####.
..##..
Z liczenia "półciastek" będzie 2, a prawidłowa odpowiedź to raczej 1.
0
To zadanie z 3 etapu, więc podejrzewam, że jest jakiś haczyk.
0
Ja bym zrobił tak (to się chyba nazywa algorytm zachłanny):
- ustaw maxSiza na min(szerokosc, wysokosz) talerza
- pętla wyszukująca następny znak '#'
- pętla po rozmiarze od 2 do maxSize
- sprawdzamy w znalezionym miejscu da się wcisnąć ciastko o danym rozmiarze (szukamy czy da się dodać krawędź do ciacha z poprzedniej iteracji, krawędź ma nie zawierać znaku '.'), jeśli nie przerwij pętlę i aktualizuj maxSize rozmiarem o 1 mniejszym
- zapełnij odpowiednie '#' znakiem 'X' (poszerz krawędź testowanego ciacha), by oznaczyć że to pole da się przykryć ciachem maxSize i przy następnej iteracji nie trzeba go sprawdzać.
- koniec pętli z punktu 3
- koniec pętli z punktu 2
Jakoś nie widzę sposobu na szybszą metodę.