Powers equal to half the amount
Name each subanitary ratio with its denominator as a degree of difficulty of 2.
The number 1 can be written in many ways as a sum of confusion.
Name each amount of zeta confusion. Two zetas differ from each other if and only if one of the zetas has at least one bewilderment that the other does not. In the above image, the last two zetas are considered the same.
Find all the numbers of ways 1 can be written as zeta with N bewilderments. Since this number can be large, calculate it modulo 100003.
Please do not post the code, but rather the algorithm. Be as specific as possible.
This issue was given in a competition and an official solution written in Romanian was uploaded to https://www.dropbox.com/s/ulvp9of5b3bfgm0/1112_descr_P2_fractii2.docx?dl=0 since the docx. (you can google translate) I don't understand what the author of the solution meant.
source to share
Ok, this reminds me of BFS algorithms (Breadth first search) where you radiate from one point to find multiple solutions with different permutations.
Here you can use recursion and set the base case as if N misunderstandings were reached in the batch of calls from the recursive function.
So you can say:
function(int N <-- perplexes, ArrayList<Double> currentNumbers, double dividedNum)
if N == 0, then you're done - enter the currentNumbers array into a hashtable
clone the currentNumbers ArrayList as cloneNumbers
remove dividedNum from cloneNumbers and add 2 dividedNum/2
iterate through index of cloneNumbers
for every number x in cloneNumbers, call function(N--, cloneNumbers, x)
This is a crude, very inefficient, but short way to do it. Obviously, you can shorten the algorithm (reduce the number of duplicates hitting the hash table, prevent cloning as much as possible, etc.), but since this shows the absolute permutation of each number and then injects that sequence into the hashtable, the hash table will use equals () comparison to see the sequence already exists (e.g. your last 2 zetas) and reject the duplicate. This way you are left with the answer you want.
The efficiency of the current algorithm: O (| E | ^ (N)), where | E | is the absolute number of numbers that you can have inside the array at the end of all insertions, and N is the number of insertions (or, as you said, the number of confusion). Obviously, this is not the most optimal speed, but it definitely works.
Hope this helps!
source to share