rachmaninoff's blog

Suggestions about solving this problem
By rachmaninoff, history, 9 years ago, In English

Hi! Could you please give me some hints on solving this problem?

Simplified statement:

You need to launch a rocket into space by detonating explosives attached to it. You can only detonate one explosive at a time and each one will carry the rocket for a distance given in the input. However, before reaching the maximum height and after launching the rocket, you may encounter some endangered bird species at different heights. You need to avoid hurting those birds by not detonating an explosive at the height they live.

Input: N — number of explosives N Integers representing how far can an explosive carry the rocket N — 1 integers representing the heights at which the birds reside

Find a configuration of detonating the explosives (that is output the order in which to detonate them — index starting from zero) such that no birds get killed.

Example : 3 2 4 6 4 8

answer: either 0 1 2 or 2 1 0

  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the constraints? and can you add a link to the problem if it's available an online judge?

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

    There is no online judge - N <= 100 — that's the only constraint I do not need a solution — just an idea to get me going Brute force is not an option here

    → Reply