Answers to: Iarcs problem archive- Find the Numbershttps://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers<p>link: <a href="http://opc.iarcs.org.in/index.php/problems/FINDNUMS">http://opc.iarcs.org.in/index.php/problems/FINDNUMS</a></p>
<p>My approach was to factorize 'P' and as it is small to brute force over all combinations of divisors.
For example for S=11, P=48 and k=3 (Shown example) I would check (1,1,48),(1,2,24),(1,3,16) and so on till i reached (3,4,4) which was the answer. Could someone suggest some method to enumerate all the sets of the divisors of the number?</p>
<p>Any other solution too would be of great help.</p>enFri, 09 Jan 2015 23:27:48 +0530Comment by superty on sandy999's answerhttps://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers#61142<p>Yeah I was initially printing i, j, k in that order but I changed it around to check if the order mattered. (it shouldn't if the testdata is correct)</p>supertyFri, 09 Jan 2015 23:27:48 +0530https://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers#61142Comment by sandy999 on sandy999's answerhttps://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers#61137<p>The order matters. In your code, if you intentionally print i before j and k, it won't give correct answer.</p>sandy999Fri, 09 Jan 2015 23:05:57 +0530https://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers#61137Comment by superty on sandy999's answerhttps://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers#61135<p>I don't think they actually follow this rule when printing output, it's just coincidence probably.</p>supertyFri, 09 Jan 2015 22:50:07 +0530https://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers#61135Comment by sandy999 on sandy999's answerhttps://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers#61132<p>Yeah I got 70 points initially, then looked at the test data :P</p>sandy999Fri, 09 Jan 2015 22:36:49 +0530https://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers#61132Comment by superty on sandy999's answerhttps://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers#61125<p>Have you deduced by looking at the testdata? :P</p>supertyFri, 09 Jan 2015 21:58:26 +0530https://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers#61125Answer by sandy999https://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers/61124<p>You could also do it recursively.</p>
<p>The base case being, if K = 1, then if S = P, the answer is yes, otherwise no.</p>
<p>Basically you are reducing the actual problem to the following sub problem. </p>
<p>You're given S, P, K.</p>
<pre><code>if K=1
if S=P
return true i.e. answer is yes
else
return false i.e. answer is no
For i = 1 to N
If P is divisible by i,
Include i in list of numbers
then solve for S-i, P/i and K-1 recursively
</code></pre>
<p>About the test data, there's extra information missing in the problem statement. Nothing about the ordering of the numbers N1, N2, ..., NK has been explicitly mentioned in the problem statement. That is:</p>
<p>If one of N1, N2, ..., NK is 1, print in descending order. Otherwise, print the numbers in ascending order.</p>sandy999Fri, 09 Jan 2015 21:30:57 +0530https://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers/61124Answer by supertyhttps://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers/61115<p>Simple brute force works: <a href="http://pastebin.com/M4CPvVZ6">http://pastebin.com/M4CPvVZ6</a></p>
<p>Note: don't worry if you get wrong answer when submitting on the server, the test data is wrong. </p>supertyFri, 09 Jan 2015 17:42:07 +0530https://inoi15.discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers/61115