W tym odcinku omówimy zadania Deski oraz Deski kontratakują z zawodów pierwszego stopnia XIV Olimpiady Informatycznej Juniorów.
Część artykułów reaktywowanego w zeszłym miesiącu Informatycznego Kącika Olimpijskiego kierowana będzie do początkujących olimpijczyków. Tytuły tych tekstów oznaczać będziemy „IKO na start”.
Deski
W oryginalnej wersji zadania budujemy kwadratową piaskownicę. Potrzebujemy do tego czterech desek o równej długości. Mamy do dyspozycji \(N\) desek o długościach wyrażonych liczbami całkowitymi. Deski te nie muszą być równej długości, ale można je dowolnie skracać. Musimy wybrać cztery, skrócić je, a potem ułożyć z nich kwadratową piaskownicę. Należy wypisać pole największej możliwej piaskownicy lub \(0,\) jeśli budowa nie jest możliwa.
Pełną treść zadania z przykładami można znaleźć na stronie
oij.edu.pl/oij14/ etap1/ zadania/des/deszad.pdf.
Zauważmy, że jeśli wybieramy cztery konkretne deski, musimy skrócić każdą do rozmiaru najkrótszej pośród nich. Aby uzyskać największą możliwą piaskownicę, wybieramy po prostu cztery najdłuższe deski. Wystarczy zatem posortować długości wszystkich dostępnych desek, do czego najlepiej użyć wbudowanej funkcji bibliotecznej sort. Polem będzie kwadrat długości czwartej co do wielkości deski.
Kiedy budowa piaskownicy nie powiedzie się? Jedynie wtedy, gdy dysponujemy mniej niż czterema deskami. Ponieważ każdy bok musi powstać z osobnej deski, przy ich mniejszej liczbie nie uda nam się zamknąć kwadratu.
Deski kontratakują
W trudniejszej wersji zadania możemy nie tylko skracać deski, ale również dzielić je na mniejsze kawałki. Nadal jednak chcemy uzyskać cztery równe fragmenty (o całkowitej długości). Na przykład, mając deski o długościach \(7,\) \(2,\) \(2\) oraz \(1,\) możemy podzielić najdłuższą z nich na trzy części o wymiarach \(2,\) \(2\) i \(3,\) co pozwoli nam uzyskać cztery elementy o długości \(2.\)
Pełną treść tego zadania z przykładami można znaleźć na stronie oij.edu.pl/ oij14/etap1/zadania/dek/dekzad.pdf.
Każdy z czterech boków piaskownicy musi zostać wycięty z jednej deski. Oznacza to, że nigdy nie wykorzystamy fragmentów pochodzących z więcej niż czterech desek. Rozważymy zatem cztery scenariusze, w których piaskownica powstaje z dokładnie jednej, dwóch, trzech lub czterech desek. Dla każdej z tych opcji wyznaczymy maksymalny możliwy bok i wybierzemy najkorzystniejszą z nich.
Zauważmy także, że zawsze będziemy chcieli użyć najdłuższych desek. Dłuższa deska daje bowiem większe możliwości niż krótsza, a zatem sięganie po inne deski niż cztery najdłuższe nie ma sensu. Oznaczmy zatem długości czterech najdłuższych desek poprzez \(d_1,\) \(d_2,\) \(d_3\) oraz \(d_4,\) gdzie \(d_1 \geq d_2 \geq d_3 \geq d_4.\)
Zacznijmy od przypadku, w którym wykorzystujemy cztery deski. Odpowiada on prostszej wersji zadania, więc bokiem piaskownicy jest długość czwartej co do długości deski.
W wariancie z trzema deskami jedna z nich musi zostać podzielona na dwa równe fragmenty. Z pozostałych dwóch desek wycinamy po jednym kawałku. Nie opłaca się dzielić na nierówne części, bo i tak jedną z nich musielibyśmy później skrócić. Wyjątek stanowi możliwość, kiedy długość deski jest nieparzysta. Nasza piaskownica musi mieć całkowite długości desek, zatem trzeba podzielić długość na dwa „bez reszty” (tj. pomijając część ułamkową). Z tego powodu w dalszej części wszystkie dzielenia będą „bez reszty”. Opłaca się dzielić na pół wyłącznie najdłuższą deskę, zatem bok naszej piaskownicy wyniesie \(\min(\frac{d_1}{2}, % d_3).\)
Przy wykorzystaniu dwóch desek mamy dwie możliwości. Możemy wyciąć trzy równe części z najdłuższej z nich i jedną z drugiej, co daje bok \(\min(\frac{d_1}{3}, d_2).\) Inną możliwością jest wycięcie po dwa kawałki z każdej deski, co daje nam bok o długości \(\min(\frac{d_1}{2}, \frac{d_2}{2}).\)
Ostatnia opcja to użycie tylko jednej deski. Wtedy optymalnym rozwiązaniem jest podzielenie jej na cztery równe deski o długości \(\frac{d_1}{4}.\)
Kiedy w tej wersji zadania nie uda się zbudować piaskownicy? Stanie się tak, gdy nie będziemy w stanie uzyskać boku o długości przynajmniej \(1.\) Wystarczy zatem sprawdzić, czy suma długości desek wynosi przynajmniej \(4 \cdot 1 = 4.\)
Co dalej, czyli kilka słów o Olimpiadzie Informatycznej Juniorów
Powyższe omówienie zadania (wierzymy, że nie za trudnego na początek) ma charakter czysto teoretycznej analizy. Na prawdziwych zawodach, oprócz wymyślenia rozwiązania, trzeba je jeszcze zapisać w odpowiednim języku programowania. Jeśli więc Czytelnik już potrafi kodować w Pythonie lub C++, zachęcamy do sprawdzenia swoich umiejętności, próbując zrobić to zadanie na portalu szkopul.edu.pl, gdzie znajduje się archiwum oraz automatyczna „sprawdzaczka” do starych zadań olimpijskich. Olimpiada Informatyczna Juniorów gorąco zachęca właśnie do tego, żeby zacząć uczyć się programowania nawet „od zera” i spróbować sił z podobnymi zadaniami. Najbliższa edycja startuje 20 września 2026 roku. Informacje dla nowych zawodników znajdują się na stronie oij.edu.pl/start.