DCP-364: Sanvi and String Flow Back to All Problems

Hard Game Theory > Sprague-Grundy Number


**Sanvi** has got a string-say **S**. The string consists of lowercase english alphabets. She knows that every lowercase alphabet has a power that they changes from their value to another lowercase alpahbet with lower ascii value ( ***see the input section for details*** ). Every lowercase letter has this power. **Sanvi** is challenging her little sister- **Manvi** to play a game with this string- S. <br> In each move, they select a particular index then changes the character of that index to another one depending upon power of that character but tries to skip the character which may lead to incompletion of game. One who got the string consisting of all characters with alphabet -**'a'** will loss the game. **Sanvi** starts playing game first. Your task is to determine the winner of this game If both of them play optimally well. If there arise a situation that nobody can win the game ,then the game will be "**Tie**". Input: ------ Input starts with an integer **T (1<=T<=1000)**, denoting the number of test cases.<br> Each case contains a string - **S** with lowercase english alphabets having length **N (1 ≤ N ≤ 200)**.<br> The next 26 lines will represent a matrix with 26 column. 1st row for representing power of 'a', second row representing power of 'b' and so on.<br> Here, if jth value of ith column is 1 , then it represent that ***ith character has power to be changed into jth character.*** Output: ------- For each case of input, output the name of player who wins the game in the format **"Case X: Name"**<br> Here, **X** represent the testcase number and **"Name"** represent the winner's name ( **"Sanvi" or "Manvi"** ) or Status of the game **"Tie"**. Sample Input ------------ 1 devskilltrainingsessionisgoingtostartsoonstaytune 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 0 Sample Output ------------- Case 1: Sanvi


Problem Setter:

Bishal Gautam

Please login to submit solution to this problem.

Problem Limits

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

Problem Stats

31/113

Solve/Submission

Ranking

# User Language Timing
01 Robbinb1993 Cpp14 0.01s
02 Morass Cpp14 0.03s
03 sahedsohel Cpp 0.06s
04 Hawk Cpp 0.07s
05 Double_O Cpp 0.08s
06 rubabredwan Cpp14 0.08s
07 ovis96 Cpp14 0.09s
08 ____ Cpp 0.09s
09 njrafi Cpp 0.10s
10 phoenix71 Cpp 0.10s
11 Bruteforceman Cpp 0.10s
12 flash_7 Cpp14 0.11s
13 Mahmudul_Tushar Cpp 0.12s
14 CLown1331 Cpp14 0.12s
15 mamun4122 Cpp 0.15s
16 tariqiitju Cpp14 0.15s
17 adamantium Cpp 0.16s
18 BishalG Cpp 0.28s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support