Tämä tehtävä on bonustehtävä, koska sen alkuperäinen malliratkaisu osoittautui vääräksi ja toimivan ratkaisun tekeminen on vaikeampaa kuin on tarkoitettua kurssilla. Saat tehtävästä pisteen automaattisesti (sinun ei tarvitse lähettää ratkaisua) mutta voit miettiä tehtävää haastavana bonustehtävänä.
Listalla on kokonaisluvut [1,2,3,...,n] jossakin järjestyksessä. Tehtäväsi on selvittää, onko lista mahdollista järjestää kahden pinon avulla.
Järjestämisessä käyt läpi listan alkiot vasemmalta oikealle. Jokaisen alkion kohdalla lisäät sen jompaankumpaan pinoon. Lisäksi saat milloin tahansa siirtää pinosta alkion tuloslistan loppuun. Tavoitteena on, että lopuksi kaikki alkiot ovat tuloslistalla järjestyksessä.
Voit olettaa, että listalla on enintään 10^5 alkiota.
Python
Toteuta tiedostoon stacksort.py
funktio check
, joka ilmoittaa, voiko listan järjestää kahden pinon avulla.
def check(t): # TODO if __name__ == "__main__": print(check([4,5,2,3,1])) # True print(check([2,3,4,5,1])) # False print(check([1,5,2,4,3])) # True
Java
Toteuta tiedostoon StackSort.java
metodi check
, joka ilmoittaa, voiko listan järjestää kahden pinon avulla.
public class StackSort { public boolean check(int[] t) { // TODO } public static void main(String[] args) { StackSort s = new StackSort(); System.out.println(s.check(new int[] {4,5,2,3,1})); // true System.out.println(s.check(new int[] {2,3,4,5,1})); // false System.out.println(s.check(new int[] {1,5,2,4,3})); // true } }