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.

**********************************************************************```
```
page revision: 1, last edited: 08 Jul 2011 02:31
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License