A. One-dimensional Japanese Crossword
You really like ladybugs. This is fortunate, as dozens of ladybugs have recently taken up residence in your garden. Every day they emerge into the sunlight and climb your garden fence. The fence is a series of regularly spaced posts which gleam brightly in the sun. The ladybugs settle into their favourite resting spots atop these posts.
Winter is nigh and you wish to protect the ladybugs from the rain. You set out to construct a rain shelter using a single length of ribbon propped up with toothpicks. To protect all the ladybugs, the ribbon must be long enough to cover all their favourite resting spots. Ribbon is not cheap, so you wish to use the shortest length of ribbon you possibly can. A ribbon of length k will cover precisely k adjacent fence posts.
For example, on the fence in the diagram above there are two ladybugs sitting on fence post 3 and one ladybug on each of 2, 6, 7 and 9. The ribbon rain shelter must cover all the posts from 2 through to 9 inclusive, so the shortest possible length of ribbon that covers all the ladybugs is 8.
Your task is to write a program to calculate the minimum length of ribbon that will cover all the ladybugs.
As luck would have it, it has rained on the morning of the concert. To make matters worse, the staff did a very rushed job drying the seats! Now it is up to you to decide how to seat everyone.
The seats are arranged in a single long line in front of the stage. In particular there are chairs in the line, and each seat is either wet or dry.
However, all is not lost. Out of the N friends you are bringing to the concert K of them are happy to sit on a wet chair. The other N-K of your friends insist on sitting on a dry chair.
Since this concert is best enjoyed with friends, you would also like your group to be seated as close together as possible so that the distance between the leftmost person and rightmost person is as small as possible. Output the smallest distance possible between the leftmost and rightmost friend at the concert.
Your task is to write a program that outputs this smallest possible distance.