First off, between every two occurrences of consonants there must be at least two vowels for it to be Alice’s Recipe. Having said that…
This was a really annoying problem, I managed to solve it after quite a few tries. Following lessons were learnt (by me, and they were valuable):
Boost library is really nice.
Don’t forget middle school lessons on how to simplify vulgar fraction. Remove their GCD.
Don’t forget link between GCD and Prime Factors.
Remember that log function, although inaccurate, is really efficient.
The problem involved doing a lot of multiplications and divisions while maintaining accuracy.
Here is what I did:
Prime factorized all numbers concerned. Stored Prime factors as a map. For example 648 can be written as 2^4*3^3. Map format {2:4, 3:3}
Implemented multiplications, divisions and raising to power by manipulating these maps. Raising to power 10 means multiplying all keys by 10. Dividing is subtracting keys. Adding means adding key.
The final solution will be a map with a series of +ve and -ve keys. This will constitute numerator and denominator of final answer.
Generate a vector of long long numbers to store all elements of numerator and same for denominator.
Use log to check whether the fraction generated is greater than 10^8 or less than 10^-8. If so, just output Infinity or zero.
Else use boost library to print the actual answer.
WEIRDO - “From Zero to Infinity” - documented code; Editorial-style overview
I was also toying with the whole prime factorisation approach, but thankfully - and slightly surprisingly - using logs turned out to be accurate enough
Many people did wrong to check whether a string is of Alice or Bob , they just count vowels and conso and check if vowels are greater than equal to conso then it will be of Alice else Bob which is Wrong
I was getting AC for subtask 1(1.41s) and WA for subtask 2. I changed from maps and strings to arrays and got AC for subtask 1(0.2s) and WA for subtask 2. Finally on using cpp_dec_float_50 to find the final answer I got AC for subtask 2. Have a look here
