Có n đống đá, n chẵn. Mỗi lượt phải chọn đúng n/2 đống còn khác rỗng và giảm mỗi đống được chọn đi một lượng dương tùy ý. Khi còn ít hơn n/2 đống khác rỗng, người tới lượt không đi được và thua. Alice đi trước.
Input
Dòng đầu chứa số nguyên n; dòng sau chứa kích thước n đống đá.
Output
In Alice hoặc Bob.
Constraints
2≤n≤5000 và n là số chẵn.
1≤ai≤109.
Scoring
Subtask 1 (50% số điểm): các test 1-10 có kích thước nhỏ, thuận tiện kiểm chứng độc lập.
Subtask 2 (50% số điểm): không có giới hạn bổ sung ngoài các cận đã nêu.
Example
Test 1
Input
2
1 1
Output
Bob
Giải thích: Có hai đống, mỗi đống chứa một viên, và mỗi lượt phải chọn đúng một đống. Alice làm rỗng một đống, Bob làm rỗng đống còn lại; Alice không còn nước đi nên in Bob.
Lời giải tóm tắt
Ý tưởng và thuật toán: Gọi m=min(a_i) và c là số đống có kích thước bằng m.
Ý tưởng và thuật toán: Nếu c > n/2, đây là trạng thái thua: in Bob nếu là trạng thái đầu.
Ý tưởng và thuật toán: Nếu c <= n/2, đây là trạng thái thắng: in Alice.
Ý tưởng và thuật toán: Để thấy nước thắng khi c<=n/2, có ít nhất n/2 đống lớn hơn m. Chọn đúng n/2 đống đó và giảm từng đống xuống m; số đống đạt minimum mới trở thành c+n/2 > n/2.
Chứng minh đúng đắn: Gọi trạng thái có hơn n/2 đống cùng đạt minimum là lớp P.
Chứng minh đúng đắn:Từ ngoài P đi được vào P. Nếu c<=n/2, số đống lớn hơn minimum là n-c>=n/2. Chọn n/2 đống trong số đó và hạ tất cả về m. Minimum không đổi và xuất hiện ít nhất c+n/2>n/2 lần.
Chứng minh đúng đắn:Từ P không thể đi vào P. Một nước chọn đúng n/2 đống. Vì có hơn n/2 đống minimum, ít nhất một đống minimum bị chọn và bị hạ xuống dưới m. Mọi đống đạt minimum mới nhỏ hơn m đều nằm trong tập vừa chọn, mà tập này chỉ có n/2 phần tử. Vì vậy minimum mới xuất hiện không quá n/2 lần, tức trạng thái kế tiếp ở ngoài P.
Chứng minh đúng đắn: Hai tính chất cho thấy các nước luân phiên giữa P và ngoài P; trạng thái không đi được cũng thuộc P khi coi các đống rỗng có giá trị 0. Do đó P là đúng lớp thua.
Độ phức tạp:O(n) thời gian, O(1) bộ nhớ ngoài mảng đầu vào.