#!/usr/bin/perl -I ../../../cgi-bin
use CGI::Carp qw(fatalsToBrowser);
use AIOC::HTML;
use AIOC::SiteBase;
use POSIX qw(strftime);
$specDir = AIOC::SiteBase::specDir();
my $site = new AIOC::SiteBase("aioc", "$specDir/aioc.train", '', $site_news);
$site->putHeader();
$site->putPageHeader("Tutorials");
print << "__END__";
Drought
Let's solve Drought.
In this problem, we are asked to use rain forecasts to predict when a water tank will be filled. This walkthrough will briefly outline a way of keeping track of the tank's water levels, before discussing how break and continue statements give us greater control over loops.
Simulating the water tank (I)
The problem statement makes things pretty clear. Each day's forecast gives us the exact amount of water that falls into the tank. We should give the day the tank fills (and we're promised it will always fill) as our answer.
Much like the previous problem, in which we had to calculate the mean of several numbers, here we need a variable to keep a running total of the water in the tank. For example:
total_rainfall = 0;
for (int day = 1; day <= N; day++) {
<read an integer into current_rainfall>
total_rainfall += current_rainfall;
}
We've had a bit of experience reading and writing loops now, so it should be clear how the above code works. After each addition, total_rainfall will have taken the correct value for the corresponding day.
From here it is a simple matter to check if the tank is full:
total_rainfall = 0;
for (int day = 1; day <= N; day++) {
<read an integer into current_rainfall>
total_rainfall += current_rainfall;
if (total_rainfall >= tank_capacity) {
//the tank is full
}
}
However, this is not exactly what the problem is asking for. We need to find out how many days it takes until the tank fills. (Equivalently, we need to find out on which day the tank is first full.) Using the if statement above, there are several ways of going about this. In my opinion, the best way is using a break statement.
About break and continue statements
(Note: in this section I specifically discuss break and continue statements as they are used in C/C++. However, the descriptions I give here apply to most of the programming languages allowed in the AIO. If you're unsure about your language, consult a textbook or teacher.)
Sometimes when we use loops, the code inside the loop starts to get a little long. There may be situations where something happens during loop execution and we don't want the rest of the inner code to run.
It is usually possible to fix this with complicated if statements and extra variables. Fortunately, many languages provide cleaner ways of controlling loop flow.
-
The break statement is placed somewhere inside a loop (normaly inside an if statement). It tells the computer to stop whatever it is doing, leave the loop, and continue on with the rest of the program.
The crude diagram above illustrates how this idea works with a while loop. For the most part, the loop will behave as per usual, checking the condition we give it until it is no longer true. But if the break statement is triggered, the computer will immediately jump to the code after the loop.
The following example code shows a break statement in action.
for (int i = 1; i <= 10; i++) {
printf("Start of iteration %d.\n",i);
if (i == 3) {
break;
}
printf("End of iteration %d.\n",i);
}
Ignoring the inner code, this is a loop that counts from 1 to 10. The first time it runs, i = 1 and so the break statement isn't triggered. Both printf calls go through uninterrupted. Similarly with the second time.
The third time it runs, the computer prints out "Start of iteration 3." as expected. Then it checks the if statement. Because (i == 3) is now true, the break statement is triggered, and the computer exits the loop without even printing "End of iteration 3." None of the other numbers from 4 to 10 are ever reached.
(You might want to try compiling and running this code to see what kind of output you get. Make sure you understand why it works the way it does.)
-
The continue statement is also placed somewhere inside a loop. It tells the computer to stop whatever it is doing and jumps back to the start of the inner loop code. If it's a for loop, it will also execute the update code (e.g. i++).
This is best illustrated with another example. The following code prints out all of the odd numbers from 1 to 10:
for (int i = 1; i <= 10; i++) {
if (i % 2 == 0) { // if i is even
continue;
}
printf("%d\n",i);
}
How does it work? Each time the computer enters the inner loop, i is either odd or even:
-
If i is odd, the continue statement is ignored. The computer continues on as it usually would: it prints out the value, increments i (that's the i++ at work), and heads back to check the condition.
-
If i is even, the continue statement is triggered. The computer skips over everything else in the loop (including the printf, so nothing is printed), increments i (that's the i++ at work), and heads back to check the condition.
Again, try compiling this code and making sure you understand why it works.
The end result is that only the odd numbers in the range are printed. Of course we could achieve the same thing by replacing the inner code with "if i is odd, then print it". But in many cases, continue is the more convenient and/or readable option.
Simulating the water tank (II)
Let's return to our rainfall simulation. Before, we noticed that we want to find out on which day the tank is first full. It follows that as soon as the tank is full, we can take the number of that day, print it, and end the simulation (that is, exit the loop).
This translates nicely into a break statement. Once the rain tank is full, we will instruct the computer to print out the number of days that have passed, before using a break statement to cleanly end the loop. Our code will look a little like this:
total_rainfall = 0;
for (int day = 1; day <= N; day++) {
<read an integer into current_rainfall>
total_rainfall += current_rainfall;
if (total_rainfall >= tank_capacity) {
//the tank is full
<print the value of day>
break;
}
}
Thus ends the simulation. There are other ways of ending the loop, but this is the simplest way I am aware of. Using an approach like this you should be able to score 100% for Drought.
__END__
$site->putPageFooter();
# Always return true.
1;