Programming Tournament

2008 UHD ACM Programming Contest

Contest "Fair" Rules

• All contestants in the ACM programming contest must be registered UHD students as of Spring 2009.
  
• Each team must have at most three members.
  
• Each team can only use one computer during the contest.
  
• Your programs should be written in C/C++. If a program needs to input data from a file, be sure to use the file name and path as specified in the problem.
  
• Teams are expected to work separately on solving contest problems.
  
• Contestants may use any reference manuals or books. Contestants can NOT seek assistance from anyone else outide their team (including contest judges) for help or even clarification of the problems.
  
• Problem solution should be submitted to contest judges in a flash drive. Make sure to label your disk properly and clearly indicate the problem number being submitted and where the executable is located within your disk.
  
• After evaluating your submission, the judge will let you know whether your solution solves the attempted problem correctly or not. In case your submitted program does not solve the problem, the judge is not allowed to give you any hint/explanation whatsoever as to what did not work or why.
  
• You can submit your program as many times as you wish. Submissions are evaluated on a FCFS basis. Expect the evaluation process for each problem to take about 5 minutes.
  

Contest Ranking Criteria

Contest problems are equally weighed. Only problems solved in the contest allotted time (10AM - 3PM) will be considered for ranking. Ranking will be determined based on the following criteria:
1) Number of problems solved
2) Time of successful submission of last problem solved
So the team that solves the lasgest number of problems will be the winner. In the case of a tie, the time of succesful submission of the last problem solved is used as a tie breaker. If there's still a tie, then a tie will be declared.

Input: inputB.dat
Output: standard output device (i.e. console)

Background
Problems that require minimum paths through some domain appear in many different areas of computer science. For example, one of the constraints in VLSI routing problems is minimizing wire length. The Traveling Salesperson Problem (TSP) -- finding whether all the cities in a salesperson's route can be visited exactly once with a specified limit on travel time -- is one of the canonical examples of an NP-complete problem; solutions appear to require an inordinate amount of time to generate, but are simple to check.

This problem deals with finding a minimal path through a grid of points while traveling only from left to right.

The Problem
Given an m x n matrix of integers, you are to write a program that computes a path of minimal weight. A path starts anywhere in column 1 (the first column) and consists of a sequence of steps terminating in column n (the last column). A step consists of traveling from column i to column i + 1 adjacent, i.e., the matrix "wraps" so that it represents a horizontal cylinder. Legal steps are illustrated below.

The weight of a path is the sum of the integers in each of the n cells of the matrix that are visited. For example, two slightly different 5 x 6 matrices are shown below (the only difference is the numbers in the bottom row).

The minimal path is illustrated for each matrix. Note that the path for the matrix on the right takes advantage of the adjacency property of the first and last rows.

The Input
The input consists of a matrix specification. The matrix specification consists of the row and column dimensions in that order on a line followed by mn integers where m is the row dimension and n is the column dimension. The integers appear in the input in row major order, i.e., the first n integers constitute the first row of the matrix, the second n integers constitute the second row and so on. The integers on a line will be separated from other integers by one or more spaces. Note: integers are not restricted to being positive. There will be only one matrix specification in an input file. Input is terminated by end-of-file.

For each specification the number of rows will be between 1 and 10 inclusive; the number of columns will be between 1 and 100 inclusive. No path's weight will exceed integer values representable using 30 bits.

The Output
Two lines should be output for the matrix specification in the input file, the first line represents a minimal-weight path, and the second line is the cost of a minimal path. The path consists of a sequence of n integers (separated by one or more spaces) representing the rows that constitute the minimal path. If there is more than one path of minimal weight the path that is lexicographically smallest should be output.

Sample Input
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4

Expected Output
1 2 3 4 4 5
16

SOLUTION: http://nopaste.info/f7ac3da109.html

Input: inputC.txt
Output: standard output device (i.e. console)

Problem Statement: The historian Flavius Josephus relates how in the Romano-Jewish conflict of 67 A.D., the Romans took the town of Jotapata which he was commanding. Escaping, Josephus found himself trapped in a cave with 40 companions. The Romans discovered his whereabouts and invited him to surrender, but his companions refused to allow him to do so. He therefore suggested that they kill each other, one by one, the order to be decided by lot. Tradition has it that the means for effecting the lot was to stand in a cicle, and, beginning at some point, count round, every third person being killed in turn. The sole survivor of this process was Josephus, who then surrendered to the Romans. Which begs the question: had Josephus previously practiced quietly with 41 stones in a dark corner, or had he calculated mathematically that he should adopt the 31st position in order to survive?

Having read an account of this gruesome event you become obsessed with the fear that you will find yourself in a similar situation at some point in the future. In order to prepare yourself for such an eventuality you decide to write a program to run on your hand-held PC which will determine the position that the counting process should start in order to ensure that you will be the sole survivor.

In particular, your program should be able to handle the following variation of the processes described by Josephus. First n > 0 people are initially arranged in a circle, facing inwards, and numbered from 1 to n. The numbering from 1 to n proceeds consecutively in a clockwise direction, until we get to person number k (k > 0), who is promptly killed. We then proceed to count a further k people in a clockwise direction, starting with the person immediately to the left of the victim. The person number k so selected has the job of burying the victim, and then returning to the position in the circle that the victim had previously occupied. Counting then proceeds from the person to his immediate left, with the kth person being killed, and so on, until only one person remains.

For example, when n = 5, and k = 2, and i = 1, the order of the execution is 2, 5, 3, and 1. The survivor is 4.

Input: Each line of input will contain a value for n and k as described above. Input will be terminated by the value 0 0 on a line. You may assume that 1 <= n <= 1000

Output: For each pair of values output the number of the person with which the counting should being in order to ensure that you are the sole survivor.

A sample input and its corresponding output are shown below.

Sample Input:
5 2
1 5
0 0

Expected Output:
3
1