Eh bien, quand j'achète des cadeaux pour mes deux épouses, je veux qu'elles se sentent tout aussi importantes pour moi, mais c'est difficile de faire du shopping avec des budgets fixes. Au lieu de cela, j'achète un tas de choses et les divise en deux groupes avec une valeur aussi égale que possible. Ensuite, j'achète un tas de chocolats pour réparer le reste.
Mais je ne veux pas faire tout ce qui est difficile quand mon ordinateur peut le faire. Et vous non plus. Alors résolvez ce problème afin que la prochaine fois que vous aurez besoin de partager des cadeaux entre vos épouses, vous sachiez que ce sera facile.
Contribution
1 tableau d'éléments (N * 2) où N * 2 est spécifié sur la 1ère ligne.
Les éléments du tableau dans la ligne suivante.
Production
2 tableaux de N éléments chacun tels que: La
différence de (Somme des éléments du tableau 1) et (Somme des éléments du tableau 2) est aussi proche que possible de 0.
Exemple
Contribution
4
1 2 3 4
Production
1 4
2 3
diff=0
Avertissement : je n'ai pas deux femmes. Mais quand je me sens mal, j'imagine avoir deux femmes. Et soudain, je suis reconnaissant et heureux de n'en avoir qu'un. :RÉ
la source
1 1 1 1 1 5
la bonne réponse serait1 1 1
|1 1 5
, tandis que1 1 1 1 1
|5
aurait plus de sens.Réponses:
Java
Essayer de résoudre ce problème en deux phases:
Entrée comme
est déjà résolu après la phase 1 comme par exemple
et entrez comme
aura besoin des deux phases pour que
(après la première phase) devient le résultat de
Bien que je puisse garantir que cette tentative fournira toujours une solution, je ne peux pas prouver qu'une solution optimale est trouvée dans tous les cas. Avec la restriction des listes de taille égale, il semble cependant tout à fait réaliste de ne laisser aucun cas de coin. Prouve moi le contraire ;-)
Programme sur ideone.com
la source
Brachylog 2
Essayez-le en ligne!
Il s'agit d'un concours de popularité, mais cela ne signifie pas nécessairement que les langues de golf ne conviennent pas. (Vraiment, j'aurais dû répondre dans Jelly parce que les réponses à Jelly ont tendance à obtenir un nombre disproportionné de votes positifs pour une raison quelconque, peu importe qui les soumet ou comment ils jouent, mais Brachylog est plus lisible.)
Nous commençons par prendre la liste de toutes les permutations de l'entrée (
pᶠ
), et en divisant chacune (ᵐ
) en deux morceaux égaux (ḍ
; nous pourrions lui donner un indice si vous aviez plus de deux femmes pour une raison quelconque). Ensuite, nous ordonnons les permutations divisées ({…}ᵒ
) en prenant la somme (+
) de chaque (ᵐ
) moitié, en prenant la différence absolue (c'esto-
-à- dire la "différence ordonnée") et en utilisant ces différences pour définir l'ordre de tri. Le meilleur résultat est le premier, donc nous prenons la tête de la liste avech
pour obtenir le résultat.la source
Mathematica
Formulaires de saisie
La chaîne d'entrée doit être prise via STDIN.
assets
fait référence aux montants à répartir entre les épouses (ou les jumeaux).length
est le nombre d'actifs.Aux fins des présentes, nous supposerons que les actifs sont constitués des entiers de 1 à 20.
En traitement
La distribution est-elle injuste? Alors, choisissez-en un autre.
@Le constructeur note que l'épouse 2 peut contester le fait que l'épouse 1 a obtenu tous les meilleurs atouts. Ainsi, ce qui suit produit toutes les parts «justes» (différence = différence la plus faible) pour l'épouse 1; l'épouse 2 obtient les actifs restants; le zéro fait référence à la différence d'actifs pour les épouses. Il existe 5448 façons de répartir les actifs pondérés de 1 à 20. Seules quelques lignes sont affichées.
Le format est
La soumission antérieure se trouve parmi les modifications. Il est beaucoup plus inefficace, car il s'appuie sur lui
Permutations
.la source
J
Il y a une feuille de triche de toutes les primitives J sur ce lien , au cas où vous voudriez suivre à la maison. Rappelez-vous: J est généralement lu de droite à gauche, c'est-à-
3*2+1
dire 7, et non 9. Chaque verbe (J pour fonction) est soit monadique, donc devant commef y
, ou dyadique, donc entre les deuxx f y
.Notes et explications:
u/
signifie "replieru
", donc effectuez l'opération binaire sur chaque élément de la liste. Ainsi, par exemple:+/
signifie Fold Plus ou Sum ;<.
est Lesser Of , donc<./
signifie Fold Lesser Of , ou Minimum .u"1
signifie "effectueru
sur des cellules à 1 dimension", c'est-à-dire sur chaque ligne. Normalement, les verbes de J sont soit atomiques, soit s'appliquent à tout l'argument. Cela s'applique aux deux arguments si le verbe est utilisé dyadiquement (avec deux arguments). Considérer ce qui suit:#:
est un verbe qui développe un nombre dans sa représentation binaire. Lorsque vous l'utilisez sur une liste avec plus d'un élément, il alignera également tous les nombres correctement, de sorte que#:i.2^n
vous obtiendrez chaque chaîne binaire de longueurn
./.
, lorsqu'il est utilisé dyadiquement, est appelé Key . Il utilise les éléments de la liste du côté gauche comme clés et ceux du côté droit comme valeurs. Il regroupe chaque ensemble de valeurs qui partagent une clé, puis effectue une opération sur celles-ci.Dans le cas de
]/.
, l'opération n'est que le verbe d'identité, donc rien de tout à fait spécial ne s'y passe, mais le fait de/.
partitionner la liste pour nous est l'élément le plus important. C'est pourquoi nous créons les listes binaires: pour que pour chaque liste ("1
), nous puissions répartir les cadeaux pour les épouses de toutes les manières possibles.1!:1]1
et1!:2&2
sont les opérations de lecture et d'écriture, respectivement. La1!:n
partie est le verbe et l'autre nombre est le descripteur de fichier.1
est console en2
entrée, console en sortie, et3 4 5
sont stdin, stdout et stderr. Nous utilisons également".
lors de la lecture afin de convertir les chaînes d'entrée en nombres.la source
Clojure
Tester
la source
[1 4 5 6 7 8]
votre programme calculé[8 5 4]
[7 6 1]
Diff 3
où il existe clairement des solutions avec une différence de 1.MATLAB
Voici ma solution:
Par exemple, la liste actuelle de mon code source se traduit par:
qui est à la fois 16.
Si je joue à mon code, ce qui est moins amusant, je reçois 132 caractères très optimisés. Bas ça ;)
la source
PHP
Avertissement: code très sale
Il essaie toutes les permutations possibles du tableau d'entrée.
Échantillon Ideone pour
4/1 2 3 4
: http://ideone.com/gIi174la source
Python:
ou un peu golfifié:
Ou encore plus golfifié, car la moitié des lignes n'est que du maquillage. (en supposant que je peux simplement vider le tableau interne brut, car cela n'est pas spécifié dans l'op) Vous pouvez laisser de côté le
print
(par exemple) le shell interactif, et ajouter un[::-1]
(à la toute fin, après[0]
) si vous voulez vraiment le diff dernier.(résultats en
(0, ((1, 2, 7, 8), (3, 4, 5, 6)))
)Cependant, cela ne fait que renforcer brutalement toutes les combinaisons possibles et ne doit pas être considéré comme efficace à distance. Cependant, si la liste étant de longueurs égales n'a pas d'importance, cela fonctionnerait également (sur les grands tableaux):
Avec le code en dessous, par exemple, il fonctionne à peine avec une différence: 500k sur 10 ^ 10 valeur maximale n'est pas beaucoup, pour ainsi dire. C'est aussi beaucoup plus rapide: là où l'autre code ne se terminerait probablement pas dans moins d'un an (et c'est très optimiste), cela s'exécute en environ une demi-seconde, même si votre kilométrage peut varier.
la source
Alphabet Haskell
J'ai utilisé la monade de liste pour la diviser.
Ensuite, nous faisons un évaluateur.
Et puis une fonction qui minimisera la différence.
Et quelque chose qui les combine tous.
Ensuite un analyseur.
Et un formateur de sortie.
Et maintenant le programme
Exemple:
la source