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

725

832

1005000


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.


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ę)


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!




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.


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


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));
  }
}

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


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


@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.





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.


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]

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ę.


1

TI-Basic, 7 bajtów

round(Ans²/2,0

Alternatywnie (8 bajtów):

int(Ans²/2+.5

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