improving this algorithm O(n)

0

I have a cake with n layers total. I know that k are vanilla. and => n-k is not. I dislike all flavors other than vanilla, so i decide to only eat those layers. I can't tell which layer is which flavor. BUT, i can smell the vanilla. For any m with 1<=m<=n, i can test the top m layers of the cake byt removing them from the cake and taking them to another room. there, i can smell whether any of those layers are vanilla, - just wether or not there is at least 1 vanilla layer among the m layers. Then i can replace those m layers in their proper poisition on top of the cake. once ive performed enough tests to determine if a layer is vanilla, i eat it right out from the middle of the cake, leaving the n-1 layers intact. i need to be certain what i eat is vanilla. then i can return to doing more tests to find the next vanilla layer/. How can i write an algorithm in that takes in n and k, and outputs the number of tests required to identify (and therefore eat) all of the vanilla layers?

IMO, the only way we can do this is by checking every single layer individually... I don't see how taking multiple layers at a time would ever work. Let vanilla = 1 and other flavors = 0 Lets say we have a cake 011: and we take 3 at a time, and find there is vanilla then we anyways need to check every layer. Lets say we have 0000001 and we take 3 layers, then yes, we can move on to the next 3. but why don't we take 4 or 5? Or 7? if we take 7 though, we'd be back at the first issue.

I think we have to do this indiivudally (it would take n tests) because trying to shorten it simply does not give us enough information.... any. clarification would be helpful as this does seem too simple to me!

https://stackoverflow.com/questions/67362420/improving-this-algorithm-on May 03, 2021 at 09:02AM