Voor school moet ik een programmaatje schrijven dat met input voor een soort probleem daar een oplossing voor bedenkt. 't Probleem is alleen dat ze bedacht hebben dat het niet met bruteforce mag en nu snap ik er de ballen van. Een tipje die ze geven is dat als je kan bewijzen dat er altijd een oplossing is dat je dit bewijs dan om kan zetten naar een programma. Ik heb echter geen flauw idee hoe en het moet toch echt morgen ingeleverd dus ik hoop dat er bij iemand hier misschien wel een lampje gaat branden en mij even de goede richting in kan helpen.
Dit is ook echt niet als zo'n 'hè jongens maak mijn huiswerk'-vraag bedoelt maar meer als een 'ik heb geen idee wat ik moet doen kan iemand me op weg helpen'-vraag.
Het probleem
Ik heb nu zelf 3 gevallen bedacht waarin je zeker weet dat een bom goed is maar die gevallen zijn helaas niet volledig dekkend.
Het probleem is dus vooral dat ik niet weet wat ik moet doen als je nog niet alle vogels voorbij bent maar geen bom hebt die er overheen kan. Sowieso weet ik ook niet of op deze manier naar het probleem kijken wel de juiste manier is.
Dit is ook echt niet als zo'n 'hè jongens maak mijn huiswerk'-vraag bedoelt maar meer als een 'ik heb geen idee wat ik moet doen kan iemand me op weg helpen'-vraag.
Het probleem
Spoiler:
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
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
Ik heb nu zelf 3 gevallen bedacht waarin je zeker weet dat een bom goed is maar die gevallen zijn helaas niet volledig dekkend.
- De laatste bom is altijd goed.
- Als je voorbij alle vogels bent zijn alle bommen goed.
- Als een bom over een vogel heen gaat en weer op een leeg plekje terecht komt is dit ook altijd goed omdat je dan in principe opnieuw in een vergelijkbare situatie komt maar dan met een n die 1 lager is.
Het probleem is dus vooral dat ik niet weet wat ik moet doen als je nog niet alle vogels voorbij bent maar geen bom hebt die er overheen kan. Sowieso weet ik ook niet of op deze manier naar het probleem kijken wel de juiste manier is.