Sherlock Holmes devient paranoïaque sur le professeur Moriarty, son archenemy. Tous ses efforts pour maîtriser le Moriarty ont été vains. Ces jours-ci, Sherlock travaille sur un problème avec le Dr Watson. Watson a mentionné que la CIA a été confrontée à des problèmes étranges avec leur supercalculateur, "la bête", récemment.
Cet après-midi, Sherlock a reçu une note de Moriarty, disant qu'il a infecté "la bête" avec un virus . De plus, la note avait le numéro n imprimé dessus. Après quelques calculs, Sherlock a compris que la clé pour éliminer le virus est le plus grand nombre «décent» ayant N chiffres.
Un nombre "décent" a -
Pendant ce temps, le compteur à la destruction de 'la bête' fonctionne très vite. Pouvez-vous enregistrer «la bête» et trouver la clé avant Sherlock?
Format d'entrée La 1ère ligne contiendra un entier T, le nombre de cas de test. Ceci est suivi de T lignes T, chacun contenant un entier N.e. Le nombre de chiffres dans le format de sortie numéro
Plus grand nombre décent ayant n chiffres. Si aucun numéro de ce type n'existe, informez Sherlock qu'il a mal et imprimez '-1'
contraintes 1 <= t <= 20 1 <= n <= 100000
explication Pour n = 1, il n'y a pas de tel numéro.
pour n = 3, 555 n'est que le nombre possible.
pour n = 5, 33333 n'est que le nombre possible.
pour n = 11, 55555333333 et Toutes les permutations de chiffres sont des nombres valides, parmi eux, le nombre donné est le plus grand.
Quelqu'un peut-il expliquer le raisonnement derrière cela? Spécifiquement, quelle est la mission de la variable "C"?
Source: https: //www.hackerrank.com/challenges/sherlock-and-the-beast
4 Réponses :
OK, la pensée va quelque chose comme ça.
5 s et combien 3 s souhaité, vous devez fronquer le 5 s . La commande ne fait aucune chance de savoir si le nombre est décent; Mais ce sera plus grand si le 5 s est à l'avant.
- Le nombre de
3 s Vous voulez être le plus petit numéro qui satisfasse les contraintes, car vous aurez alors plus 5 S, ce qui fait un plus grand nombre.
- Le nombre de
3 s doit être divisible par 5. Cela signifie qu'il n'y a jamais de point à avoir plus de 10 3 S: Vous ne devez considérer que 0, 5 ou 10 3 s. En effet, vous voulez que le plus petit nombre laisse le nombre de chiffres restants divisibles par 3, pour satisfaire à l'autre contrainte. Si vous avez 15 3 S fonctionne, il suffit donc de 0 3 s; Si 20 fonctionne, alors 5; Si 25 fonctionne, alors 10. En général, soustrayez 15 du nombre de 3 S laissera les contraintes toujours satisfaites si elles étaient auparavant.
- Le nombre de
5 s doit donc être n-0 ou n-5 ou n-10 N-10 et nous voulons que celui qui donne un numéro divisible par 3. Le calcul c = 5 * (2 * N% 3) vous donnera 0 3 s et donc n 5 s si n était déjà divisible par 3; et 10 3 s et donc n-10 5 s si n était supérieur à un multiple de 3, Dans quel cas N-10 est toujours divisible par 3; et ainsi de suite.
- La seule chose à tester est de savoir si le calcul de
C 3 s et nc 5 s satisfait le Contrainte implicite que NC devrait être non négatif. Si c'est négatif, il n'y a pas de solution; Si c'est non négatif, il s'agit d'une solution valide et de chargement frontal Le 5 s vous donnera la plus grande solution de cette telle.
Il s'agit d'une part assez large de problèmes de "programmation" où le test ne voit pas vraiment si vous pouvez frapper du code qui fait le travail, mais de voir si vous pouvez réduire le problème logiquement au point de vue. où il est trivial et peut être résolu très efficacement.
une solution mathématique:
laissez A = len des "5's, b = len des '3's. Donc
Nous savons que 3 divise A, et 5 divise B, alors laissez A = 3n, b = 5m
Ceci est une équation diophantine ( http://fr.wikipedia.org/wiki/diophantantine_quation ) avec une solution être (N0, M0) = (2n, -n) et solution générale
Le problème est maintenant de minimiser la quantité 3K-N ( Par exemple, si N = 10 ou 11, nous recherchons 3K = 12, ou K = 4.
3K-N est donc la distance entre N et ce prochain multiple de 3. L'auteur de la solution affirme que 3K-N = 2N% 3, et vous prouvez cela par épuisement, évaluant le boîtier pour lequel n% 3 = 0, 1, et 2. Pour le compte rendu, le "2" dans l'expression "2n% 3" n'est pas unique, cela fonctionnerait pour un certain nombre de séquences 2, 5, 8, 11 ... et pourquoi L'auteur a choisi cette expression particulière, je ne peux pas dire.
Vous pouvez également penser à la manière dont N% 3 dans ce sens est la fermeture de la norme n ° du multiple inférieur de 3. a + b = n
3n + 5m = n
(n, m) = (5k + 2n, 3k-n), k tout entieur
La solution ne devrait-elle pas être (n, m) = (2n + 5k, -n -3k), k tout entieur ? Parce que pour ce qui est écrit en wikipeida Page: si (x, y) est une solution, les autres solutions ont la forme (x + kv, y-ku), où k est un entier arbitraire, et u et v sont les quotients d'A et B (respectivement) par le plus grand diviseur commun d'A et B. donc x = 2n, y = -n, v = 5, u = 3 vous êtes En supposant u = -3 , pourquoi? Merci.
Je pense que les maths ont aidé un peu et je lisons sur les différentes parties de celui-ci et de l'histoire. Ma solution a passé les 15 tests à la première fois, alors que je n'utilisais pas les mathématiques, ma prise en charge peut vous aider. J'ai manipulé 10 et moins comme des cas de bord que je viens de codé dur. Quelque chose de plus de 10 j'ai divisé par 3 pour obtenir le plus "555" s. Bien sûr, lors de la division par 3, le reste ne peut être que 0, 1 ou 2. zéro sûr, cela signifie simplement écrire 555 mais plusieurs fois. Un moyen de soustraire 3 des 555s pour revenir à 10 emplacements ouverts pour les 10 trois. Deux moyens soustrayez 1 des 555s qui laisse 5 emplacements pour un 333333.
3 IFS pour les restes. 10 IFS pour les cas de bord. 1 si pour les contraintes. 1 pour.
x = int(raw_input())
while x!= 0 :
y=int(raw_input())
z=y
while(z%3!=0):
z-=5
if(z<0):
print '-1'
else:
print z*'5'+(y-z)*'3'
x = x-1
If the number(say 66317) is not divisible by 3, it will leave a modulo of either 0,1 or 2. If I decrease the number by 5, I am basically making it a multiple of 3, and the remaning digits will be a multiple of 5 as I am subtracting it from the number.modulo 0 implies number divisibile modulo 1 implies 5 needs to be subtracted twice. modulo 2 implies 5 needs to be subtracted once.
Eh bien, d'abord,
2 * n% 3 va être0 sin est divisible par 3,2 Si c'estn-1 est divisible par 3,1 sin + 1 est divisible par 3. donc,c va être0 ,10 ou5 dans ces trois cas. (Imprimer[5 * (2 * N% 3) pour N dans la plage (20)] S'il n'est toujours pas clair.) Et remarquez ce queC est utile pour -Vous avezNC 5 etC 3. Est-ce suffisant pour le comprendre?