You are not logged in. Please login at www.codechef.com to post your questions!

×

Iarcs problem archive- Find the Numbers

link: http://opc.iarcs.org.in/index.php/problems/FINDNUMS

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?

Any other solution too would be of great help.

asked 08 Jan '15, 21:02

ajs97's gravatar image

3★ajs97
1123
accept rate: 0%


You could also do it recursively.

The base case being, if K = 1, then if S = P, the answer is yes, otherwise no.

Basically you are reducing the actual problem to the following sub problem.

You're given S, P, K.

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

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:

If one of N1, N2, ..., NK is 1, print in descending order. Otherwise, print the numbers in ascending order.

link

answered 09 Jan '15, 21:30

sandy999's gravatar image

2★sandy999
39111538
accept rate: 10%

Have you deduced by looking at the testdata? :P

(09 Jan '15, 21:58) superty3★

Yeah I got 70 points initially, then looked at the test data :P

(09 Jan '15, 22:36) sandy9992★

I don't think they actually follow this rule when printing output, it's just coincidence probably.

(09 Jan '15, 22:50) superty3★

The order matters. In your code, if you intentionally print i before j and k, it won't give correct answer.

(09 Jan '15, 23:05) sandy9992★
2

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)

(09 Jan '15, 23:27) superty3★

Simple brute force works: http://pastebin.com/M4CPvVZ6

Note: don't worry if you get wrong answer when submitting on the server, the test data is wrong.

link

answered 09 Jan '15, 17:42

superty's gravatar image

3★superty
36417
accept rate: 31%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×109
×61

question asked: 08 Jan '15, 21:02

question was seen: 8,379 times

last updated: 09 Jan '15, 23:27