Étant donné un entier positif N
, affichez le nombre de paires d'entiers 0 <= a <= b < 2**N
tel que a*b >= 2**N
.
Règles
- Vous pouvez supposer qu'elle
N
est inférieure ou égale à la largeur de bits maximale pour les entiers dans votre langue (par exemple pour C,N
ne dépassera pas32
ou64
, selon l'architecture de la machine). Si votre langue est capable de gérer des entiers de largeur arbitraire, alors il n'y a pas de limite supérieureN
.
Cas de test
1 0
2 3
3 19
4 96
5 437
6 1876
7 7804
8 31904
9 129170
10 520135
11 2088143
12 8369175
13 33512744
14 134128704
15 536681553
16 2147082274
a <= b
condition.{0, 3, 19, 96, 437, 1876, 7804, 31904, 129170, 520135, 2088143, 8369175, 33512744, 134128704, 536681553, 2147082274, 8589086503, 34357951447}
Réponses:
Python 2,
7568 octetsEssayez-le en ligne!
Cela fonctionne dans des opérations O (2 n / 2 ) plutôt que O (2 n ) ou O (2 2 · n ), donc il fonctionne sur des entrées beaucoup plus grandes.
(Notez qu'il existe un algorithme O (2 n / 3 ) encore plus rapide .)
la source
x=0;y=0
pourx=y=0
2^{N/3}
solution.Gelée ,
1210 octetsTermine les cas de test combinés en moins de 3 secondes.
Essayez-le en ligne!
Comment ça fonctionne
la source
MATL ,
109 octetsEssayez-le en ligne!
Cela essaie toutes les paires possibles. Il manque de mémoire dans l'interpréteur en ligne pour le dépassement d'entrée
12
.Explication
la source
Brachylog , 21 octets
Essayez-le en ligne!
la source
A
à cette variable, en économisant un octet.05AB1E ,
1312 octets-1 octet grâce à Emigna
Essayez-le en ligne!
Explication
la source
P
assez ici.JavaScript (ES7),
706560 octetsCas de test
Afficher l'extrait de code
la source
Mathematica, 37 octets
Essayez-le en ligne sur http://sandbox.open.wolframcloud.com . Mathematica n'a pas de limite sur les entiers, et cet algorithme s'exécute dans le temps 2 n , il est donc très lent pour les grands
n
.la source
Clojure, 78 octets
la source
En fait , 13 octets
Essayez-le en ligne!
Une implémentation littérale du problème. Assez lent.
la source
╙;r;∙♂S╔♂π♀≥Σ
(modification mineure de la version que j'ai publiée dans le chat )PHP , 62 octets
Essayez-le en ligne!
la source
Python 2 , 53 octets
Essayez-le en ligne!
la source
Gelée , 11 octets
Essayez-le en ligne!
Une implémentation littérale du problème. Assez lent.
la source