A computer's memory is one-dimensional, but we often need to represent two-dimensional (or higher) objects. If an array A has three rows and two columns, we could store A in memory as either a sequence of rows (row-major order),
or a sequence of columns (column-major order).*--------+--------+--------+--------+--------+--------* | A[1,1] | A[1,2] | A[2,1] | A[2,2] | A[3,1] | A[3,2] | *--------+--------+--------+--------+--------+--------*
*--------+--------+--------+--------+--------+--------* | A[1,1] | A[2,1] | A[3,1] | A[1,2] | A[2,2] | A[3,2] | *--------+--------+--------+--------+--------+--------*
Other representations are of course possible, but these two are the most convenient. Note that in row-major form the row numbers vary least quickly as you read the elements from left to right, and in column-major form the column numbers vary least quickly. This property generalizes to higher dimensions; for example, in the row-major layout of a three-dimensional array, the first dimension will vary least quickly and the last dimension will vary most quickly. Your job is to write a program that can compute the exact location of any element of an array.
The input will consist of one or more lines, each of which contains an array description. Each array description will contain the following parameters separated by spaces: d, the dimension of the array; B, the base address of the array; w, the width in bytes of each element of the array; d numbers representing the size of the array in each dimension; and d indices that select an element of the array. Arrays are origin-1, meaning that all the first elements in each dimension are numbered 1, the second are numbered 2, and so on. (This differs from C and C++, which are origin-0.) Arrays will not be empty, meaning that the size for all dimensions will be at least 1. The total length of a line will not exceed 255 characters. No indices will exceed the bounds of the array.
For each array description, output the exact address of the selected array element assuming that the array is stored in row-major order. The final address will fit into a signed 32-bit integer.
Input must be read from the file prob45.in, and output must be written to the file prob45.out. All output to the screen will be ignored.
1 0 4 10 5 3 220 8 6 2 3 5 1 2
16 420
A version of this problem originally appeared in the 1996 ACM Mid-Central regional programming contest.
Dr. Eric Shade