potega_hetmanow

Potęga Hetmanów - projekt z przedmiotu AdPTO

Zadanie: Potęga Hetmanów

Opis:

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

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⁶⁰.

Przykład:

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

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]

Dla danych z rysunku plik ma postać:

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:

Rozwiązanie należy zapisać na standardowe wyjście jako kolejne wiersze opisujące kolejne ruchy (wiersz kolumna wiersz kolumna):

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

Wiersze i kolumny na szachownicy są numerowane od 0.

Przykłady zadań:

Uwaga: Nie wszystkie zadania jest w stanie rozwiązać (w sensownym czasie) zastosowany przeze mnie algorytm.

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

Dodatkowe informacje, programy i dane:

Dodatkowe programy i informacje zostana udostepnione pozniej.

• Program sędziego: judge.zip

Program sedziego został zaimplementowany w języku Python, dla interpreterów z rodziny 2.7. Sędzie potrafi także rysować plansze. Aby włączyć tę opcję należy w jego kodzie ustawić zmienną viewer na True.

Wywołanie sędziego:

python judge.py input output

gdzie input to opis planszy z zadaniem, a output to opis planszy z rozwiązaniem.

The original homework description:

http://home.agh.edu.pl/~faliszew/atpo2016/