- Baseball
- The problem is to keep track of a game of (simplified) baseball
during one team's half of an inning. The input is a series of
characters describing the outcome of each successive pitch:
- B--Ball (the ball was not in the strike zone and the batter did
not try to hit it)
- F--Foul (the batter hit the ball but it went out of fair territory)
- H--Hit (the batter hit the ball in fair territory and ran to first base)
- O--Out (the batter hit the ball but it was caught in flight)
- S--Strike (the ball was not hit but it was in the strike zone or
the batter tried to hit it)
To make things easier, we'll assume that all hits are singles (that is,
the batter runs to first base and any other runner advances to the next
base), and the only ways a player can be put out are to get three
strikes or to hit the ball and have it caught. In particular, we won't
consider tag outs, forced outs, stolen bases, home runs, errors, wild
pitches, or any of the other complications that make a real baseball
game interesting (or not, depending on your point of view...).
Therefore, the relevant rules are the following:
- Each batter receives a series of pitches until one of the
following occurs:
- The batter has received four Balls. When this happens,
the batter goes to first and any other runners advance one base.
- The batter gets a Hit. The batter goes to first and any
other runners advance one base.
- The batter gets an Out. The batter leaves the field and
any runners stay where they were.
- The batter has received three Strikes. This is also an
out, so the batter leaves the field and any runners stay where they
were.
- If the batter hits a Foul ball, it counts as a
Strike, unless the batter already has two strikes, in which
case it is ignored.
- Runners advance from first base to second base, then to third
base, and finally to home. Each runner who makes it home scores a run
(and leaves the field to await their next turn at bat).
- The half-inning is over when the third out is received.
Your program should keep reading characters until the half-inning is
over. The output should be the number of runs scored during the
half-inning. For example, with the following input (the spaces
here separate each batter, but your program should not rely on this):
H BBBB BFBFBFS O SSFFFFFFFFFFH BBBSSH FFBBBFFB SSBBBS
the output should be 2. (The first player gets a hit, the second
gets a base on balls, the third strikes out, the fourth flies out, the
fifth gets a hit after lots of foul balls, the sixth gets a hit and
brings in a run, the seventh gets a base on balls and brings in the
second run, and the eighth strikes out.) If there is more input after
the third out, ignore it.
- Brackets
- (This is based on a true story.) A somewhat misguided
committee of computer scientists decides to create a new computer
language that requires lots of parentheses. However, they quickly
realize that they are going to spend a lot of time counting how many
parentheses are still open at the end of an expression and then typing
enough closing parentheses to match them all. One of them hits upon the
idea of using a closing bracket,
']', to mean ``close a
bunch of open parentheses all at once.'' They debate for a while whether
the rule should be ``close all the open parentheses'' or ``close
only the open parentheses that don't get closed later in the
expression,'' but each of these choices has some disadvantages. Finally
they decide that they will also have opening brackets, and a closing
bracket will close all of the open parentheses back to the matching
opening bracket.
To restate, the rules for a well-formed expression are that each opening
left bracket, '[', must be matched by a closing right bracket,
']'. Each opening left parenthesis, '(', must be matched
by a corresponding right parenthesis, ')', with the exception
that a right bracket will also serve as a closing symbol for any
remaining open parentheses that were contained within the matched pair
of brackets.
Here are some examples of well-formed expressions using this rule, where
all of the real content of the expression has been left out to just
leave the skeleton of parentheses and brackets:
( )
( ) ( )
( ( ) )
[ ( ) ]
[ ( ( ) ]
[ ( ( ( ]
( [ ( ) ( ] )
[ ( ( [ ( ] ) ) ]
[ ( ( ] [ ]
Your task is to write a program to check that a sequence of opening and
closing parentheses and brackets is well-formed according to this rule.
The input will be the sequence to be checked, followed by a question
mark signalling the end of the input. The output should be the single
word YES or NO reporting whether or not the sequence was
properly matched up. For example, if the input is
[ ( ( ] [ ] ?
then the output should be YES, while if
the input is
( [ ( ] ?
then the output
should be NO (since the initial opening parenthesis was never
closed). Recall that C++ automatically skips over blanks and newlines in
the input if you use cin >> c; for a char variable
c, so the spaces in the above examples are irrelevant. You may
assume that there will never be more than 100 currently open symbols at
any point in a valid expression.
- Eeny Meeny
- An ancient math problem concerns a group of people who
stand in a circle and count off by reciting a rhyme such as ``Eeny
Meeny, Miney Mo, ...'' (or simply by counting up to some predetermined
number; there are lots of versions of this). Every time the count comes
to the end, the last person leaves the circle and the count starts over
with the next person. This continues until only one person is left.
Some variations end with the last person being killed, while others have
the last person as the only survivor. We will consider a much more
benign version; the people will be numbered 1 through N, and as each
person leaves the circle we will just print out their number. To make
matters simple, we will just say ``Eeny Meeny,'' so as we go around the
circle, every other person will be eliminated (the ``Meenies'').
For example, if we start with 10 people standing in order from 1 to 10,
then the order in which they are eliminated is 2, 4, 6, 8, 10, 3, 7, 1,
9, 5. It is pretty easy to write a program to do this, especially if we
have a queue ADT available. After filling up the queue with the
appropriate numbers, we repeatedly remove the front element and then
either reinsert it at the end or print it out, switching between these
in strict alternation.
Instead of working the problem forwards, your problem is to work it
backwards: figure out an initial ordering for N people so that when
they play ``Eeny Meeny'' the people will be eliminated in strict
increasing order, from 1 to N. For example, when N = 10, if we had
initially lined them up in the order 8, 1, 6, 2, 10, 3, 7, 4, 9, 5, then
the people will be eliminated in the correct order from 1 to 10.
Your program should simply take the number N as input, and print out
the correct initial ordering. For instance, if the input is
3,
then the output should be (please include the commas and spaces)
2, 1, 3
You may assume that the number N is in the range 1 to 100, inclusive.
- Number Names
- Write a program which reads in a positive integer less than 1 billion
(that's the American billion, with 9 zeroes: 1,000,000,000) and prints
out its name in words. For example, if the input is
12345678,
then the output should be
twelve million three hundred forty-five thousand six hundred seventy-eight
(Note: this problem is the ``easy though perhaps tedious'' choice on the
exam; it doesn't require as much insight as some of the others, but it
can turn into a big mess of code to handle all the special cases unless you
design it carefully.)