Ile Wazirów można umieścić na szachownicy N × N?

30

Załóżmy, że do szachów wprowadzono nowy szachy wróżki o nazwie Wazir. Waziry mogą poruszać się z pozycji ( x , y ) do:
 ( x +1, y )
 ( x , y +1)
 ( x -1, y )
 ( x , y -1)

Oznacza to, że poruszają się prostopadle jak wieża, ale tylko jeden krok naraz jak król. Ile takich wazirów można umieścić na szachownicy N × N, aby żadne dwa waziry nie mogły się nawzajem atakować?

 Na planszy 1 × 1 może znajdować się tylko 1 taki pionek.
 Na planszy 2 × 2 mogą znajdować się 2 takie elementy.
 Na planszy 3 × 3 może być 5 takich elementów.

Biorąc pod uwagę N, zwróć liczbę wazirów, które można umieścić na szachownicy N × N.

Jest to sekwencja OEIS A000982 .

Więcej przypadków testowych

7 → 25

8 → 32

100 → 5000

code-golf  number  chess 
— Sasha R.
źródło
4
Czyli Wielbłąd jest dla Wieży tym, czym Król jest dla Królowej? Tj. Może poruszać się tylko ortogonalnie i tylko jeden krok na raz.
— Adám
2
@SashaR Czy mogę przepisać twoje pytanie jako poprawne wyzwanie do gry w golfa?
— Adám
2
Pewnie! W ten sposób mogę również zobaczyć, jak sformułować pytania związane z kodowaniem słów w przyszłości
— Sasha R
15
Jako nowy użytkownik tej strony, tym razem miałeś dużo szczęścia. Wiele (nie-tematycznych) pytań programowych na tej stronie zostało trwale zamkniętych i poddanych ocenie, nie zredagowanych jako wyzwanie i tak ocenionych. Jak już wyjaśnili inni, ta strona służy wyłącznie do programowania konkursów, a nie do zadawania zadań domowych. Możesz użyć piaskownicy (na codegolf.meta.stackexchange.com/questions/2140/... ) przed wysłaniem wyzwania, aby uniknąć typowych błędów następnym razem; i zauważ, że większość użytkowników tej witryny, jak widzieliście, używa języków „nieczytelnych”.
— user202729,
16
To pytanie jest dość mylące, ponieważ Wielbłąd jest już standardową wróżką szachową dla kawałka takiego jak rycerz, który wykonuje dłuższe skoki, a opisany już kawałek ma imię wróżki: Wazir .
— Mark S.

Odpowiedzi:

33

Biała spacja , 45 bajtów

Wypróbuj online!

Nawiasem mówiąc, oto dowód, że formuła ⌈n² / 2⌉ jest poprawna.

  • Zawsze możemy umieścić co najmniej ⌈n² / 2⌉ wazirów : po prostu ułóż je w szachownicę! Zakładając, że lewy górny kafelek jest biały, na planszy n × n znajdują się białe kafelki ⌈n² / 2⌉ i czarne ⌊n² / 2⌋ czarne kafelki . A jeśli kładziemy waziry na białych kafelkach, żadne z nich nie atakuje się nawzajem, ponieważ każdy wazir „widzi” tylko czarne kafelki.

    Oto jak umieszczamy 13 wazirów na planszy 5 × 5 (każda W to wazir).

    　　　　　　　　　　13 wazirów na planszy 5 × 5

  • Nie możemy zrobić nic lepszego : dowolnie ułóżmy szachownicę kawałkami domina 2 × 1, opcjonalnie używając kawałka 1 × 1 do końcowego rogu szachownicy o nieparzystej długości, tak jak:

    　　　　　　　　　　okładka domina z planszy 5 × 5

    Potrzebujemy inon² / 2⌉ domina do pokrycia szachownicy. Oczywiście, umieszczenie dwóch wazirów na jednym dominie sprawia, że ​​mogą się one atakować! Więc każdy domino może zawierać tylko co najwyżej jeden wazir, co oznacza, że nie możemy ewentualnie umieścić więcej niż ⌈n² / 2⌉ wazirs na pokładzie.

— Lynn
źródło
Nie potrzebujesz zasady szuflady na ostatnią część: masz dokładnie ⌈n² / 2⌉ płytek, a najwyżej wielbłąda na płytkę, więc masz najwyżej ⌈n² / 2⌉ wielbłądów.
— ShreevatsaR
8
@ShreevatsaR Co gwarantuje, że nie możesz umieścić wielbłądów x> ²n² / 2⌉ w płytkach ⌈n² / 2⌉? To zasada
— szuflady
2
Na początku myślałem, że kod się nie ładuje, więc odświeżyłem stronę i nadal nie. Potem zdałem sobie sprawę, jaki język napisano na górze.
— Arthur
7
Doceniam to, że poszedłeś i zmieniłeś swoje Cna Ww dowodzie ilustracyjnym.
— Giuseppe,
4
Doceniam również to, że W są na BIAŁYCH PRZESTRZEŃ, a odpowiedź w WHITESPACE.
— corsiKa
9

APL (Dyalog) , 9 7 6 bajtów

Teraz używa formuły pana Xcodera.

Jest to ukryta funkcja anonimowego przedrostka, która przyjmuje argument N jako argument.

⌈2÷⍨×⍨

Wypróbuj online!

×⍨ kwadrat N (podświetlone selfie z mnożeniem, tj. pomnóż przez siebie)

2÷⍨ podziel przez 2

⌈ sufit (zaokrąglony w górę)

— Adám
źródło
Wow! Nie mam pojęcia, jak to zrobiłeś! Nie zrozumiałem logiki, westchnienie
— Sasha R
Cholera, ktoś już odkrył wzór.
— Feathercrown
1
Właśnie zrozumiałem, że formuła znajduje się na stronie OEIS. Prawdopodobnie nie powinien był tego powiązać.
— Feathercrown
6

dc , 6 bajtów

2^2~+p

2^: plac; 2~: podziel przez 2, przesuwając iloraz, a następnie resztę; +p: dodaj resztę do ilorazu i wydrukuj.

Wypróbuj online!

— brhfl
źródło
5

C (gcc) , 23 18 17 bajtów

f(n){n=n*n+1>>1;}

Wypróbuj online!

C (gcc) , 22 bajty (bez użycia niezdefiniowanego zachowania)

f(n){return n*n+1>>1;}

Wypróbuj online!

Niektórzy ludzie naprawdę nie lubią wykorzystywać niezdefiniowanego zachowania określonego kompilatora podczas używania określonych flag kompilatora. Takie postępowanie pozwala jednak zaoszczędzić bajty.

— Jonathan Frech
źródło
3
Dziwny sposób udzielania odpowiedzi IMO, ale: f (n) {n = n * n + 1 >> 1;}, aby zapisać bajt.
— Tahg
1
@Tahg Dzięki; choć w jaki sposób uważasz, że mój sposób udzielania odpowiedzi jest dziwny?
— Jonathan Frech
2
Nie sądziłem, że zmiana argumentu wejściowego jest normalnym sposobem zwracania wartości w C.
— Tahg
2
@YSC Jednak zdaniem kompilatora jest to zrozumiałe i tworzy plik wykonywalny, który działa.
— Jonathan Frech
5
@YSC Uważamy tutaj, na PPCG, że jeśli program działa na jednym tłumaczu, jest to poprawne zgłoszenie. Działa na tłumaczu online, dlatego jest ważny bez dalszych uwag.
— Conor O'Brien
4

Python 3 , 19 bajtów

lambda x:-(-x*x//2)

Wypróbuj online!

lambda x:-(-x*x//2)  # Unnamed function
lambda x:            # Given input x:
            x*x      # Square
           -         # Negate
               //2   # Halve and Floor (equivalent of Ceil)
         -(       )  # Negate again (floor -> ceil)

-1 bajt dzięki Mr. Xcoder

— HyperNeutrino
źródło
x**2->x*x
— Pan Xcoder,
@ Mr.Xcoder Facepalm dzięki
— HyperNeutrino
Co lambda x:x*x+1>>1?
— Alix Eisenhardt
Lub lambda x:x*x+1//2 Zastrzeżenie: Nie znam składni tego języka ani kolejności operacji, więc zgadywałem; Mówię: dodaj 1 przed tobą //2 zamiast dwa razy negować.
— Dan Henderson
@DanHenderson Nadal potrzebujesz nawiasów, w przeciwnym razie jest on parsowany jako (x*x) + (1//2), więc tak naprawdę nie jest krótszy.
— Skyler
4

język maszynowy x86_64 (Linux), 9 8 bajtów

0:       97                      xchg   %eax,%edi
1:       f7 e8                   imul   %eax
3:       ff c0                   inc    %eax
5:       d1 f8                   sar    %eax
7:       c3                      retq

Aby Spróbuj online! , skompiluj i uruchom następujący program C.

#include<stdio.h>
const char *f="\x97\xf7\xe8\xff\xc0\xd1\xf8\xc3";
int main() {
  for(int i=1; i<10; i++) {
    printf("%d\n", ((int(*)())f)(i));
  }
}
— sufitowy
źródło
3

J , 8 bajtów

Anonimowa ukryta funkcja prefiksu.

2>.@%~*:

Wypróbuj online!

*: plac

>. pułap (zaokrąglenie w górę)
@ po
2… %~ podzieleniu przez dwa

— Adám
źródło
Alternatywne rozwiązania: <.@-:@*:i*:<.@%2:
— Conor O'Brien
2
@ ConorO'Brien‽ 2>.@%~*:Skąd to wziąłem? Nie mogę tego odczytać - wygląda mi to na hałas linii…
— Adám
>.@-:@*:dostaje mój głos.
— Jonasz
1
@Jonah Jeśli zmrużysz oczy, zobaczysz wielbłąda.
— Adám,
3

R , 22 21 bajtów

cat((scan()^2+1)%/%2)

Wypróbuj online!

Kwadrat, przyrost, podział na liczby całkowite. Bułka z masłem.

Dane wejściowe ze standardowego wejścia; może zająć wejście oddzielone spacją lub znakiem nowej linii i obliczy maksymalną liczbę wazirów dla każdego rozmiaru tablicy wejściowej. Wyjście na standardowe wyjście.

-1 bajt dzięki plannapusowi

— Giuseppe
źródło
@plannapus naprawiono, dziękuję.
— Giuseppe,
2

Cubix , 11 bajtów

Iu*:^\)2,O@

Heheh :^\)

Wypróbuj online!

Rozwija się do następującej kostki:

    I u
    * :
^ \ ) 2 , O @ .
. . . . . . . .
    . .
    . .

Który jest tym samym algorytmem, którego używa wielu.

  • ^Iu : wczytaj wejściowy jako int i zmień kierunki
  • :* : dup góra stosu, pomnóż
  • \) : zmiana kierunku, przyrost
  • 2, : push 2, dzielenie liczb całkowitych
  • O@ : wypisuje jako int, program końcowy.
— Giuseppe
źródło
1

Japt , 4 bajty

Siedziałem na nich, odkąd wyzwanie zostało zamknięte.

²Ä z

Spróbuj

Objaśnienie: Kwadrat, dodaj 1, podział podłogi przez 2

Alternatywny

²ÄÁ1

Spróbuj

Objaśnienie: Kwadrat, dodaj 1, przesunięcie bitowe o 1.

— Kudłaty
źródło
1

Komentator , 19 bajtów

//{-//-}! {-#  -}<!

Wypróbuj online!

Kto potrzebuje języków gry w golfa? Mam mylące języki!

Wersja bez golfa:

5//{-8}//{5-}
print(10!= 5)
x={-1,3,4} # Smiley :-}
print(5<!=10)*/ # Weird comparision.

Wypróbuj online!

Jak to działa? Wytłumaczę, z wejściem 5

//                         - Take input.                           Tape: [5 0 0]
  {-//-}!                  - Square the input.                     Tape: [25 0 0]
  {-                         - Move one along the tape
    //                       - Copy the input to the tape.         Tape: [5 5 0]
      -}                     - Move one back along the tape
        !                    - Take the product of the tape.       Tape: [25 5 0]
         <space>           - Increment the tape head.              Tape: [26 5 0]
                 {-#  -}<! - Halve the tape head (floor division). Tape: [13 2 0]
                 {-          - Move one along the tape
                   #         - Set the tape head to 2.             Tape: [26 2 0]
                      -}     - Move one back along the tape
                        <!   - Reduce the tape by floor division.  Tape: [13 2 0]
— Cairney Coheringaahing
źródło
1

OCaml , 19 bajtów

let f n=(n*n+1)/2;;

Wypróbuj online!

Jestem trochę zdezorientowany, że nazwa zmieniła się z „wielbłądów” na „wazirs”, zanim udało mi się to napisać, ale pomyślałem, że i tak to opublikuję.

— Giuseppe
źródło
1

TI-Basic, 7 bajtów

round(Ans²/2,0

Alternatywnie (8 bajtów):

int(Ans²/2+.5
— Timtech
źródło
-int(-.5Ans²działa również
— Oki
@Oki Z pewnością tak. Chciałbym tylko, żeby mieli jakąś ceil(funkcję.
— Timtech,
1

/// , 35 bajtów

/I///,*/+,//+/I//**,/,A//*/A//,//,I

Wypróbuj online!

Pobiera dane wejściowe unarne za pomocą symbolu *, a dane wyjściowe unarne za pomocą symbolu A. Jest to dozwolone w przypadku niektórych określonych języków, w tym /// ( meta )

Ponieważ nie ma możliwości przyjęcia danych wejściowych w ///, dane wejściowe powinny być zakodowane na stałe:

/I/«put input here»//,*/+,//+/I//**,/,A//*/A//,//,I

dla danych wejściowych = 4.

Objaśnienie: (przed czytania, trzeba wiedzieć, że tylko składnia ///to /pattern/replacement/, co zastąpi każde wystąpienie patternprzez replacementoraz \na ucieczkę; inne znaki są drukowane na wyjściu)

Dla n=4:

/I/****//,*/+,//+/I//**,/,A//*/A//,//,I    Start program.
/I/****/                                   Replace all `I` in the program by the input.

/,*/+,//+/****//**,/,A//*/A//,//,****      Remaining part of the program.
/,*/+,/                                    Use the `,` as a scanner, scan through `*` after it and convert to `+`.
       /+/****//**,/,A//*/A//,//++++,      Note that only `*` in the second group is affected.
       /+/****/                            Replace all `+` (which is just created) by `n` asterisks (from the first `I` group)

/**,/,A//*/A//,//****************,         Now at the last of the program before the `,` there are `n²` asterisks.
/**,/,A/                                   Scan the `,` to the left to perform division by 2:
                                           replace each `**` by a `A` as the scanner `,` pass through.
/*/A//,//,AAAAAAAA                         Remaining program.
/*/A/                                      If there is any `*` remaining (if `n²` is odd), replace it with `A`.
     /,//                                  Remove the scanner `,`.
          AAAAAAAA                         Output the result.
— użytkownik202729
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.