Rozważ wszystkie 2^n
różne ciągi binarne długości n
i załóż n > 2
. Możesz usunąć dokładnie b < n/2
bity z każdego z ciągów binarnych, pozostawiając ciągi o długości n-b
pozostającej. Liczba pozostałych ciągów znaków zależy od tego, które bity usuwasz. Zakładając, że Twoim celem jest pozostawienie jak najmniejszej liczby różnych ciągów znaków, wyzwaniem jest napisanie kodu, aby obliczyć, jak mało możesz pozostawić jako funkcję n
.
Przykład n=3
i b = 1
. Możesz zostawić tylko dwa ciągi 11
i 00
.
Za n=9
i b = 1,2,3,4
mamy70,18,6,2
Za n=8
i b = 1,2,3
mamy40,10,4
Za n=7
i b = 1,2,3
mamy20,6,2
Za n=6
i b = 1,2
mamy12,4
Za n=5
i b = 1,2
mamy6,2
To pytanie zostało pierwotnie postawione przeze mnie w 2014 r. W innej formie na temat MO .
Wejście i wyjście
Twój kod powinien przyjmować liczbę całkowitą n
i wypisywać jedną liczbę całkowitą dla każdej wartości b
rozpoczynania od b = 0
i zwiększania.
Wynik
Twój wynik jest najwyższy, n
dla którego Twój kod wypełnia wszystko b < n/2
w ciągu minuty na moim komputerze z systemem Linux. W przypadku przerw remisowych, największy b
Twój kod otrzyma za wspólne największe n
wygrane. W przypadku zerwania remisu również na tym kryterium decyduje najszybszy kod dla największych wartości n
i b
. Jeśli czasy mieszczą się w sekundach lub dwóch, wygrywa pierwsza opublikowana odpowiedź.
Języki i biblioteki
Możesz użyć dowolnego języka biblioteki, który ci się podoba. Ponieważ muszę uruchomić kod, pomogłoby, gdyby był darmowy (jak w piwie) i działał w Linuksie.
źródło
b > 0
jako dodatkowy wymóg wejściowy? A możen=3
ib=0
po prostu wyjście2^n
jako wynik?2^n
rzeczywiście generować .n
i pojedynczeb
, ale wynik jest największy,n
dla którego kod kończy sięb < n/2
w niecałą minutę. Czy nie byłoby lepiej miećn
w tym przypadku jedno wejście i wyświetlać wszystkie wyniki0 <= b < n/2
? Albo powinniśmy zapewnić dwa programy / funkcje: jedna biorąc dwa wejścian
ib
, a jeden biorąc tylko wejścien
i wyprowadzanie wszystkie wyniki w zakresie0 <= b < n/2
?Odpowiedzi:
Python 2.7 / Gurobi n = 9
To rozwiązanie jest bardzo proste wykorzystanie solvera ILP firmy Gurobi do logicznych problemów mieszanych (MIP).
Jedyną sztuczką jest usunięcie symetrii w uzupełnieniu 1, aby zmniejszyć o połowę rozmiary problemów.
Korzystając z ograniczonej czasowo „darmowej” licencji firmy Gurobi LLC, jesteśmy ograniczeni do 2000 ograniczeń, ale rozwiązanie 10 del 1 jest poza moim 60-sekundowym terminem.
AKTUALIZACJA + CORR: 10,2 ma optymalne rozwiązanie o rozmiarze 31 (patrz np.) Gurobi pokazuje, że nie istnieje symetryczne rozwiązanie o rozmiarze 30 (zwraca problem nieosiągalny) .. [moja próba wykazania asymetrycznej wykonalności w 30 pozostawała niejednoznaczna po 9,5 godziny pracy] np. Bit wzory liczb całkowitych
0 7 13 14 25 28 35 36 49 56 63 64 95 106 118 128 147 159 170 182 195 196 200 207 225 231 240 243 249 252 255
lub0 7 13 14 19 25 28 35 36 49 56 63 64 95 106 118 128 159 170 182 195 196 200 207 225 231 240 243 249 252 255
źródło
C ++, n = 6
Brute force z kilkoma drobnymi optymalizacjami.
Uruchom lokalnie:
źródło