Wyzwanie z prostymi regułami, ale nietrywialnymi algorytmami. :-)
Zadanie
Weź dane wejściowe w postaci liczb całkowitych oddzielonych spacją:
N A B S
Gdzie N jest długością boku kwadratowej macierzy 2D wypełnionej unikalnymi liczbami (liczbami całkowitymi) między A i B włącznie. Dla każdego wiersza i kolumny w tej macierzy suma jest zawsze taka sama: S. (Innymi słowy, macierz jest półmagicznym kwadratem).
Uwaga:
Wszystkie liczby są dodatnie. Wyjątkiem jest A, które może wynosić 0.
Przykłady
Dla
3 1 10000 2015
poprawnym rozwiązaniem byłoby
Dla
8 1 300 500
poprawnym rozwiązaniem byłoby
Wydajność
Dane wyjściowe powinny być tabelą ASCII. Przykład dla pierwszego przykładu powyżej:
384 159 1472
1174 499 342
457 1357 201
Wyrównane do prawej liczby całkowite wypełnione spacjami. Szerokość każdej kolumny to szerokość największej liczby całkowitej w tej kolumnie.
Punktacja
To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach. Obowiązują standardowe luki (szczególnie w przypadku wbudowanych rozwiązań tego problemu). Nie musisz się przejmować błędnymi lub w inny sposób niemożliwymi danymi wejściowymi (w tym liczbami ujemnymi). Podaj przykładowy wynik w swojej odpowiedzi (obowiązkowy) dla drugiego przykładu powyżej.
A
,B
, iN
mogą być ujemne?Odpowiedzi:
CJam,
11991 bajtówJest to możliwe do udowodnienia, niedeterministyczne podejście.
Na moim pulpicie drugi przypadek testowy zazwyczaj kończy się w mniej niż 10 minut.
Pierwsza sprawa kończy się natychmiast. Wypróbuj online w interpretatorze CJam .
Przykładowy przebieg
Pomysł
Bez ograniczeń czasowych możemy po prostu losowo generować kwadraty, aż do znalezienia prawidłowego kwadratu. To podejście opiera się na tym pomyśle, dodając dwie optymalizacje:
Zamiast pseudolosowego generowania kwadratu o długości boku N , generujemy kwadraty o długości boku N-1 , dodajemy jedną kolumnę, aby utworzyć prostokąt N × (N-1), którego rzędy mają sumę S , a następnie jeden wiersz, aby utworzyć kwadrat o długość boku N , których słupy mają sumy S .
Ponieważ suma elementów wszystkich kolumn będzie NS a suma elementów pierwszych N-1 rzędami wynosi (n-1), S , ostatni wiersz również sumy S .
Jednak ten proces może generować nieprawidłową macierz, ponieważ nie ma gwarancji, że wszystkie elementy ostatniego wiersza i kolumny będą unikalne lub mieszczą się w zakresie [A ... B] .
Wybieranie losowo kwadratu unikatowych liczb całkowitych w [A ... B] i długości boku N-1 równomiernie zajęłoby dużo czasu. W jakiś sposób musimy nadać priorytet kwadratom, które mają większą szansę na uzyskanie prawidłowego kwadratu o długości boku N po zastosowaniu procesu opisanego w poprzednim punkcie.
Biorąc pod uwagę, że każdy wiersz i kolumnę musi mieć sumy S , jej elementy mają średnio S / N . Zatem wybranie większej liczby elementów zbliżonych do tej średniej powinno zwiększyć nasze szanse.
Dla każdego I w [A ... B] pseudolosowo wybieramy liczbę zmiennoprzecinkową od 0 do (I - S / N) 2 + 1 i sortujemy elementy [A ... B] według wybranych liczb zmiennoprzecinkowych. Zachowujemy pierwsze N 2 liczby i umieszczamy je w kolejności czytania w kwadracie.
Zakładając idealnie równomierny rozkład wszystkich liczb rzeczywistych między 0 a (I - S / N) 2 + 1 na każdym etapie, wszystkie kwadraty mają niezerowe prawdopodobieństwo wybrania, co oznacza, że proces ostatecznie się zakończy.
Kod
źródło