Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

For example, like:


The inaugural International Olympiad in Frogleaping is being held in Australia in 2013 and you are determined to win. While you want nothing to do with such slimy, jumpy creatures, you plan to enter a frog-like robot that you know will be faster than all the other organic entrants.

The IOF takes place in a large pond in which there is a sequence of lily pads arranged in a long line. The rules of the race are simple: your frog will be placed on the first lily pad, then it must jump to the second lily pad, then the third and so forth until it reaches the last lily pad in the course. Note that you can not `skip' lily pads--every lily pad must be jumped on exactly once. The first frog to reach the last lily pad will win the race. Since your robotic frog has super-frog speed, you are confident in your victory.

However, your frog has one minor incorrectable flaw--it is only able to jump one fixed distance. Specifically, it can only jump exactly K metres forward from its current location, even if this lands the frog in the water (where it will promptly short-circuit).

Since the initial lily pad positions may make it impossible for your frog to reach the last lily pad, you plan to create a distraction and move the lily pads so that they are spaced exactly K metres apart, enabling your frog to jump from the first to the last without falling in the water. Shifting a lily pad by one metre will take you one second, and the longer you spend stealthily moving lily pads, the more likely that the IOF judges will notice and disqualify you from the competition.

Given the initial distances between the lily pads in the course, you must write a program to compute the minimum time you will have to spend shifting lily pads such that all pairs of consecutive lily pads are exactly K metres apart. You can assume that the pond is sufficiently long so that the first lily pad can be moved any distance back, and the last lily pad can be moved any distance forward.

Input

Your program should read from the file frogin.txt. The first line of this file will consist of two space-separated integers N and K. The following N-1 lines will contain the initial distances between consecutive pairs of lily pads. Specifically, the ith line will contain one integer representing the distance between the ith and (i+1)th lily pad.

Output

Your program should write to the file frogout.txt. Your output file should consist of one line containing one integer: the minimum total time spent shifting lily pads so as to ensure your victory.


This is a sample problem from the Australian Informatics Olympiad, which I happened to come across searching on the internet.

But I do not believe that any programming-related problems which do not directly connect with real-life situations will have any helpful effects upon one's real-world programming ability. Will they?

share|improve this question
    
@Simon Is this better? –  think123 Jan 27 at 23:06
    
yep nice edit :-) –  Simon Jan 28 at 8:03

3 Answers 3

up vote 9 down vote accepted

Think about this:

  • first of all, to solve the given problem, there is a non-trivial program to be written. It does not need to have a fancy Web or desktop UI or a "database layer" or , but it involves some kind of "business logic" which has to be tested and debugged.
  • for solving the problem, you need some integer math / combinatorics. There are lots of real-world problems for which knowing integer math / combinatorics is helpful (of course, there is also a huge number of problems where you don't need this).

So IMHO yes, solving such problems teaches you certain aspects of beeing a better programmer. Of course, they don't teach you everything about real-world programming, especially nothing which involves a special technology. But the "Australian Informatics Olympiad" (or the Informatics Olympiad in other countries) is about informatics, not about real-world programming, so it has a different goal.

share|improve this answer

Usually when people rant against a problem's relevance, that means they find it too hard. It's by solving difficult problems that you grow. The best you get from repeatedly solving easy problems is you get faster at solving easy problems.

Those sorts of problems are meant to be fun, but that doesn't mean they aren't relevant to a programmer's daily work. Some examples of problems that are similar in terms of algorithms and thought process, but more "serious" are:

  • Creating an animation to evenly space out elements placed roughly on a display.
  • Calculating the latency to handle events that arrive at irregular times, but that you wish to handle evenly-spaced.
  • Compensating for jitter in streaming audio or video.
share|improve this answer

Yes, they are. I agree with Doc Brown, and I want to add that some problems (eg. ACM's ICPC) apart from math skills are also exercising your ability to model a problem, write an algorithm, etc.

Although most official submitted solutions are probably full of dirty hacks because of the time limits, you can take your time and solve the problems in an optimal and elegant way.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.