Rare programmeer opdracht

Explosive Recursion

Introduction

The government has decided that it's about time we sent something into space again. However due to the recent economic recession there's a rather tight budget for this. Luckily the government still has an old shed full with explosives lying around which they can use to get to space. There are some problems though with the launch site. Some of the heights are habited by rare protected bird species. The rocket is allowed to fly through these but is not allowed to detonate explosions at these specific locations.

The bird protection people have numbers on on what heights the birds reside, and the space agency has numbers on how far each explosive will take the rocket in kilometres. There are no two explosives that make the rocket travel the same distance. The space agency doesn't have a budget to hire someone to do the calculating, so you volunteered to help them get their rocket's to space because you're a nice guy.

The rocket uses explosives tied to the bottom to propel them upward. This means that you can't stop them once you lighted them, and they will always travel a set distance. (The space agency has made budget cuts, and decided a lot of money could be saved if they ignored gravity and friction). This set distance is a integer given to you, and will always be a round natural number. No multiple explosives can be fired since that would damage the rocket and bring the astronaut in danger. The bird federation also gives you these numbers as round numbers. There's always one less bird spot then there are explosives.

It is your task to figure out in what order to ignite the explosives in such a way that you do not blow up any rare birds.

Exercise

The input is a positive integer N, followed by N positive integers. Each of these are the number of meters the i-th explosive will take you. Then there are N-1 positive integers which are the heights at which rare birds reside and no explosive should be ignited. Both of these are in kilometres.

The output are N integers, the zero-based indices of the explosives to ignite (The first explosive on the list is indexed 0). The order of the output is the order in which to ignite them. This order is such that no explosive will be ignited on a bird spot and all explosives are ignited.

The rocket starts at height 0, and the target destination is at the location you get to after igniting all the explosives. There are no rare birds at either the starting position 0 or the maximum position. They are all between these two positions.

It is in fact always possible to get the rocket to maximum height, no matter the locations of the birds or the distance each explosive propels you. Not just in the test cases I give you but for all input you can generate given the restrictions. Your program should essentially be a proof of this fact. This is a really important given property if you want to solve the program effectively. On igniting a explosive, the rocket always fly exactly the number of kilometres given in the input for that explosive. You cannot decide to fly a shorter distance than that. Also note that the number of kilometres a explosive can take you is different for every explosive.

Hint: use recursion. You could change your recursion to a non-recursive program later (to prevent a stack overflow for really large inputs). In your recursion, remember that it's also possible to recurse and change the result of that recursive call after the recursion.

Constraints

You have to do better than simply trying all possible orders of igniting the explosives (brute-forcing). This would take way too long. You have to at least be able to calculate an ordering for 100 explosives, for any input of that size. You should try to make a program that directly constructs a good ordering. Any approach involving trying lots of ways hoping to stumble on a good ordering will be too slow. A good place to start is to try to prove that there is always a good ordering, and then converting that proof into a program. Figuring the problem out by paper before programming it will help you.

If your program is too slow for any input with 100 explosives your solution is no good. Too slow means that it takes you more then a few seconds to solve for 100 explosives. You'll notice.

Examples

Some example inputs. If the second case takes long you're on the wrong track with your algorithm. Do note that for some inputs there can be multiple solutions but Peach only checks for one, so don't panic if Peach says you got it wrong but have a look at the in and output. And as always, do your own tests to make sure it works, Peach is just there to help you test.

input (split to three lines for clarity)

3
2 4 6
4 8

output

0 1 2

a different output

2 1 0

input (split to three lines for clarity)

20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191

output

19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0