enum SeatStatus
{
    SOLD, UNSOLD, PENDING
}

class SelloutException extends Exception
{
}

class Seat
{
    public Seat( int n )
    {
        seatNum = n;
        status = SeatStatus.UNSOLD;
    }

    synchronized public boolean isAvailable( )
    {
        return status == SeatStatus.UNSOLD;
    }

    synchronized public void commit( )
    {
        status = SeatStatus.SOLD;
    }

    synchronized public void release( )
    {
        status = SeatStatus.UNSOLD;
    }

    synchronized public void reserve( )
    {
        status = SeatStatus.PENDING;
    }

    private int seatNum;
    private SeatStatus status;
}

public class TicketAllocator
{
    public static final int NUM_SEATS = 10;
    public static final int NUM_THREADS = 100;
    public static final double BUY_PROB = (double) NUM_SEATS / NUM_THREADS;

    private static java.util.Random r = new java.util.Random( );

    private Seat [ ] theSeats;
    private int numSold;

    public TicketAllocator( )
    {
        theSeats = new Seat[ NUM_SEATS ];
        for( int i = 0; i < theSeats.length; i++ )
            theSeats[ i ] = new Seat( i );

        numSold = 0;
    }

    synchronized public boolean isSellout( )
    {
        return numSold == NUM_SEATS;
    }

    synchronized public int ticketsSold( )
    {
        return numSold;
    }

    // Reserve a seat (return which one)
    private int reserve( ) throws SelloutException
    {
        while( !isSellout( ) )
        {
            for( int i = 0; i < theSeats.length; i++ )
            {
                synchronized( theSeats[ i ] )
                {
                    if( theSeats[ i ].isAvailable( ) )
                    {
                        theSeats[ i ].reserve( );
                        return i;
                    }
                }
            }

            synchronized( this )
            {
                try
                {
                    if( !isSellout( ) )
                        this.wait( );  // see if a seat shows up
                }
                catch( InterruptedException e )
                {
                    throw new SelloutException( );
                }
            }
        }

        throw new SelloutException( );
    }

    public int buy( double prob ) throws SelloutException
    {
        if( prob <= 0 || prob >= 1 )
            throw new IllegalArgumentException( );

        int s = reserve( );

        try
        {   // Slow us down a little
            Thread.sleep( 1 );
        }
        catch( InterruptedException e )
        {
        }

        if( r.nextDouble( ) <= prob )
        {
            // Want to buy
            theSeats[ s ].commit( );
            synchronized( this )
            {
                numSold++;
                if( isSellout( ) )
                    this.notifyAll( );
            }

            return s;
        }
        else
        {
            // Want to throw it back
            theSeats[ s ].release( );
            synchronized( this )
            {
                this.notifyAll( );
                return -1-s;
            }
        }
    }

    public static void main( String [ ] args )
    {
        final TicketAllocator ta = new TicketAllocator( );

        Thread [ ] tarray = new Thread[ NUM_THREADS ];

        for( int i = 0; i < NUM_THREADS; i++ )
        {
            final int id = i;
            tarray[ i ] = new Thread( new Runnable( )
                {
                    public void run( )
                    {
                        String cstr = "Customer " + id;
                        try
                        {
                            int s = ta.buy( BUY_PROB );

                            if( s >= 0 )
                                System.out.println( cstr + " buys seat " + s );
                            else
                                System.out.println( cstr + " passes on seat " +
                                                           ( -s - 1 ) );
                        }
                        catch( SelloutException e )
                        {
                            System.out.println( cstr + " sees a SELLOUT");
                        }
                    }

                }
            );

        }

        for( Thread t : tarray )
            t.start( );

        try
        {
            for( Thread t : tarray )
                t.join( );
        }
        catch( InterruptedException e )
        {
        }

        System.out.println( "SOLD " + ta.ticketsSold( ) + " tickets" );
    }
}