Usaco Oct10 Bronze

Part of USACO Oct10

**********************************************************************
                           BRONZE PROBLEMS
**********************************************************************
                  Two problems numbered 11 through 12
**********************************************************************

Problem 11: Interactive Guess my Number [Kolstad, 2007]

Bessie is thinking of a secret integer between 1 and N (1 <= N <=
2,000,000,000) inclusive. You must write a program to guess this
integer in as few guesses as possible.

This is a 'reactive' task. Your program should read from standard
input (the console) and write to standard output. See special
instructions below.

Initially, your program should read a single integer N on a line
all by itself.

You should then conduct a dialog:
    * Print a single integer on a line by itself as your guess
    * Read a line that contains a single character 'H' or 'L'
      telling you if your guess was high or low.
    * Your program will be forcefully terminated when you guess
      the proper number or if you take too many guesses (the grader
      calculates this as a function of N) altogether.

By way of example, consider a dialog where the range of numbers is
1..25 and the computer's secret number is 15. Below is a sample
of the interactions where the '<-' arrow means a line coming into
your program via standard input and the '->' arrow means a line
going to standard output:

       <- 25
       -> 13
       <- L
       -> 14
       <- L
       -> 15
  [program is terminated by grader]

Interactive programs usually require extra code that causes output
to be unbuffered -- to be written in real time instead of buffering
for faster (but later) output.

Those C/C++ users who use #include <stdio.h> should execute this
line before any input or output:

    setlinebuf (stdout);

Users of <stdio.h> should also use fgets () to read from stdin.
Use of scanf is not recommended; do something like this to parse
input data:

    char line[1000];
    setlinebuf (stdout);

    fgets (line, 1000, stdin);
    sscanf (line, "..format..", &var1, ...);
    /* if the line contents need to be interpreted */

Those C++ users who use iostream should cout << flush after each
line (and also use cin in the normal manner):

    cout << guess << endl;
    cout << flush;

Be sure when you read the response from the computer that you read
*all* the letters, not just the first one. The response will never
be more than one letter + one newline + one string terminator ('\0').

Java users should use the following output scheme for output:

    import java.io.*;
    ...
    PrintStream out = new PrintStream (System.out, true); // 'unbuffers' output
    ...
    // sample integer print:
    out.println (guess);

For Pascal, use the following scheme for writing:

    writeln (stdout, ...your output here...); flush(stdout);

Be sure to read in the entire reply -- make room for the letter, the
newline, and the string terminator.

Despite the references to iguess.in and iguess.out below, no files are
used for input or output.

PROBLEM NAME: iguess

INPUT FORMAT:

* Lines 1..??: See above

SAMPLE INPUT (file iguess.in):

OUTPUT FORMAT:

* Lines 1..??: See above.

SAMPLE OUTPUT (file iguess.out):

**********************************************************************

Problem 12: Counting Beads [Sherry Wu, 2010]

Bessie has spilled her collection of N (1 <= N <= 80) blue and orange
cowbeads (represented as 1s and 0s, respectively, in the human world) on
the floor. She cleans up the mess by arranging the beads into a long line.
She then counts the number of times a blue bead is next to an orange bead
and vice versa, but is not sure if she is correct. Write a program to
validate Bessie's count.

PROBLEM NAME: countbead

INPUT FORMAT:

* Line 1: A single integer: N

* Line 2: Line 2 contains N integers, each of which is 0 or 1

SAMPLE INPUT (file countbead.in):

6
1 0 0 1 1 1

INPUT DETAILS:

There are six beads in total: the first bead in the line is a blue bead,
followed by two orange beads, and finally by three blue beads.

OUTPUT FORMAT:

* Line 1: A single integer describing the number of occurrences that a
        blue bead is next to an orange bead and vice versa.

SAMPLE OUTPUT (file countbead.out):

2

OUTPUT DETAILS:

There are two times in the line that two differently colored beads are next
to each other.

**********************************************************************
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License