PROBLEM LINK: Contest Page | CodeChef
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY : INTERMEDIATE
Chris and Nick want to play the Word Challenge game.
Game Rules :
Both players are given the same string S. Both players have to make substrings using the letters of the string S .
Chris has to make words starting with consonants.
Nick has to make words starting with vowels.
The game ends when both players have made all possible substrings.
Scoring : A player gets +1 point for each occurrence of the substring in the string S .
Eg : String = BANANA
Nick’s vowel beginning word = ANA
Here, ANA occurs twice in BANANA. Hence, Nick will get 2 Points.
The solution is finding the player who scores more points by making words from a given string.Both the players need to follow rules ie, player1 starts with consonants and player2 starts with vowels and they are also rewarded with bonus points.
This challenge can be solved by finding all the substrings of the string and separating the substrings on the basis of their first character.
If the string is BANANA, the substrings are:
B , BA , BAN , BANA , BANAN , BANANA
A , AN , ANA , ANAN , ANANA
N , NA , NAN , NANA
A , AN , ANA
N , NA
INo. of substrings formed with BANANA are as follows:
Words formed using the first letter B = 6
Words formed using the second letter A = 5
Words formed using the third letter N = 4
Words formed using the fourth letter A = 3
Words formed using the fifth letter N = 2
Words formed using the last letter A = 1
Using this pattern, we can run a loop from the start to the end of the string and filter out words starting with vowels and consonants.
S = raw_input().strip()
S_length = len(S)
player1, player2 = 0,0
for i in xrange(S_length):
if S[i] in “AEIOU”:
player1 += S_length - i
player2 += S_length - i
if player1 > player2:
print “Nick”, player1
elif player1 < player2:
print “Chris”, player2