Einführung
In dieser Herausforderung müssen Sie entscheiden, ob eine bestimmte Folge von Zahlen in zwei Teilfolgen unterteilt werden kann, von denen die eine zunimmt und die andere abnimmt. Betrachten Sie als Beispiel die Reihenfolge 8 3 5 5 4 12 3
. Es kann wie folgt in zwei Untersequenzen unterteilt werden:
3 5 5 12
8 4 3
Die Unterfolge in der ersten Reihe nimmt zu und die in der zweiten Reihe nimmt ab. Darüber hinaus sollten Sie diese Aufgabe effizient ausführen.
Eingang
Ihre Eingabe ist eine nicht leere Liste L
von ganzen Zahlen im Bereich von 0 bis einschließlich 99999. Es wird im Muttersprachenformat Ihrer Sprache angegeben oder einfach durch Leerzeichen begrenzt.
Ausgabe
Ihre Ausgabe ist ein wahrer Wert, wenn er L
in eine aufsteigende und eine absteigende Folge unterteilt werden kann, und ansonsten ein falscher Wert. Die Teilsequenzen müssen nicht unbedingt zunehmen oder abnehmen, und eine von ihnen kann leer sein.
Regeln und Boni
Sie können ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig. Darüber hinaus ist Brute Forcing in dieser Herausforderung verboten: Ihr Programm muss in der Länge der Eingabe in Polynomialzeit ausgeführt werden .
Sie müssen die beiden Teilsequenzen nicht tatsächlich zurückgeben, aber dafür gibt es einen Bonus von -20% . Damit der Bonus leichter in statisch typisierten Sprachen beansprucht werden kann, ist es akzeptabel, ein Paar leerer Listen für die falschen Instanzen zurückzugeben.
Testfälle
input -> None
Wird im Format für falsche Eingaben und input -> inc dec
für wahrheitsgemäße Eingaben angegeben. Hier ist nur ein mögliches Paar von Teilsequenzen angegeben; es kann mehr geben.
[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]