![]() If solutions does not contain abs( x/2-time )Īppend abs( x/2-time ) to solutions_to_add ![]() If solutions does not contain abs( x-time ) #then continuously add additional ropes until we have n ropes #of the first recorded time measurable with 1 rope. Let start_idx be an index in the solutions array #we will store the index of the first time that was recorded with n-1 ropes #we can be efficient by only checking the times achievable with n-1 ropes So, in pseudocode, perhaps something like this let solutions be a list of measurable times We do not care about a time t that was achieved with m with m<=n-1 ropes because we would have considered these four cases when we were adding the m+1-th rope. This means we can achieve abs( x/2 - x_prev) minutes. Start burning the x_prev minutes as we burn the next rope from 2 ends.This means we can achieve abs( x - x_prev ) minutes. Start burning the x_prev minutes as we burn the next rope from 1 end.This means we can achieve x_prev + x/2 minutes. Wait for the whole x_prev minutes to expire, then burn the next rope from 2 ends.This means we can achieve x_prev + x minutes. Wait for the whole x_prev minutes to expire, then burn the next rope from 1 end.Then, consider what happens if we add the n+1th rope. Now, suppose it is possible to measure x_prev minutes with n ropes. We can start with a base state of 1 rope yields x minutes or x/2 minutes. ![]() I might have overlooked something, so be wary even if it seems to make sense. Well, here is my attempt to solve the problem with greater efficiency. until n = 0 (All ropes finished burning)įor n = 2 and x = 60, I've found that the following time period can be measured: 30, 60, 90, 120, 45 and 15.Īs suggested, I posted the question on cs.: Repeat the step 1 argument with x + y + z = n - 1 (with constraints imposed on x, y, and z since some ropes are still burning and we cannot set the fire off) and add all the newly generated cases to the stack/queue. Now we have another scenarios with certain amount of ropes that are being burnt. Output the time that has passed (calculated based on how long the finished rope has burnt, and which ends were burnt at what time).
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |