Sunday, April 10, 2016

VK Cup Prep Series 3

C

 
C. Soldier and Cards
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Two bored soldiers are playing card war. Their card deck consists of exactly n cards, numbered from 1 to n, all values are different. They divide cards between them in some manner, it's possible that they have different number of cards. Then they play a "war"-like card game.
The rules are following. On each turn a fight happens. Each of them picks card from the top of his stack and puts on the table. The one whose card value is bigger wins this fight and takes both cards from the table to the bottom of his stack. More precisely, he first takes his opponent's card and puts to the bottom of his stack, and then he puts his card to the bottom of his stack. If after some turn one of the player's stack becomes empty, he loses and the other one wins.
You have to calculate how many fights will happen and who will win the game, or state that game won't end.
Input
First line contains a single integer n (2 ≤ n ≤ 10), the number of cards.
Second line contains integer k1 (1 ≤ k1 ≤ n - 1), the number of the first soldier's cards. Then follow k1 integers that are the values on the first soldier's cards, from top to bottom of his stack.
Third line contains integer k2 (k1 + k2 = n), the number of the second soldier's cards. Then follow k2 integers that are the values on the second soldier's cards, from top to bottom of his stack.
All card values are different.
Output
If somebody wins in this game, print 2 integers where the first one stands for the number of fights before end of game and the second one is 1 or 2 showing which player has won.
If the game won't end and will continue forever output  - 1.
Examples
Input
4
2 1 3
2 4 2
Output
6 2
Input
3
1 2
2 1 3
Output
-1
Note
First sample:
Second sample:
 
 
 
 
 
 
 
 
 Idea : Simulation + Max possible states calculation (Cycle detection)
 
 


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/****************************************

@_@
Cat Got Bored *_*
#_#
*****************************************/

#include <bits/stdc++.h>


#define loop(i,s,e) for(int i = s;i<=e;i++) //including end point

#define pb(a) push_back(a)

#define sqr(x) ((x)*(x))

#define CIN ios_base::sync_with_stdio(0); cin.tie(0);

#define ll long long

#define ull unsigned long long

#define SZ(a) int(a.size())

#define read() freopen("input.txt", "r", stdin)

#define write() freopen("output.txt", "w", stdout)


#define ms(a,b) memset(a, b, sizeof(a))

#define all(v) v.begin(), v.end()

#define PI acos(-1.0)

#define pf printf

#define sfi(a) scanf("%d",&a);

#define sfii(a,b) scanf("%d %d",&a,&b);

#define sfl(a) scanf("%lld",&a);

#define sfll(a,b) scanf("%lld %lld",&a,&b);

#define mp make_pair

#define paii pair<int, int>

#define padd pair<dd, dd>

#define pall pair<ll, ll>

#define fs first

#define sc second

#define CASE(t) printf("Case %d: ",++t) // t initialized 0

#define INF 1000000000   //10e9

#define EPS 1e-9


using namespace std;
queue<int>firstPlayer;
queue<int>secondPlayer;
ull allPossibleStatesCount()
{
    /*
    Firstly let's count a number of different states that we can have in the game.
     Cards can be arranged in any one of n! ways. In every of this combination,
      we must separate first soldier's cards from the second one's. We can
      separate it in n+1 places (because we can count the before and after
    deck case too).


    */



    ull states = 1;
    for(int i=1;i<=11;i++)
        states*=i;
    return states;
}
int main()
{
    //Just using simulation
    int mxStates = allPossibleStatesCount();

    int n,k1,k2;
    cin>>n>>k1;
    loop(i,1,k1)
    {
        int card;
        cin>>card;
        firstPlayer.push(card);
    }
    cin>>k2;
    loop(i,1,k2)
    {
        int card2;
        cin>>card2;
        secondPlayer.push(card2);
    }
    int simulationOn = 1;
    int statesCounter = 0;
    int winner = 0;
    while(simulationOn)
    {
        if(firstPlayer.empty())
        {
            winner = 2;
            break;
        }

        if(secondPlayer.empty())
        {
            winner = 1;
            break;
        }
        int fsCard = firstPlayer.front();
        int scCard = secondPlayer.front();
        firstPlayer.pop();
        secondPlayer.pop();
        if(fsCard>scCard)
        {
            firstPlayer.push(scCard);
            firstPlayer.push(fsCard);
        }
          if(fsCard<scCard)
        {
            secondPlayer.push(fsCard);
            secondPlayer.push(scCard);
        }

        statesCounter++;
        if(statesCounter>mxStates)
        {
            winner = -1;
            break;
        }


    }
    if(winner==-1)
        cout<<winner<<endl;
    else
    cout<<statesCounter<<" "<<winner<<endl;


    return 0;
}
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)