Wprowadzenie
Wszyscy znają grę w kółko i krzyżyk, ale w tym wyzwaniu wprowadzimy mały zwrot akcji. Będziemy używać tylko krzyży . Pierwsza osoba, która stawia trzy krzyże z rzędu, przegrywa. Ciekawym faktem jest to, że maksymalna liczba krzyży, zanim ktoś straci, wynosi 6 :
X X -
X - X
- X X
Oznacza to, że dla planszy 3 x 3 maksymalna kwota wynosi 6 . Tak więc dla N = 3 musimy wyprowadzić 6.
Kolejny przykład, dla N = 4 lub płyty 4 x 4:
X X - X
X X - X
- - - -
X X - X
To optymalne rozwiązanie, widać, że maksymalna liczba krzyży wynosi 9 . Optymalne rozwiązanie dla płyty 12 x 12 to:
X - X - X - X X - X X -
X X - X X - - - X X - X
- X - X - X X - - - X X
X - - - X X - X X - X -
- X X - - - X - - - - X
X X - X X - X - X X - -
- - X X - X - X X - X X
X - - - - X - - - X X -
- X - X X - X X - - - X
X X - - - X X - X - X -
X - X X - - - X X - X X
- X X - X X - X - X - X
Daje to 74 .
Zadanie
Zadanie jest proste, biorąc pod uwagę liczbę całkowitą większą niż 0, wypisuje maksymalną liczbę krzyży, które można umieścić bez trzech X sąsiadujących w linii wzdłuż rzędu, kolumny lub po przekątnej.
Przypadki testowe
N Output
1 1
2 4
3 6
4 9
5 16
6 20
7 26
8 36
9 42
Więcej informacji można znaleźć na https://oeis.org/A181018 .
Zasady
- To jest golf golfowy , więc wygrywanie z najmniejszą ilością bajtów wygrywa!
- Możesz podać funkcję lub program.
Odpowiedzi:
Pyth,
575149 bajtówPodobnie jak rozwiązanie CJam @ PeterTaylor, jest to brutalna siła, więc działa w czasie O (n 2 2 n 2 ). Tłumacz online nie kończy się w ciągu minuty dla n = 4.
Wypróbuj tutaj dla N <4.
Wypróbuj funkcję przekątnych .
źródło
CJam (
5856 bajtów)Jest to niezwykle powolne i zajmuje dużo pamięci, ale dla ciebie to gra w golfa .
Sekcja
źródło
O(n a^n)
gdziea ~= 5.518
.DO,
460456410407362351318 bajtówTo jest naprawdę zła odpowiedź. To niezwykle wolne podejście z użyciem brutalnej siły.
Staram się trochę pograć w golfa, łączącfor
pętle.Przypadki testowe
Bez golfa
Edycja: Zadeklaruj zmienne int jako nieużywane parametry; usuń współrzędną y, po prostu użyj indeksu; przenieś zmienną na listę parametrów zamiast globalnej, napraw niepotrzebne parametry przekazywane do
s()
; połącz w pętle, usuń niepotrzebne nawiasy; zastępuje&&
się*
,||
w+
; makro-ify kontrola 3 w rzędzieźródło
#define d(x,y)b[x]*b[x+y]*b[x+y+y]
; zmieniając począteks
nas(i,m){for(m=n-2;
i zastępując wszystkie wystąpienian-2
; i zmieniającb[x]++
sięb[x++]++
i następnie zastąpieniex==n*n-1
zx==n*n
,x+1
zx
, ix
zx-1
.C 263
264 283 309Edytuj Kilka bajtów zaoszczędzonych dzięki @Peter Taylor - mniej niż się spodziewałem. Następnie 2 bajty przydzieliły więcej pamięci, teraz mogę wypróbować większy rozmiar, ale staje się to bardzo czasochłonne.
Uwaga Dodając wyjaśnienie, odkryłem, że marnuję bajty, utrzymując siatkę w tablicy R - abyś mógł zobaczyć znalezione rozwiązanie ... nie jest wymagane dla tego wyzwania !!
Usunąłem go w wersji golfowej
Program C w golfa, który w rozsądnym czasie może faktycznie znaleźć odpowiedź dla n = 1..10.
Mój test:
Mniej gra w golfa i próbuję wyjaśnić
źródło
buildRows
metodę; może nawet 20, jeślifor(scanf("%d",&n);(v=2*V[i++])<1<<n;v%8<6&&V[++j]=v+1)v&&V[++j]=v;
jest ważne. (Obecnie nie mam dostępu do kompilatora C).999
oznacza, że chcesz zignorować tę część. Chociaż może naprawdę powinieneś sprawić, by nie był zakodowany na stałe, aby w zasadzie poradzić sobie z większymi wejściami niż 11 lub 12.Rubinowy, 263 bajty
Jest to również rozwiązanie brutalnej siły i napotyka te same problemy, co odpowiedź C Cole'a Camerona, ale jest jeszcze wolniejsze, ponieważ jest rubinowe, a nie C. Ale hej, jest krótszy.
Przypadki testowe
Bez golfa
źródło
Haskell, 143 bajty
W pewnym sensie tak się nie dzieje, ale dobrze się bawiłem, więc oto:
Oto kod:
źródło