Il y a N portes et K singes. Au départ, toutes les portes sont fermées.

Tour 1: Le 1er singe visite chaque porte et fait basculer la porte (si la porte est fermée, elle est ouverte; si elle est ouverte, elle se ferme).

Tour 2 : Le 1er singe visite chaque porte et bascule la porte. Ensuite, le 2ème singe visite toutes les 2 portes et fait basculer la porte.

. . .

. . .

Round k: Le 1er singe visite chaque porte et fait basculer la porte. . . . . . . . . . Le kième singe visite chaque kième porte et fait basculer la porte.

Entrée: NK (séparé par un seul espace)

Sortie: numéros de porte ouverts, séparés chacun par un seul espace.

Exemple :

Entrée: 3 3

Sortie: 1 2

Contraintes :

0 <N <101

0 <= K <= N

Remarque :

• Supposons que N portes sont numérotées de 1 à N et K singes sont numérotés de 1 à K

• Celui avec le code le plus court gagne. Afficher également la sortie pour N = 23, K = 21

APL, 32 28 26

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

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

Explication

• {+/0=⍺|⍨⍳⍵}est une fonction qui renvoie le nombre de fois que la porte ⍺(argument de gauche) est basculée sur round ⍵(argument de droite), ce qui équivaut au nombre de facteurs ⍺qui est ≤ ⍵:

  • ⍳⍵ Générer un tableau numérique de 1 à ⍵

  • ⍺|⍨Calculer le ⍺module pour chaque élément de ce tableau

  • 0= Passez à 1 où il y avait un 0 et un 0 pour tout le reste

  • +/ Additionner le tableau résultant

• La fonction extérieure:

  • (⍳⍺), ⍳⍵Générer des tableaux de 1 à N et 1 à K

  • ∘.{...}Pour chaque paire d'éléments des deux tableaux, appliquez la fonction. Cela donne une matrice de nombre de basculements, chaque rangée représente une porte et chaque colonne représente un rond.

  • +/Additionnez les colonnes. Cela donne un tableau du nombre de fois que chaque porte est basculée sur tous les tours.

  • 2|Module 2, donc si une porte est ouverte, c'est un 1; s'il est fermé, c'est un 0.

  • (...)/⍳⍺ Enfin, générez un tableau de 1 à N et sélectionnez uniquement ceux où il y a un 1 dans le tableau à l'étape précédente.

• /⎕ Enfin, insérez la fonction entre les nombres de l'entrée.

ÉDITER

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

• ,↑⍳¨⍳⍵Générez tous les "singes" (si K = 4, alors c'est 1 0 0 0 1 2 0 0 1 2 3 0 1 2 3 4)

  • ⍳⍵Tableau de 1 à ⍵(K)

  • ⍳¨ Pour chacun d'entre eux, générez un tableau de 1 à ce nombre

  • ,↑Convertissez le tableau imbriqué en matrice ( ↑), puis démêlez-le en un tableau simple ( ,)

• (,↑⍳¨⍳⍵)∘.|⍳⍺Pour chaque nombre de 1 à ⍺(N), modifiez-le avec chaque singe.

• 0=Changez pour un 1 où il y avait un 0 et un 0 pour tout le reste. Cela donne une matrice de bascules: les lignes sont chaque singe à chaque tour, les colonnes sont des portes; 1 signifie une bascule, 0 signifie pas de bascule.

• +⌿ Additionnez les lignes pour obtenir un tableau de nombre de fois que chaque porte est basculée

Les autres pièces ne sont pas modifiées

ÉDITER

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

Utilisez XOR Reduce ( ≠⌿) au lieu de sum et mod 2 ( 2|+⌿)

GolfScript, 33 caractères

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

Si les portes étaient numérotées en commençant par zéro, cela économiserait 3 caractères.

Exemples (en ligne ):

> 3 3
1 2

> 23 21
1 2 4 8 9 16 18 23

Mathematica, 104 caractères

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

Exemple:

Dans [1]: = {n, k} = FromDigits / @ StringSplit @ InputString []; Sélectionnez [Range @ n, OddQ @ DivisorSum [#, If [#> k, 0, k + 1 - #] &] & ] ~ Ligne ~ ""

? 23 21

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

Rubis, 88

Basé sur la réponse de @ manatwork.

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

Ces globales louches cassent toujours la coloration syntaxique!

Python 3, 97 84

Si un singe apparaît dans un nombre pair de tours, cela ne change pas du tout. Si un singe apparaît un nombre pair de fois, c'est la même chose qu'exactement un tour.

Ainsi, certains singes peuvent être laissés de côté, et les autres n'ont qu'à changer de porte une fois.

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

Sortie pour 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))

Simulation:

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

voici une (minuscule) version lisible:

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

DEMO violon

je dois noter qu'il commence à compter à partir de 0 (techniquement, une erreur au coup par coup)

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=' '))

Sortie pour N = 23, K = 21:

1 2 4 8 9 16 18 23  

Testé dans Chrome, mais n'utilise pas de nouvelles fonctionnalités ECMAScript de fantaisie donc devrait fonctionner dans n'importe quel navigateur!

Je sais que je ne gagnerai jamais contre les autres entrées et que @tryingToGetProgrammingStrainght a déjà soumis une entrée en JavaScript, mais je n'obtenais pas les mêmes résultats pour N = 23, K = 21 que tout le monde obtenait cela, alors j'ai pensé que je voudrais essayer ma propre version.

Edit : source annotée (en regardant à nouveau, j'ai repéré des endroits pour enregistrer encore 3 caractères, donc ça peut probablement être encore amélioré ...)

(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 caractères

(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 

Voici le calcul, en pseudo-code:

• Soit s (d) le nombre de fois où la porte d est touchée après k tours.
• s (d) = somme (m = 1..m = k) (d% m == 0? (n-m + 1): 0)
• la porte d est ouverte après k tours si s (d)% 2 = 1 (ou> 0)

Si vous n'êtes pas convaincu que l'expression de s (d) est correcte, regardez-la de cette façon:

• Soit s (d, r) le nombre de fois que la porte d est touchée après r tours.
• s (d, k) - s (d, k-1) = somme (m = 1, .., m = k) (d% m == 0? 1: 0)
• s (d, k-1) - s (d, k-2) = somme (m = 1, .., m = (k-1)) (d% m == 0? 1: 0)
• ...
• s (d, 2) - s (d, 1) = d% 2 == 0? dix
• s (d, 1) = 1
• additionner les deux côtés pour obtenir l'expression ci-dessus pour s (d), qui est égale à s (d, k)

PowerShell: 132

Code golf:

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

Code non golfé, commenté:

# 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 octets

Basé sur la réponse de Cary Swoveland .

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

Script de test:

$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"
}

Production:

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