nick_johnson's blog

TIMUS oj 1049. Brave Balloonists...
By nick_johnson, history, 7 years ago, In English

On Timus getting wa on test 2 ..somebody plz tell me what is wrong?

the problem 1049 brave ballon

my code: ideone

Idea : what i tried to do was ..calculate all prime factors of those 10 num;

Then maintained dp where dp[x]..would be n^(x or higher)...the number of factor which has x or higher power.. then i calculate the number of situation where all numbers are prime, i gradually lessened the length and calculate new numbers where the situation was of that length;

if it was : 36 length 4: 2, 3 case [2*2*3*3] length 3 : 4,9,6 cases[ 4 * 3* 3, 2*2*9, 6*6] length 2 : 12, 18 cases [12*3, 18*2]

length 1 : 1, 36

in my code length was denoted as x

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In Line — 37 You are modifying n {n = n/i}, and using sqrt(n) in the for loop condition(line 35)

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hmm, I am not certain I understand your DP idea. Could you explain more precisely what your dp[x] is meant for and how(and why) do you use it to calculate the final answer.

Alternatively, this problem has a rather simple number theory solution, which I would be happy to explain to you (either here or message you directly).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    thanks for the reply man... sorry for the delay.. i figured it out.....i figured the number theory solution too..... i think it is (power of prime factor1+1)*(power of factor2+1)*......... what i tried to do was: what if I multiply x numbers from total factors how many new factor would i get. it was foolish idea i tried to from a new number one at a time instead of thinking the combination approach.

    → Reply