online advertising

Monday, September 8, 2014

UVa Problem 394 - MapMaker

Problem:

Please find the problem here.

Solution:

This is the simplest problem I ever had, just implement the given formulas! However, it does take me some time to write.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=330

#include "UVa394.h"

#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Array
{
public:
    string name;
    int base_address;
    int element_size;
    int num_dimensions;
    vector<int> lower_bounds;
    vector<int> upper_bounds;
    vector<int> constants;
};

int UVa394()
{
    int num_arrays, num_references;
    cin >> num_arrays;
    cin >> num_references;
    Array* arrays = new Array[num_arrays];
    for (int i = 0; i < num_arrays; i++)
    {
        cin >> arrays[i].name;
        cin >> arrays[i].base_address;
        cin >> arrays[i].element_size;
        cin >> arrays[i].num_dimensions;
        for (int j = 0; j < arrays[i].num_dimensions; j++)
        {
            int lower_bound;
            int upper_bound;
            cin >> lower_bound;
            cin >> upper_bound;
            arrays[i].lower_bounds.push_back(lower_bound);
            arrays[i].upper_bounds.push_back(upper_bound);
            arrays[i].constants.push_back(0);
        }
        arrays[i].constants.push_back(0);

        arrays[i].constants[arrays[i].num_dimensions] = arrays[i].element_size;
        for (int j = arrays[i].num_dimensions - 1; j > 0; j--)
        {
            arrays[i].constants[j] = arrays[i].constants[j + 1] * (arrays[i].upper_bounds[j] - arrays[i].lower_bounds[j] + 1);
        }
        arrays[i].constants[0] = arrays[i].base_address;
        for (int j = 1; j <= arrays[i].num_dimensions; j++)
        {
            arrays[i].constants[0] -= arrays[i].constants[j] * arrays[i].lower_bounds[j - 1];
        }
    }
    for (int i = 0; i < num_references; i++)
    {
        string array_name;
        cin >> array_name;
        for (int j = 0; j < num_arrays; j++)
        {
            if (arrays[j].name == array_name)
            {
                cout << arrays[j].name;
                cout << "[";
                int result = arrays[j].constants[0];
                for (int k = 0; k < arrays[j].num_dimensions; k++)
                {
                    if (k != 0)
                    {
                        cout << ", ";
                    }
                    int reference_index;
                    cin >> reference_index;
                    cout << reference_index;
                    result += reference_index * arrays[j].constants[k + 1];
                }
                cout << "] = ";
                cout << result << endl;
            }
        }
    }
    delete[] arrays;
    return 0;
}

5 comments :

  1. This comment has been removed by the author.

    ReplyDelete
  2. can you explain it further in details how you are manipulating the array

    ReplyDelete
  3. Thanks for the comment - you are the 2nd people who comments in my blog.

    Sure, but I am afraid the code and the problem itself is already quite clear.
    Are there something you are unclear about it?

    ReplyDelete
    Replies
    1. yaa actually see i know the formula for finding the offset for address for 2-d and 3-d array but here i have to find out for n upto 10 so then i went looking for finding offset for n-d array but i didn't find out so i decided to look for the solution so i just want to know the logic or is there any formula or the way i had completely understand the code means how it's working and in what place i had what value but i don,t understand the why we are taking that value like if we take a simple example of "ONE 1500 2 2 0 3 1 5" so according to your code
      name will be ONE
      base_address will be 1500
      element_size will be 2 ......
      lower_index[0]=0 upper_index[0]=3 constant[0]=1500
      lower_index[1]=1 upper_index[1]=5 constant[1]=(5-1)*2=10
      constant[2]=2
      after that you are doing some subtraction so could you kindly explain me what you are doing and why you are doing that ?

      Delete
    2. This comment has been removed by the author.

      Delete