introduction

Dans ce défi, votre tâche consiste à décider si une séquence donnée de nombres peut être séparée en deux sous-séquences, dont l'une augmente et l'autre diminue. À titre d'exemple, considérons la séquence 8 3 5 5 4 12 3. Il peut être divisé en deux sous-séquences comme suit:

  3 5 5   12
8       4    3

La sous-séquence de la première ligne augmente et celle de la deuxième ligne diminue. En outre, vous devez effectuer cette tâche efficacement.

Contribution

Votre entrée est une liste non vide Ld'entiers compris entre 0 et 99999 inclus. Il est donné au format natif de votre langue, ou simplement délimité par des espaces.

Production

Votre sortie est une valeur vraie si elle Lpeut être divisée en une sous-séquence croissante et une sous-séquence décroissante, et une valeur fausse sinon. Les sous-séquences n'ont pas besoin d'être strictement croissantes ou décroissantes, et l'une ou l'autre peut être vide.

Règles et bonus

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites. De plus, le forçage brutal est interdit dans ce challenge: votre programme doit s'exécuter en temps polynomial dans la longueur de l'entrée .

Vous n'êtes pas obligé de retourner réellement les deux sous-séquences, mais il y a un bonus de -20% pour le faire. Pour rendre le bonus plus facile à réclamer dans des langues tapées statiquement, il est acceptable de renvoyer une paire de listes vides pour les instances de falsification.

Cas de test

Donné dans le format input -> Nonedes entrées fausses et input -> inc decdes entrées véridiques. Une seule paire possible de sous-séquences est donnée ici; il peut y en avoir plus.

[4,9,2,8,3,7,4,6,5] -> None
[0,99999,23423,5252,27658,8671,43245,53900,22339] -> None
[10,20,30,20,32,40,31,40,50] -> None
[49,844,177,974,654,203,65,493,844,767,304,353,415,425,857,207,871,823,768,110,400,710,35,37,88,587,254,680,454,240,316,47,964,953,345,644,582,704,373,36,114,224,45,354,172,671,977,85,127,341,268,506,455,6,677,438,690,309,270,567,11,16,725,38,700,611,194,246,34,677,50,660,135,233,462,777,48,709,799,929,600,297,98,39,750,606,859,46,839,51,601,499,176,610,388,358,790,948,583,39] -> None
[0,1,2,3,4] -> [0,1,2,3,4] []
[4,3,2,1,0] -> [] [4,3,2,1,0]
[1,9,2,8,3,7,4,6,5] -> [1,2,3,4,6] [9,8,7,5]
[71414,19876,23423,54252,27658,48671,43245,53900,22339] -> [19876,23423,27658,48671,53900] [71414,54252,43245,22339]
[10,20,30,20,30,40,30,40,50] -> [10,20,20,30,40,40,50] [30,30]
[0,3,7,13,65,87,112,43,22,1] -> [0,3,7,13,65,87,112] [43,22,1]
[7,4,4,7,4,7,7,4,7,4,4,4,7,7] -> [7,7,7,7,7,7,7] [4,4,4,4,4,4,4]
[7,997,991,957,956,952,7,8,21,924,21,923,22,38,42,44,920,49,58,67,71,83,84,85,917,89,907,896,878,878,90,861,115,860,125,128,140,148,858,155,160,836,164,182,826,191,824,805,195,792,205,782,206,210,769,213,756,748,214,745,724,701,234,241,693,268,685,293,679,297,334,671,336,669,341,652,356,648,362,364,370,375,386,630,622,388,389,618,398,408,468,615,470,533,611,539,544,609,586,582,572,565,547,602,536,619,624,528,512,631,640,649,669,671,677,505,678,723,743,489,489,473,454,757,446,445,758,759,764,445,431,770,429,426,418,409,790,383,379,366,363,791,358,795,809,827,835,356,353,841,844,333,867,323,317,879,311,881,309,896,282,281,897,263,904,237,236,226,202,195,914,186,177,917,920,157,926,936,154,138,943,131,945,100,98,947,957,964,95,973,989,57,43,32,21,16,13,11,8,0] -> [7,7,8,21,21,22,38,42,44,49,58,67,71,83,84,85,89,90,115,125,128,140,148,155,160,164,182,191,195,205,206,210,213,214,234,241,268,293,297,334,336,341,356,362,364,370,375,386,388,389,398,408,468,470,533,539,544,586,602,619,624,631,640,649,669,671,677,678,723,743,757,758,759,764,770,790,791,795,809,827,835,841,844,867,879,881,896,897,904,914,917,920,926,936,943,945,947,957,964,973,989] [997,991,957,956,952,924,923,920,917,907,896,878,878,861,860,858,836,826,824,805,792,782,769,756,748,745,724,701,693,685,679,671,669,652,648,630,622,618,615,611,609,582,572,565,547,536,528,512,505,489,489,473,454,446,445,445,431,429,426,418,409,383,379,366,363,358,356,353,333,323,317,311,309,282,281,263,237,236,226,202,195,186,177,157,154,138,131,100,98,95,57,43,32,21,16,13,11,8,0] 

Pyth, 34 octets

.N|!N|&ghNT:tNhNY&gYhN:tNThN:QZ^T5

Suite de tests

Utilise la récursivité mémorisée pour réduire le temps d'exécution. Définit une fonction à 3 entrées :, qui prend le suffixe de liste des entrées, fin de la séquence croissante, fin de la séquence décroissante.

Brachylog , 16 octets - 20% = 12,8 (mais ce n'est certainement pas polynomial)

⊇≥₁X&⊇≤₁Y;X.cp?∧

Essayez-le en ligne!

Échoue s'il n'y a pas de paire de sous-séquences conformes et les génère via sa variable de sortie s'il y en a une (mais s'imprime simplement true.si elle est exécutée en tant que programme). Je dis qu'il est presque certainement pas polynomiale parce que la beauté de Brachylog est que depuis qu'il est un langage déclaratif, vous ne le faites pas beaucoup de la manière de mettre en œuvre un algorithme que vous venez de décrire les relations entre les variables et de demander à l'ordinateur de manivelle résultats . Donc, il y a des chances que ce soit de la force brute hardcore, mais j'ai passé suffisamment de temps à copier les cas de test (dont deux fois), je pense que je devrais le soumettre de toute façon, si pour aucune autre raison que de faire glisser ce défi vers le haut à l'arrière de la liste des "plus récents" problèmes de décision .

   X                X is a
 ≥₁                 non-increasing
⊇                   sublist of the input
    &               and
        Y           Y is a
      ≤₁            non-decreasing
     ⊇              sublist of the input
         ;X         which paired with X
           .        is the output variable
            c       which when its elements are concatenated
             p      is a permutation of
              ?     the input
               ∧    which is not unified with the output.

Haskell , 65 octets

(>[]).foldl(%)[(0,9^6)]
p%x=do(u,d)<-p;[(x,d)|x>=u]++[(u,x)|x<=d]

Essayez-le en ligne!

Itère dans la liste, suivant les paires possibles (u,d)du maximum de la séquence croissante et du minimum de la séquence décroissante. Chaque nouvel élément xremplace soit uou d, ce qui correspond à son ajout à cette sous-séquence. Il se peut que les deux options, ou aucune, ne soient valides. Au final, on vérifie que la liste des possibilités n'est pas vide.

Les limites initiales (0,9^6)utilisent que le problème spécifie les nombres compris entre 0 et 99999. Une solution plus générale pourrait être apportée (1/0,-1/0)à make (-inf,inf).