Projekt z przedmiotu Algorytmy dla Problemów Trudnych Obliczeniowo

Sprawy organizacyjne

Prowadzący przedmiot:

• dr hab. inż. Piotr Faliszewski
• dr inż. Marcin Kurdziel
• dr inż. Marek Gajecki
• mgr inż. Krzysztof Magiera
• mgr inż. Marcin Skotniczny

Terminy oddania projektu:

• Pierwszy termin: 15 lipca 2016r. 30 czerwca 2016r. 12 czerwca 2016r., godz 23.59.
• Drugi termin: 1 wrzesnia 2015, godz 23.58.
• Trzeci termin: 15 września 2015, godz 23.59.

Do wykonania w ramach projektu:

• Należy napisać program, który rozwiązuje zadanie opisane poniżej oraz wysłać go do systemu arbitrażowego dla zadania.
• Należy także dostarczyć dokumentacje programu. Dokumentacja nie może przekraczać 8 stron tekstu czcionką 11pt, przy rozsądnych marginesach. Dokumentacja powinna zawierać wyłącznie informacje na temat użytych algorytmów i pomysłów rozwiązania zadania, a nie szczegółów technicznych implementacji. Dokumentacja istotnie krótsza wcale nie musi być wadą projektu.

Języki programowania: Jedyne dwa dopuszczalne języki programowania to C oraz C++/C++11 (obecnie zainstalowany kompilator to gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3).

Zasoby/współbieżność: Programy nie mogą odwoływać się do systemu plików, nie mogą próbować nawiązywać połączeń sieciowych, być wielowątkowe, wieloprocesorowe, itp. Programy powinny jedynie wczytać ze standardowego wejscia opis zadania, wykonać obliczenia w pamięci i wypisać wynik na standardowe wyjście. Złamanie tych zasad, w szczególności odwołania do sieci oraz próby hackowania systemu arbitrażowego, mogą skutkować brakiem zaliczenia przedmiotu. (Istnieje takze mozliwosc, ze taka osoba bedzie musiala wysluchac bezposrednio od prowadzacych jak bardzo nas rozczarowala.)

Oceny:

• Na Państwa ocenę największy wpływ ma jakość działania zgłoszonego programu, a w drugim rzędzie jakość dokumentacji. Wyróżniająca się dokumentacja podnosi ocenę z projektu o 0.5 stopnia. Wyjątkowa zła dokumentacja (w tym nieistniejąca) obniża ocenę o 0.5 stopnia (w przypadku zaliczenia w terminie innym niż pierwszy dokumentacja, lub jej brak, nie wpływa na ocenę).
• Programy będą oceniane na podstawie ilości plansz, które będą w stanie rozwiązać. Dla każdej planszy będzie zadane ograniczenie czasowe (od kilku do kilkunastu sekund) oraz dostępna ilość pamięci (dokładne dane zostaną udostępnione później).
• Aby uzyskać zaliczenie, Państwa program musi być w stanie rozwiązywać zestaw podstawowych testów, który udostępnimy Państwu przez system arbitrażowy.
• Aby uzyskać wyższą ocenę, program musi być w stanie rozwiązywać odpowiednio trudniejsze testy. Oceny powstaną na podstawie porównania jakości programów.
• Kod źródłowy państwa programów nie jest oceniany, ale może być przeglądany, więc proszę stosować komentarze i wcięcia.
• W przypadku wykrycia plagiatu, obie zaangażowane osoby otrzymują ocenę 2.0 z wszystkich trzech terminów.

Wymagania na ocenę 3.5

Dodatkowe informacje, programy i dane

• Program sędziego: judge.zip

Wywołanie sędziego:

  python judge.py input output

System arbitrażowy

• Adres dostępny spoza KI: 149.156.100.139:88.
• Adres wewnętrzny w KI: 172.29.128.10:88.

Zadanie: Potega Hetmanow

Na szachownicy o rozmiarach NxN ustawiono pewną liczbę hetmanów. Każdy hetman dysponuje pewną potęgą określoną liczbą w postaci 2ⁿ, gdzie n ≥ 0. Hetman może zbić innego hetmana o tej samej potędze i wtedy jego potęga wzrasta dwukrotnie.

Należy znaleźć sekwencję ruchów, która redukuje liczbę hetmanów na szachownicy do liczby nie większej niż K.

Przykład zadania

Powyższy układ hetmanów należy zredukować do K=1 hetmana.

Rozwiązaniem jest sekwencja ruchów (współrzędne podane jako wiersz kolumna):

1. 2 1 → 1 1
2. 0 1 → 1 0
3. 5 6 → 5 4
4. 3 1 → 2 2
5. 5 4 → 1 0
6. 1 1 → 1 0
7. 1 3 → 1 6
8. 1 0 → 1 2
9. 1 6 → 1 2
10. 2 2 → 1 2

Założenia

Należy założyć że:

• hetman może wykonywać ruchy jak w grze w szachy;
• szachownica ma rozmiar nie większy niż 128x128;
• łączna potęga hetmanów na szachownicy jest mniejsza od 2⁶⁰.

Dane wejściowe

Dane wejściowe należy wczytać ze standardowego wejścia formacie (opis zawartości kolejnych wierszy):

[rozmiar szachownicy - N]
[liczba do której należy zredukować liczbę hetmanów - K]
[położenie hetmanów na szachownicy – N wierszy po N liczb, każda liczba jest wartością hetmana na danym polu lub zerem]

8
1
0    1    0    0    0    0    0    0
1    2    8    8    0    0    8    0
0    2   16    0    0    0    0    0
0   16    0    0    0    0    0    0
0    0    0    0    0    0    0    0
0    0    0    0    1    0    1    0
0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0

Wynik

2 1 1 1 
0 1 1 0 
5 6 5 4 
3 1 2 2 
5 4 1 0 
1 1 1 0 
1 3 1 6 
1 0 1 2 
1 6 1 2 
2 2 1 2

Przykłady zadań

8
1
 0    1    2    1    1    0    0    0
 0    0    0    0    0    1    0    0
 0    0    0    0    0    0    0    0
 1    1    2    8    2    0    0    0
16    8    0    0   16    0    0    0
 0    0    0    0    0    0    0    0
 1    0    1    0    0    0    0    1
 0    1    0    0    0    0    0    0

8
2
16    0    0    1    8    8    4    0
 0    0    0    0    1    0    0    0
 0    0    0    0    2    0    0    0
 0    0    0    2    0    1    0    1
16    0   16    0    0    0    0    0
 0    0    2    0    0    0    0    2
32    1    0    1    0    0    2    4
 0   64    0    0    4    0    0    4

8
3
16   16    8    0   32    0    0    4
16    0    0   32    4    4    2    4
 8   16    0    0    8    0    0    8
16    0    0    0    0    0    0   16
 0    4    0    2    0    4   16   16
16    0    0    0    0    2    2   32
 2    0    0    0    0    1    1    8
 0   64   32    0    4   16   16    0

 
 8
 4
 0    0    1   16   16   64    8   16
 4    1    0    1    2    0    8   16
 4    0    1    0    8   16    4   16
 0    0    1    8    8    2    8    8
64    1    8   64    2    2    1    8
16   32    2    1    0    1    2    0
 4    1    4    8    1    0    0    4
 1    1    1    2    8    0    4   32