Permutation Spiel - 2. Eingabe Fall - Erklärung

Question

Permutation Spiel (30 Punkte)

Alice und Bob das folgende Spiel spielen:

1) Sie wählen eine Permutation der ersten Zahlen N mit zu beginnen.

2) Sie spielen abwechselnd und Alice spielt zuerst.

3) In einer Runde können sie jede verbleibende Zahl aus der Permutation entfernen.

4) Das Spiel endet, wenn die verbleibenden Zahlen eine steigende Sequenz bilden. Die Person, die den letzten Zug gespielt hat (danach wird die Reihenfolge größer), gewinnt das Spiel.

Vorausgesetzt beide spielen optimal, wer gewinnt das Spiel?

Eingabe:
Die erste Zeile enthält die Anzahl der Testfälle T. T Testfälle folgen. Jeder Fall enthält eine Ganzzahl N in der ersten Zeile, gefolgt von einer Permutation der Ganzzahlen 1..N in der zweiten Zeile.

Ausgang:
Ausgang T Linien, eine für jeden Testfall mit „Alice“, wenn Alice das Spiel und „Bob“ sonst gewinnt.

Constraints:
< 1 = T < = 100
= N < = 15

Die Permutation wird eine wachsende Folge zunächst nicht sein.

Probe Input:

Beispielausgabe:
Alice
Bob

Erläuterung: Für die Im ersten Beispiel kann Alice die 3 oder die 2 entfernen, um die Reihenfolge zu erhöhen und das Spiel zu gewinnen .

Kann ich bitte jemand helfen, auf dem zweiten Eingang Fall out: 5 3 2 1 4

Die zunehmenden Sequenzen möglich sind:
1) 3 4 - Entfernen von 5, 2, 1 in beliebiger Reihenfolge
2) 2 4 - Entfernen 5, 3, 1 in beliebiger Reihenfolge
3) 1 4 - 5, 3, 2 in beliebiger Reihenfolge Alice

so dass die Ausgabe sein sollte zu entfernen?

Bitte teilen Sie keinen Code. Danke

Answer 1

Wenn Alice jeder 5,3,2,1 entfernt dann Bob entfernt 4. So kann die zunehmende Sequenz nur aus einem Element bestehen, Elemente können in beliebiger Reihenfolge entfernt werden. Daher gewinnt Bob.

Wenn Alice 4 entfernt, dann muss auch die steigende Sequenz von einem Element sein. Bob gewinnt.

So gewinnt Bob.

Answer 2

HINWEIS: Dies ist kein Programmierproblem und gehört wirklich nicht auf dieser Seite ...

Es sieht sicher wie Alice sollte der Gewinner des zweiten Testfall sein.

Fluss:

// Start state 
5 3 2 1 4 

// Alice remove 5 
3 2 1 4 

// Bob remove 3, 2, or 1 
(2 1 4) or (3 1 4) or (3 2 4) 

// Alice remove first number remaining 
(1 4) or (2 4) 

// Alice won! 

Answer 3

Ein möglicher Fall 4 sein könnte oder 5 zu erhöhen seq

Da die Eingangsparameter betrachtet wird, sind n> = 2

Aber Alice würde optimal spielen und entfernen 5