Card Game
Two players decided to play one interesting card game.
There is a deck of 𝑛n cards, with values from 11 to 𝑛n. The values of cards are pairwise different (this means that no two different cards have equal values). At the beginning of the game, the deck is completely distributed between players such that each player has at least one card.
The game goes as follows: on each turn, each player chooses one of their cards (whichever they want) and puts on the table, so that the other player doesn't see which card they chose. After that, both cards are revealed, and the player, value of whose card was larger, takes both cards in his hand. Note that as all cards have different values, one of the cards will be strictly larger than the other one. Every card may be played any amount of times. The player loses if he doesn't have any cards.
For example, suppose that 𝑛=5n=5, the first player has cards with values 22 and 33, and the second player has cards with values 11, 44, 55. Then one possible flow of the game is:
The first player chooses the card 33. The second player chooses the card 11. As 3>13>1, the first player gets both cards. Now the first player has cards 11, 22, 33, the second player has cards 44, 55.
The first player chooses the card 33. The second player chooses the card 44. As 3<43<4, the second player gets both cards. Now the first player has cards 11, 22. The second player has cards 33, 44, 55.
The first player chooses the card 11. The second player chooses the card 33. As 1<31<3, the second player gets both cards. Now the first player has only the card 22. The second player has cards 11, 33, 44, 55.
The first player chooses the card 22. The second player chooses the card 44. As 2<42<4, the second player gets both cards. Now the first player is out of cards and loses. Therefore, the second player wins.
Who will win if both players are playing optimally? It can be shown that one of the players has a winning strategy.
Input
Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1≤𝑡≤1001≤t≤100). The description of the test cases follows.
The first line of each test case contains three integers 𝑛n, 𝑘1k1, 𝑘2k2 (2≤𝑛≤100,1≤𝑘1≤𝑛−1,1≤𝑘2≤𝑛−1,𝑘1+𝑘2=𝑛2≤n≤100,1≤k1≤n−1,1≤k2≤n−1,k1+k2=n) — the number of cards, number of cards owned by the first player and second player correspondingly.
The second line of each test case contains 𝑘1k1 integers 𝑎1,…,𝑎𝑘1a1,…,ak1 (1≤𝑎𝑖≤𝑛1≤ai≤n) — the values of cards of the first player.
The third line of each test case contains 𝑘2k2 integers 𝑏1,…,𝑏𝑘2b1,…,bk2 (1≤𝑏𝑖≤𝑛1≤bi≤n) — the values of cards of the second player.
It is guaranteed that the values of all cards are different.
Jag har ingen aning om hur jag ska börja! Har speciellt problem med den här delen"Who will win if both players are playing optimally?"
Menar du att du inte förstår vad de frågar efter? Eller hur man ska börja lösa det?
(Du har säkert märkt att alla matematiska uttryck har blivit dubblerade, så att det står t. ex. n=5n=5 när det ska stå n=5.)
Laguna skrev:Menar du att du inte förstår vad de frågar efter? Eller hur man ska börja lösa det?
(Du har säkert märkt att alla matematiska uttryck har blivit dubblerade, så att det står t. ex. n=5n=5 när det ska stå n=5.)
ja dels vad de frågar efter men faktum är att det är ett långt problem som jag har läst minst 3 gånger och fortfarande inte vet hur jag ska börja.
Jag har antagligen missat något, för jag förstår inte varför man spiller så mycket text på ett helt trivialt problem. Spelaren med det högsta kortet lägger bara det hela tiden.
Att programmera detta kan dock vara en bra övning.
Laguna skrev:Jag har antagligen missat något, för jag förstår inte varför man spiller så mycket text på ett helt trivialt problem. Spelaren med det högsta kortet lägger bara det hela tiden.
Problemet är inte helt trivialt. Spelarna vet endast vilka kort de själva har eller har haft. När spelet börjar vet ingen av spelarna om de har det högsta kortet eller inte.
Lindehaven skrev:Laguna skrev:Jag har antagligen missat något, för jag förstår inte varför man spiller så mycket text på ett helt trivialt problem. Spelaren med det högsta kortet lägger bara det hela tiden.
Problemet är inte helt trivialt. Spelarna vet endast vilka kort de själva har eller har haft. När spelet börjar vet ingen av spelarna om de har det högsta kortet eller inte.
" on each turn, each player chooses one of their cards (whichever they want)"
"Every card may be played any amount of times"
Så, man väljer sitt högsta kort, varje gång.
Men man skall nog tolka det som att man väljer ett kort i blindo (eller slumpmässigt).
Den som råkar ha det högsta kortet från början kommer ändå alltid vinna.
Roligare vore om man varannan gång ("turn") spelade högst-kort-vinner och varannan gång lägst-kort-vinner. Då kan vem som helst vinna. Det hade även varit en roligare programmeringsuppgift.
joculator skrev:
"Every card may be played any amount of times"
Ooops, det missade jag. Laguna och joculator har förstås rätt - det är ett trivialt problem.
Det ser ut som att uppgiften hämtats från Codeforces. Pseudo-kod för en lösning:
Läs in antalet testfall.
Repetera för samtliga testfall:
Läs in totala antalet kort, antalet kort för spelare 1 och antalet kort för spelare 2.
Läs in kortvärden för spelare 1 och håll reda på vilket kortvärde som är högst.
Läs in kortvärden för spelare 2 och håll reda på vilket kortvärde som är högst.
Jämför spelarnas högsta kortvärden och den spelare som fått högst kortvärde vinner.
baharsafari, hur gick det?
Lindehaven skrev:baharsafari, hur gick det?
inte så bra, har fortfarande inte fått ihop det.
Beskriv närmare vad du fastnat på (kanske i en ny tråd).
