Ada N pintu dan K monyet. Awalnya, semua pintu ditutup.

Babak 1: Monyet pertama mengunjungi setiap pintu dan menghidupkannya (jika pintu itu tertutup, ia akan membukanya; jika terbuka, ia akan ditutup).

Babak 2 : Monyet pertama mengunjungi setiap pintu dan menghidupkannya. Kemudian Monyet ke-2 mengunjungi setiap pintu ke-2 dan mematikannya.

. . .

. . .

Babak k: Monyet pertama mengunjungi setiap pintu dan mematikan pintu. . . . . . . . . . Monyet k mengunjungi setiap pintu k dan beralih ke pintu.

Input: NK (dipisahkan oleh satu spasi)

Keluaran: Nomor pintu yang terbuka, masing-masing dipisahkan oleh satu ruang.

Contoh :

Input: 3 3

Output: 1 2

Kendala :

0 <N <101

0 <= K <= N

Catatan :

• Asumsikan N pintu diberi nomor dari 1 hingga N dan K monyet diberi nomor dari 1 hingga K

• Yang dengan kode terpendek menang. Juga, tampilkan output untuk N = 23, K = 21

APL, 32 28 26

{(2|+/(⍳⍺)∘.{+/0=⍺|⍨⍳⍵}⍳⍵)/⍳⍺}/⎕

⎕:
      23 21
 1 2 4 8 9 16 18 23 

Penjelasan

• {+/0=⍺|⍨⍳⍵}adalah fungsi yang mengembalikan berapa kali pintu ⍺(argumen kiri) beralih di putaran ⍵(argumen kanan), yang sama dengan jumlah faktor ⍺yang ≤ ⍵:

  • ⍳⍵ Hasilkan array numerik dari 1 hingga ⍵

  • ⍺|⍨Hitung ⍺modulus setiap item dari array itu

  • 0= Ubah ke 1 di mana ada 0, dan 0 untuk setiap hal lainnya

  • +/ Jumlah array yang dihasilkan

• Fungsi luar:

  • (⍳⍺), ⍳⍵Buat array dari 1 ke N dan 1 ke K

  • ∘.{...}Untuk setiap pasangan elemen dari dua array, terapkan fungsi. Ini memberikan matriks berapa kali beralih, setiap baris mewakili pintu dan setiap kolom mewakili putaran.

  • +/Jumlah kolom. Ini memberikan array tentang berapa kali setiap pintu diputar di semua putaran.

  • 2|Modulus 2, jadi jika pintu terbuka, itu adalah 1; jika ditutup, itu adalah 0.

  • (...)/⍳⍺ Terakhir, hasilkan array dari 1 hingga N dan pilih hanya yang memiliki 1 di array pada langkah sebelumnya.

• /⎕ Terakhir, masukkan fungsi antar angka dari input.

EDIT

{(2|+⌿0=(,↑⍳¨⍳⍵)∘.|⍳⍺)/⍳⍺}/⎕

• ,↑⍳¨⍳⍵Hasilkan semua "monyet" (Jika K = 4, maka ini 1 0 0 0 1 2 0 0 1 2 3 0 1 2 3 4)

  • ⍳⍵Array dari 1 ke ⍵(K)

  • ⍳¨ Untuk masing-masing dari itu, menghasilkan array dari 1 ke nomor itu

  • ,↑Ubah array bersarang menjadi sebuah matriks ( ↑) dan kemudian pisahkan ke array sederhana ( ,)

• (,↑⍳¨⍳⍵)∘.|⍳⍺Untuk setiap angka dari 1 hingga ⍺(N), mod dengan masing-masing monyet.

• 0=Ubah ke 1 di mana ada 0, dan 0 untuk setiap hal lainnya. Ini memberikan matriks toggle: Baris adalah masing-masing monyet di setiap putaran, kolom adalah pintu; 1 berarti toggle, 0 berarti no toggle.

• +⌿ Jumlahkan baris untuk mendapatkan array berapa kali setiap pintu di-toggle

Bagian lain tidak berubah

EDIT

{(≠⌿0=(,↑⍳¨⍳⍵)∘.|⍳⍺)/⍳⍺}/⎕

Gunakan XOR kurangi ( ≠⌿) alih-alih jumlah dan mod 2 ( 2|+⌿)

GolfScript, 33 karakter

~:k;),1>{0\{1$)%!k@-&^}+k,/}," "*

Jika pintu diberi nomor mulai dari nol akan menghemat 3 karakter.

Contoh ( online ):

> 3 3
1 2

> 23 21
1 2 4 8 9 16 18 23

Mathematica, 104 karakter

{n,k}=FromDigits/@StringSplit@InputString[];Select[Range@n,OddQ@DivisorSum[#,If[#>k,0,k+1-#]&]&]~Row~" "

Contoh:

Dalam [1]: = {n, k} = FromDigits / @ StringSplit @ InputString []; Pilih [Rentang @ n, OddQ @ DivisorSum [#, Jika [#> k, 0, k + 1 - #] &] & ] ~ Baris ~ ""

? 23 21

Keluar [1] = 1 2 4 8 9 16 18 23

Ruby, 88

Berdasarkan jawaban @ manatwork.

gets;~/ /
$><<(1..$`.to_i).select{|d|(1..k=$'.to_i).count{|m|d%m<1&&(k-m+1)%2>0}%2>0}*$&

Global yang cerdik itu selalu mematahkan sorotan sintaksis!

Python 3, 97 84

Jika monyet muncul dalam jumlah putaran genap, itu sama sekali tidak berubah. Jika seekor monyet muncul dalam jumlah genap, itu sama dengan persis satu putaran.

Dengan demikian beberapa monyet dapat ditinggalkan, dan yang lainnya hanya perlu berganti pintu sekali.

N,K=map(int,input().split())
r=set()
while K>0:r^=set(range(K,N+1,K));K-=2
print(*r)

Output untuk 23 21:

1 2 4 8 9 16 18 23

R - 74

x=scan(n=2);cat(which(colSums((!sapply(1:x[1],`%%`,1:x[2]))*x[2]:1)%%2>0))

Simulasi:

> x=scan(n=2);cat(which(colSums((!sapply(1:x[1],`%%`,1:x[2]))*x[2]:1)%%2>0))
1: 23 21
Read 2 items
1 2 4 8 9 16 18 23

javascript 148 127

function e(n,k){b=array(n);d=[];function a(c){for(i=0;i<n;i+=c)b[i]=!b[i];c<k&&a(c+1)}a(1);for(i in b)b[i]&&d.push(i);return d}

di sini adalah versi yang dapat dibaca (sedikit):

function e(n, k) {     //define N and K
     b = array(n); //declare all doors as closed
     d = [];     //create array later used to print results

     function a(c) {   //(recursive) function that does all the work
         for (i = 0; i < n; i += c)  //increment by c until you reach N and...
              b[i] = !b[i];  //toggle said doors
         c < k && a(c + 1)  //until you reach k, repeat with a new C (next monkey)
     }
     a(1); //start up A

     for (i in b) b[i] && d.push(i); //convert doors to a list of numbers
     return d //NO, i refuse to explain this....
}   //closes function to avoid annoying errors

Biola DEMO

saya harus mencatat bahwa itu mulai menghitung dari 0 (secara teknis kesalahan satu-per-satu)

JavaScript, 153

(function(g){o=[],f=g[0];for(;i<g[1];i++)for(n=0;n<=i;n++)for(_=n;_<f;_+=n+1)o[_]=!o[_];for(;f--;)o[f]&&(l=f+1+s+l);alert(l)})(prompt().split(i=l=s=' '))

Output untuk N = 23, K = 21:

1 2 4 8 9 16 18 23  

Diuji di Chrome, tetapi tidak menggunakan fitur-fitur ECMAScript baru yang mewah, jadi harus berfungsi di browser apa pun!

Saya tahu saya tidak akan pernah menang melawan entri lain dan bahwa @tryingToGetProgrammingStrainght sudah mengirimkan entri dalam JavaScript, tapi saya tidak mendapatkan hasil yang sama untuk N = 23, K = 21 karena semua orang mendapatkan itu, jadi saya pikir saya akan mencoba versi saya sendiri.

Sunting : sumber beranotasi (dalam melihat ini lagi, saya melihat tempat untuk menyimpan 3 karakter lainnya, jadi mungkin masih dapat ditingkatkan ...)

(function(g) {
    // initialise variables, set f to N
    o = [], f = g[0];

    // round counter
    // since ++' ' == 1 we can use the same variable set in args
    for (; i < g[1]; i++)
        // monkey counter, needs to be reset each round
        for (n = 0 ; n <= i; n++)
            // iterate to N and flip each Kth door
            for (_ = n; _ < f; _ += n + 1)
                // flip the bits (as undef is falsy, we don't need to initialise)
                // o[_] = !~~o[_]|0; // flips undef to 1
                o[_] = !o[_]; // but booleans are fine
    // decrement f to 0, so we don't need an additional counter
    for (;f--;)
        // build string in reverse order
        o[f] && (l = f + 1 + s + l); // l = (f + 1) + ' ' + l
    alert(l)
    // return l // use with test
// get input from user and store ' ' in variable for use later
})(prompt().split(i = l = s = ' '))
// })('23 21'.split(i = l = s = ' ')) // lazy...

// == '1 2 4 8 9 16 18 23  '; // test

Ruby - 65 karakter

(1..n).each{|d|
t=0
(1..k).each{|m|t+=n-m+1 if d%m==0}
p d if t%2>0}

n = 23, k = 21 # => 1 2 4 8 9 16 18 23 

Ini perhitungannya, dalam pseudo-code:

• Biarkan s (d) menjadi berapa kali pintu d disentuh setelah putaran k.
• s (d) = jumlah (m = 1..m = k) (d% m == 0? (n-m + 1): 0)
• pintu d terbuka setelah putaran k jika s (d)% 2 = 1 (atau> 0)

Jika Anda tidak yakin bahwa ungkapan untuk s (d) benar, lihat seperti ini:

• Misalkan s (d, r) adalah berapa kali pintu d disentuh setelah r putaran.
• s (d, k) - s (d, k-1) = jumlah (m = 1, .., m = k) (d% m == 0? 1: 0)
• s (d, k-1) - s (d, k-2) = jumlah (m = 1, .., m = (k-1)) (d% m == 0? 1: 0)
• ...
• s (d, 2) - s (d, 1) = d% 2 == 0? 1: 0
• s (d, 1) = 1
• jumlah kedua belah pihak untuk mendapatkan ungkapan di atas untuk s (d), yang sama dengan s (d, k)

PowerShell: 132

Kode Golf:

$n,$k=(read-host)-split' ';0|sv($d=1..$n);1..$k|%{1..$_|%{$m=$_;$d|?{!($_%$m)}|%{sv $_ (!(gv $_ -Va))}}};($d|?{(gv $_ -Va)})-join' '

Tidak Golf, Kode Komentar:

# Get number of doors and monkeys from user as space-delimited string.
# Store number of doors as $n, number of monkeys as $k.
$n,$k=(read-host)-split' ';

# Store a list of doors in $d.
# Create each door as a variable set to zero.
0|sv($d=1..$n);

# Begin a loop for each round.
1..$k|%{

    # Begin a loop for each monkey in the current round.
    1..$_|%{

        # Store the current monkey's ID in $m.
        $m=$_;

        # Select only the doors which are evenly divisible by $m.
        # Pass the doors to a loop.
        $d|?{!($_%$m)}|%{

            # Toggle the selected doors.
            sv $_ (!(gv $_ -Va))
        }
    }
};

# Select the currently open doors.
# Output them as a space-delimited string.
($d|?{(gv $_ -Va)})-join' '

# Variables cleanup - don't include in golfed code.
$d|%{rv $_};rv n;rv d;rv k;rv m;

# NOTE TO SELF - Output for N=23 K=21 should be:
# 1 2 4 8 9 16 18 23

Powershell, 66 byte

Berdasarkan jawaban Cary Swoveland .

param($n,$k)1..$n|?{$d=$_
(1..$k|?{($n-$_+1)*!($d%$_)%2}).Count%2}

Skrip uji:

$f = {

param($n,$k)1..$n|?{$d=$_
(1..$k|?{($n-$_+1)*!($d%$_)%2}).Count%2}

}

@(
    ,(3, 3   , 1,2)
    ,(23, 21 , 1, 2, 4, 8, 9, 16, 18, 23)
) | % {
    $n,$k,$expected = $_
    $result = &$f $n $k
    "$("$result"-eq"$expected"): $result"
}

Keluaran:

True: 1 2
True: 1 2 4 8 9 16 18 23