Can someone please explain the solution to this problem?
Heres the Question : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=676
I have read various blogs and solutions but could not figure out what they are trying to do.
Thanks in advance.
At first you have to find out which scores you can score by throwing the dart. There is 0, 50 and x,2x and 3x where x = 1,2,3…,20. You can store these numbers in a array, vector or set.
Hint: set can be useful here.
Now, we have to find out the combinations and permutations. In permutations, the order doesn’t matter. So you just need to achieve the total target in 3 moves in any way possible. As the number of throws is only 3, you can easily use 3 for loops to iterate through the scores container(array, vector or set, whatever you are using). Just check if arr[i] + arr[j] + arr[k] = score, permutation++
Remember, if the number of throws were higher, you would’ve needed dynamic programming.
If you can achieve the score, you will get an answer. But if the count is 0, you can print this line, “THE SCORE OF N CANNOT BE MADE WITH THREE DARTS.”
Now, let’s come to finding combinations. Here order matters. So, you can keep a map like m[throw1][throw2][throw3], and check for every permutation, if the map stores it or not. Thus, we can find out the combinations.
Hope, this will help.