"Warmup" Programming Assignments


See Program 10189 or see below:

Implement in a language of your choice.

  • In order to use the online judge, use Java, C, C++, or Pascal.
  • Register for the online judge
  • Your program needs a comment line such as: /* @JUDGE_ID: 1000AA 100 C "Dynamic Programming" */
    The argument after the @JUDGE_ID: is your user ID (1000AA for example), followed by the problem number (100 in the example),
    then by the language used.
  • FOR FULL CREDIT you must submit your programs and have them "Accepted" by the online judge

    Here are the warmup problems:

    1. The 3n + 1 problem (program number for judge submission: 100)
      (Sample starter in C, and also Java version)
      (Also, see these shell versions if you need more help: C and Java version)
      • Consider the following algorithm to generate a sequence of numbers. Start with an integer n.
        If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat
        this process with the new value of n, terminating when n = 1. For example,
        the following sequence of numbers will be generated for n = 22:
                     22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
        
      • It is conjectured that this algorithm will terminate at n = 1 for every integer n.
        This conjecture holds for all integers up to at least n = 1,000,000.
      • For an input n, the cycle-length of n is the number of numbers
        generated up to and including the 1. In the example above, the cycle length of
        22 is 16. Given any two numbers i and j, you are to determine the
        maximum cycle length over all the numbers between i and j, including
        both endpoints.

      • Input: The input consists of a series of pair of integers i and j, one
        pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

      • Output: For each pair of input integers i and j, output i, j
        in the same order they appeared in the input and then the maximum cycle length
        for integers between and including i and j. These three numbers
        should be separated by one space, with all three numbers on one line and with
        one line of output for each line of input.
                    Sample Input             Sample Output
        	     1 10                   1 10 20
        	     100 200                100 200 125
        	     201 210                201 210 89
        	     900 1000               900 1000 174
        

    2. Minesweeper (program number for judge submission: 10189)
      (Sample starter in C (dynamic allocation) and starter in C (static allocation)
      Also see these shell versions if you need more help: C and Java version
      • The goal of the game is to find where all the mines are located within a M x N field.
      • The game shows a number in a square which tells you how many mines there are
        adjacent to that square. Each square has at most eight adjacent squares. The
        4 x 4 field on the left contains two mines, each represented by a "*" character.
        If we represent the same field by the hint numbers described above, we end up
        with the field on the right.
                  * . . .           * 1 0 0
        	  . . . .           2 2 1 0
        	  . * . .           1 * 1 0 
                  . . . . 	    1 1 1 0
        
      • Input: The input will consist of an arbitrary number of fields. The first
        line of each field contains two integers n and m (both are
        greater than 0 and less than or equal to 100) which stand for the number of rows
        and columns of the field. Each of the next n lines contains exactly m
        characters representing the field.
      • Safe squares are denoted by "." and mine squares by "*". The first field line where
        n = m = 0 represents the end of the input and should not be processed.

      • Output: For each field, print the message Field #x: on the line alone,
        where x stands for the number of the field starting from 1. The next n
        lines should contain the field with the "." characters replaced by the number of mines
        adjacent to that square. There must be an empty line between field outputs.
                  Sample input    Sample output
        	  4 4              Field #1
        	  * . . .           * 1 0 0
        	  . . . .           2 2 1 0
        	  . * . .           1 * 1 0 
                  . . . . 	    1 1 1 0
        	  
        	  3 5              Field #2
        	  * * . . .           * * 1 0 0
        	  . . . . .           3 3 2 0 0
        	  . * . . .           1 * 1 0 0 
                  
        	  0 0
         
        In your ouput and input, you don't need to put spaces between the characters.