BIDGAME - Bidding Game
Alice and Bob are two of the richest businessmen in the city. Both of them have a passion for antique collection. So much so that they always compete with each other regarding who can collect more antiques.
There is a news about a fresh new collection of valuable antique items have arriving in the city. These items will be sold in an auction coming Friday. Both Alice and Bob are going there as well.
There will be N items sold in the auction one after the other. Each item has a starting bidding price S and a target price T. The first bidder needs to bid a higher price than the S. Next bidder will bid a higher price and it will go on like this until the price reaches at least T. In such case the last bidder wins that item. Then bidding of the next item starts.
There is however one more restriction regarding how much any of them can increase the bidding. If the latest bid is B, then the bidder has to increase the price by at least L%, but can not increase the bid by more than H%. For the first bid the increase in bid is counted against the starting price S. The bid amount must always be an integer.
As there is no other person as rich as Alice and Bob the bidding is only limited between them. Alice starts the bidding with the first item and then bidding continues by turn between Alice and Bob. The last bidder for an item (i.e. the winner of an item) would bid second for the next item.
If both Alice and Bob bid sensibly to win most items, you have figure out who will win most items among the N items. If both win the same number of items, then it is a draw between them.
Input
The first line contains an integer representing number of test cases to follow.
Each test case starts with line containing 3 integers, N, L, and H. Here L is the minimum increase in bid amount and H is the maximum increase in bid amount. Both L and H are represented as percentage.
Next N lines represent the starting bid and target bid of N items. Each of those lines contains two integers S and T where S is the starting price and T is the target price.
Output
For each test case print a single line with the name of the winner "Alice" or "Bob". If both of them wins the same number of items then print "Draw".
Constraints
Test <= 100
N <= 100
10 <= S <= 100
100 <= T <= 100000
S <= T
10 <= L < H <= 50
H - L >= 10
Example
Input: 3 1 10 50 100 150 2 10 50 100 120 100 130 3 10 20 100 120 100 130 100 150 Output: Alice Draw Alice
Problem Setter: Md Imrul Hasan. Used in Eid 2016 contest. More about Eid 2016 contest: Click Here
hide comments
Jacob Plachta:
2016-08-08 10:21:17
I got 0s with no constant optimization, so I guess the time limit is fine for a different algorithm :P |
|
[Rampage] Blue.Mary:
2016-07-23 11:46:06
Time limit is a little bit strict. |
Added by: | Raihat Zaman Neloy |
Date: | 2016-07-22 |
Time limit: | 1s-2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |