DCP-91: String lovers Back to All Problems

Hard Game Theory > Nim

Alice and Bob are fond of string. They invent a new game with string. Initially they have N strings of different length. They play alternate move and Alice make the 1st move. In each move player chose a string and replace it with another string which length is same as selected string and which is lexicographically smaller then selected string.The game ends, when someone is unable to make any move, and loses the game. Assume both player play optimally. You are given n string. You have to find the winner. Input: ------ Input starts with an integer **T (1<=T<=10)**, denoting the number of test cases. Each case contains an integer **N (1 ≤ N ≤ 100000)** denoting the number of string. Next N line contains N string **Si (1<=i<=N). 1<=|Si| <= 10**. String contain only lower case English letters. Output: ------- For each case, print the case number and 'Alice' or 'Bob' depending on the winner of the game. Sample Input ------------ 2 1 b 2 ab ab Sample Output ------------- Case 1: Alice Case 2: Bob

Problem Setter:

MD Musfiqur Rahman Sanim

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats




# User Language Timing
01 feodorv C 0.12s
02 inam Cpp14 0.12s
03 Morass Cpp14 0.13s
04 robin_aust Cpp14 0.13s
05 tariqiitju Cpp14 0.13s
06 seyedssz Cpp14 0.14s
07 Robbinb1993 Cpp 0.20s
08 moinul_shaon Cpp14 0.91s
09 ksohan Cpp14 1.38s

Your feedback is our precious!

Or call +88 02 9853138 for support