Sample Solutions

Below is the full description for Culture, the first question of the 2003 Australian Informatics Competition.

Beneath this problem description are sample solutions for Culture in the programming languages C, C++ and Pascal. Each of these solutions scores 100%.

Problem Description: Culture

Input File: cultin.txt
Output File: cultout.txt
Time Limit: 1 second

You are a biologist working in a large laboratory. For the last month you have been growing a culture of your favourite bacteria, Bacillus Fortranicus. You are particularly interested in the way in which it grows in hostile environments.

Today is the last day of your experimentation. With anticipation you pull your log book from the shelf, but in your excitement you knock a bottle of acid from the bench. You watch in despair as it spills across your log book and your precious notes dissolve before your eyes.

You try desperately to recall some statistics. How many individual bacteria did you begin with? You can't even remember for how many days the experiment has been running. In desperation you call over your lab assistant.

"No, I don't remember how many bacteria we began with either," she says. "But I do remember that it was an odd number. Oh yes, and the number of bacteria doubled each day." She looks down at the bench, sniffs the acid and walks back to her desk with a wrinkled nose.

Although you have lost your notes, you can still count the total number of bacteria that you have now. Combining this total with the assistant's information, you must write a program to answer your two original questions. That is, you must calculate (i) how many bacteria you began with, and (ii) for how many days the experiment has been running.

Input

The input file will consist of one line only. This line will contain a single integer n representing the number of bacteria that you have now. You are guaranteed that 1 <= n <= 30,000.

Output

The output file must consist of the two integers b and d on a single line, where b represents the number of bacteria at the beginning of the experiment and d represents the number of days for which the experiment has been running. These two integers must be separated by a single space.

Sample Input

Sample Output

17 3

The sample data above can be explained as follows. We are given that the final bacteria count is 136. Observe that 136 = 17 x 2 x 2 x 2. Since 17 is odd, we see that the initial bacteria count was 17. Furthermore, the bacteria count has doubled three times and so the experiment must have been running for precisely three days.

Scoring

The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.

Sample C Solution

#include <stdio.h>

int main() {
    FILE* in;
    FILE* out;
    int total, start, days;

    // Open the I/O files.
    in = fopen("cultin.txt", "r");
    out = fopen("cultout.txt", "w");

    // Read in the total number of bacteria.
    fscanf(in, "%d", &total);

    // Assume the experiment has been running for 0 days.
    start = total;
    days = 0;

    // While the initial number of bacteria is still even, halve this
    // initial number and add one day to the experiment.
    while (start % 2 == 0) {
        start = start / 2;
        days++;
    }

    // Now the initial number of bacteria is odd, so we must have our
    // solution.
    fprintf(out, "%d %d\n", start, days);

    // Tidy up.
    fclose(in);
    fclose(out);
    return 0;
}

Sample C++ Solution

#include <fstream>

int main() {
    // Open the I/O files.
    std::ifstream in("cultin.txt");
    std::ofstream out("cultout.txt");

    // Read in the total number of bacteria.
    long total;
    in >> total;

    // Assume the experiment has been running for 0 days.
    long start = total;
    long days = 0;

    // While the initial number of bacteria is still even, halve this
    // initial number and add one day to the experiment.
    while (start % 2 == 0) {
        start = start / 2;
        days++;
    }

    // Now the initial number of bacteria is odd, so we must have our
    // solution.
    out << start << ' ' << days << '\n';
    return 0;
}

Sample Pascal Solution

program Culture;

var
    inFile : text;
    outFile : text;
    total : integer;    { The final number of bacteria. }
    start : integer;    { The number of bacteria we began with. }
    days : integer;     { The number of days the experiment has run. }

begin
    { Open the I/O files. }
    assign(inFile, 'cultin.txt');
    reset(inFile);
    assign(outFile, 'cultout.txt');
    rewrite(outFile);

    { Read in the total number of bacteria. }
    readln(inFile, total);

    { Assume the experiment has been running for 0 days. }
    start := total;
    days := 0;

    { While the initial number of bacteria is still even, halve this
      initial number and add one day to the experiment. }
    while start mod 2 = 0 do begin
        start := start div 2;
        days := days + 1;
    end;

    { Now the initial number of bacteria is odd, so we must have our
      solution. }
    writeln(outFile, start, ' ', days);

    { Tidy up. }
    close(inFile);
    close(outFile);
end.