You will write a solver for in non-negative integers, built on the extended Euclidean algorithm, and a tool for the coin problem.
The idea. The function extended_gcd(a, b) is given. It returns with . If there is no solution. Otherwise is one solution, and the others step by and .
Your tasks.
one_solution(a, b, c). Return a pair with , or None when .non_negative(a, b, c). Return the sorted list of all pairs with . A loop over from to is enough.largest_unpayable(a, b). Return the largest from to with non_negative(a, b, n) == [].Run your code once to unlock the worked solution.
Have you tried it?
Do the tasks in the editor first, and run the checker after each one. Its hints help when a check fails. When you are ready, compare your code with this solution.
Log in to join the discussion.
Loading…