All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

( Problem B ) Prime Game
Tag(s):

Algorithms, Dynamic Programming, Easy, Two dimensional

Problem
Editorial
Analytics

Alice and Bob have an integer \(x\) consisting only of digits 2,3,5,7. They are playing a game with this number. 

The rules of the game are as follows:

  • Alice starts the game and then both of them take alternating turns.
  • In each turn, the player removes one digit either from the front or back of the integer \(x\) in the decimal notation. For example, if the player has the integer \(53722\), then he or she might remove \(5\) from the front to obtain \(3722\) or \(2\) from the back to obtain \(5372\).
  • The player who reduces the given integer to a prime number loses the game.

Note that when the number is reduced to one digit, it will always become a prime number, as it will be equal to one of 2,3,5 or 7.

Determine who wins the game if both play optimally.

Input:

  • First line: \(t \) (number of test cases)
  • Next \(t\) lines: Contains the description of \(t \) test cases. Each test case is described in a single line with an integer \(x\).

Note:

  • It is guaranteed that the integer \(x\) consists of only digits \(2, 3, 5,\) and \(7\).
  • The integer \(x\) is not a prime number.

Output:

For each test case:

  • If Alice wins, then print 'Alice' (without quotes) in a single line.
  • If Bob wins, then print 'Bob' (without quotes) in a single line.

Scoring:

In all test sets, \(1 \leq t \leq 10\).

In the first test set worth 35 points,  \(1 \leq x \leq 10^6\).

In the second test set worth 50 points, \(1 \leq x \leq 10^{12}\).

In the third test set worth 15 points, \(1 \leq x \leq 10^{18}\).

SAMPLE INPUT
2
3237
3273
SAMPLE OUTPUT
Alice
Bob
Explanation

In the first test, Alice starts with integer 3237 and can turn it into either 323 or 237, neither of which is a prime number.

Let's investigate first what happens if she choses to continue with number 323. Bob can then choose between either 32 or 23. As 23 is a prime which would make Bob lose instantly, he would choose 32. Then, however, Alice loses, as both 3 and 2 are primes, and she has no other turn.

What if Alice picks the other option at the start of the game, and removes the '3' from the beginning? Then Bob is left with number 237 and his situation is much worse. Whatever he chooses, he will end up with a prime right away - as both 23 and 37 are prime numbers. 

Hence, Alice can win by removing the '3' from the beginning.

Time Limit: 5,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HourStorm #3

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?