394 - Mapmaker

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Problem 394, easy in theory but ...

Post by WR » Tue Mar 23, 2004 2:41 pm

My WA list keeps growing and growing, which is especially annoying when relatively easy problems have to be added.

Problem 394 ist probably one of the easier problems.

Is there any tricky input, like lower and upper bounds switched?
Could there be negative indices?

As all my sample input is processed correctly I need some test cases.

Thanks

Oh btw, I'm using Pascal for this problem. Could the WA really be some run-time error (array's too small or something like that)? I've read this happens from time to time.

Akhnukh
New poster
Posts: 3
Joined: Wed Sep 22, 2004 1:53 pm

394 Map Maker WA

Post by Akhnukh » Wed Sep 22, 2004 2:01 pm

any one help me in solving this problem it is giving me wa error i hav checked with given sample input it is working well or any one can send me sample test casees

this is my problem code
#include<iostream>
using namespace std;

struct Array
{

char name[10];
int B;
int Cd;
int D;
int U[20];

Array()
{
int j;
for(j=0;j<10;j++)
name[j]='*';
B=0;
Cd=0;
D=0;

}

bool equal(char* a)
{
int i;

for(i=0;i<10;i++)
{
if(name!=a)
return false;
}
return true;
}
void setArray(int a)
{

char na[10];
int k;
for(k=0;k<10;k++)
{
na[k]='*';
}
int i;
cin>>na;
cin>>B;
cin>>Cd;
cin>>D;

//U=new int[2*D];

for(i=0;i<2*D;i=i+2)
{
cin>>U;
cin>>U[i+1];

}

for(int j=0;j<10;j++)
{
name[j]=na[j];
}
}

};


struct Input
{

char name[10];
int in[10];

Input()
{
int j;
for(j=0;j<10;j++)
name[j]='*';

}

void setInput(char* na ,int d)
{

int i;
for(i=0;i<10;i++)
name=na;

for(i=0;i<d;i++)
cin>>in;

}

};

void solve(Array* Ar,Input In,int siz)
{

int index;
int add;
int size;


for(index=0;index<siz;index++)
{



if(Ar[index].equal(In.name))
{
if(index!=0)
cout<<endl;
cout<<Ar[index].name<<"[";
size=Ar[index].D;
int C[10];
//C=new int[size];
C[size-1]=Ar[index].Cd;

int k,u,j,l;

u=(size*2)-1;
for(k=size-2;k>=0;k--)
{
C[k]=C[k+1]*(Ar[index].U-Ar[index].U[u-1]+1);

}

int Co;

for(j=0;j<size;j++)
{
Co=Co+(C[j]*Ar[index].U[2*j]);
}
Co=Ar[index].B-Co;



for(l=0;l<size;l++)
{
add=add+(C[l]*In.in[l]);
}
add=add+Co;


// cout<<Ar[index].name"["<<add<<endl;

}
}

for(index=0;index<size;index++)
{

if(size==1)
{
cout<<In.in[index]<<"] = ";
}
else
{

if(index==0)
cout<<In.in[index];

if(index==size-1)
cout<<", "<<In.in[index]<<"] = ";
else if((index!=size-1)&&(index!=0))
cout<<", "<<In.in[index]; ///////
}


}
cout<<add;

}

int getDim(Array* a,int siz,char* name)
{
int i;
for(i=0;i<siz;i++)
{
if(a.equal(name))
return a.D;

}
return 0;


}

int main()
{
int i=0,j=0,k=0,l=0;


cin>>i>>j;

Array a[5000];
Input In[5000];

// for(k=0;k<i;k++)
// {
//
// }

for(k=0;k<i;k++)
{
a[k].setArray(0);

}


for(k=0;k<j;k++)
{

char input[10];

int temp;
for(temp=0;temp<10;temp++)
input[temp]='*';


cin>>input;
int d;
d=getDim(a,i,input);

In[k].setInput(input,d);
}

for(k=0;k<j;k++)
{
solve(a,In[k],i);
}




return 0 ;

}

Akhnukh
New poster
Posts: 3
Joined: Wed Sep 22, 2004 1:53 pm

Dear Have u got some solution for Problem 394

Post by Akhnukh » Wed Sep 22, 2004 2:06 pm

tell me i have same problem Wa have u any clue plz help me

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Sep 19, 2005 2:00 am

There are some test cases. Try them. May be they can help.

Input:

Code: Select all

4 8
ONE       1500 2 2 0 3 1 5
TWO       2000 4 3 1 4 0 5 5 10
THREE     3000 1 1 1 9
FOUR      5000 3 4 0 4 19 22 22 32 9 12
ONE       2 4
THREE     7
TWO       2 0 6
TWO       3 3 9
FOUR      1 20 23 11
FOUR      4 21 31 9
FIVE   
THREE     8
Output:

Code: Select all

ONE[2, 4] = 1526
THREE[7] = 3006
TWO[2, 0, 6] = 2148
TWO[3, 3, 9] = 2376
FOUR[1, 20, 23, 11] = 5678
FOUR[4, 21, 31, 9] = 7484
THREE[8] = 3007
I ignored the query names that donot match with any array names. But I m not sure that they have this types of input or not. But my Accepted code can handle this...
Ami ekhono shopno dekhi...
HomePage

arh
New poster
Posts: 2
Joined: Tue Sep 27, 2005 9:37 am

Post by arh » Tue Sep 27, 2005 9:49 am

I have the same problem. I've tried the following input:

Code: Select all

4 8
ONE       1500 2 2 0 3 1 5
TWO       2000 4 3 1 4 0 5 5 10
THREE     3000 1 1 1 9
FOUR      5000 3 4 0 4 19 22 22 32 9 12
ONE       2 4
THREE     7
TWO       2 0 6
TWO       3 3 9
FOUR      1 20 23 11
FOUR      4 21 31 9
FIVE   
THREE     8
and my solution produced the following results, which are correct:

Code: Select all

ONE[2, 4] = 1526
THREE[7] = 3006
TWO[2, 0, 6] = 2148
TWO[3, 3, 9] = 2376
FOUR[1, 20, 23, 11] = 5678
FOUR[4, 21, 31, 9] = 7484
THREE[8] = 3007
The problem is not complicated, but I cannot find the input which will give me incorrect result.

I would appreciate any help with this issue.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Sep 28, 2005 5:59 am

Hi,

I've tried this input in my Accepted program

Code: Select all

4 7
ONE       1500 2 2 0 3 1 5
TWO       2000 4 3 1 4 0 5 5 10
THREE     3000 1 1 1 9
FOUR      5000 3 4 0 4 19 22 22 32 9 12
ONE       2 4
THREE     7
TWO       2 0 6
TWO       3 3 9
FOUR      1 20 23 11
FOUR      4 21 31 9
THREE     8
and my output is the same as yours:

Code: Select all

ONE[2, 4] = 1526
THREE[7] = 3006
TWO[2, 0, 6] = 2148
TWO[3, 3, 9] = 2376
FOUR[1, 20, 23, 11] = 5678
FOUR[4, 21, 31, 9] = 7484
THREE[8] = 3007
and I don't think that cases of incorrect array names exist.

Just be reminded that there can be many "arrays" in the input. :)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR » Fri Sep 30, 2005 8:03 am

This problem really IS easy to solve - no tricks, no negative indices.

Just try to solve the examples by hand and that's about it. The description is all one needs.

There could be a problem with taking the input and formatting the output of course.

arh
New poster
Posts: 2
Joined: Tue Sep 27, 2005 9:37 am

Post by arh » Thu Oct 13, 2005 2:03 pm

Could you please make a review of my code. I think there should be some trick with an input and output but I can't figure out what exactly should be corrected to get it accepted by judge.

Code: Select all

#include <iostream>
#include <string.h>
using namespace std;

typedef unsigned short USHORT;
typedef USHORT* PUSHORT;
typedef char*   PSZ;

typedef struct
{
  int L;                      // Lower bound
  int U;                      // Upper bound
} BOUND, *PBOUND;

typedef struct
{
  char     name[10];          // Array name
  USHORT   usB;               // Base address of the array
  USHORT   usD;               // Number of dimensions
  USHORT   usCD;              // Array element size in bytes
  PBOUND   pbound;            // Lower and Upper bounds of each dimension
  PUSHORT  pusC;              // Used to calculate address of references
} ARRAY, *PARRAY;

typedef struct
{
  char    name[10];           // Reference name
  PUSHORT pusI;               // Indexes
  USHORT  usD;                // Number of dumensions
  USHORT  usBaseAddress;      // To be calculated 
} REF, *PREF;

typedef struct
{
  USHORT usArrayCount;        // Number of arrays
  USHORT usRefCount;          // Number of references
} CFG, *PCFG;


int main()
{
  PCFG   pcfg   = (PCFG)malloc(sizeof(CFG));
  USHORT usIndex;
  USHORT usIndex2;
  PARRAY pArrays;
  PREF   pRefs;
  PSZ    pChar;

  // Read the configurations parameters - number of arrays and references
  cin >> pcfg->usArrayCount >> pcfg->usRefCount;

  // Allocate memory for Arrays and References
  pArrays = (PARRAY)malloc(pcfg->usArrayCount * sizeof(ARRAY));
  pRefs   = (PREF)malloc(pcfg->usRefCount * sizeof(REF));

  // Begin the input scan for Arrays and calculate necessary data
  for (usIndex = 0; usIndex < pcfg->usArrayCount; usIndex++)
  {
    PARRAY pArray = &pArrays[usIndex];
    char*  pszName = (char*)malloc(sizeof(char));

	// Read the name of the array and check its length.
    cin >> pszName;
    if (strlen(pszName) > 10)
    {
	  goto exit;
	}
    strcpy(pArray->name, pszName);

	// Read the rest of the input
	cin >> pArray->usB;
    cin >> pArray->usCD;
    cin >> pArray->usD;
	// Check the number of dimensions
    if (pArray->usD < 1 || pArray->usD > 10)
    {
	  goto exit;
    }

	// Allocate memory for Array bounds.
    pArray->pbound = (PBOUND)malloc(pArray->usD * sizeof(BOUND));

	// Read Lower and Upper bound for each Array dimension
    for (usIndex2 = 0; usIndex2 < pArray->usD; usIndex2++)
    {
      cin >> pArray->pbound[usIndex2].L >> pArray->pbound[usIndex2].U;
    }

	// Allocate memory for C.
    pArray->pusC = (PUSHORT)malloc((pArray->usD + 1) * sizeof(USHORT));

	// Calcualte C[0]
    pArray->pusC[0] = pArray->usB;
    pArray->pusC[0] -= pArray->usCD * pArray->pbound[pArray->usD - 1].L;

	// Set the C[Last] to be CD
    pArray->pusC[pArray->usD] = pArray->usCD;

	// Calculate all C[i] except C[0] and C[last]
    for (usIndex2 = (pArray->usD - 1); usIndex2 >= 1; usIndex2--)
    {
      pArray->pusC[usIndex2] = pArray->pusC[usIndex2 + 1] * (pArray->pbound[usIndex2].U 
                                                             - pArray->pbound[usIndex2].L + 1);
      pArray->pusC[0] -= pArray->pusC[usIndex2] * pArray->pbound[usIndex2 - 1].L;
    }
  } // End Arrays loop.

  // Begin Refernces loop. Read input and calculate necessary data.
  for (usIndex = 0; usIndex < pcfg->usRefCount; usIndex++)
  {
    PREF   pRef = &pRefs[usIndex];
    pRef->usD = 0;

	// Read the name of the reference
    cin >> pRef->name;

	// Search for the appropriate array in Arrays and calculate BaseAddres
    for (usIndex2 = 0; usIndex2 < pcfg->usArrayCount; usIndex2++)
    {
      PARRAY pArray = &pArrays[usIndex2];
      USHORT usIndex3;

      if (!strcmp(pRef->name, pArray->name))
      {
        pRef->usBaseAddress = pArray->pusC[0];

        pRef->pusI = (PUSHORT)malloc(pArray->usD * sizeof(USHORT));
        pRef->usD = pArray->usD;
        for (usIndex3 = 0; usIndex3 < pArray->usD; usIndex3++)
        {
          cin >> pRef->pusI[usIndex3];
          pRef->usBaseAddress += pRef->pusI[usIndex3] * pArray->pusC[usIndex3 + 1]; 
        }
      }
    } // End Search
  } // End Refernces loop

  // Output
  for (usIndex = 0; usIndex < pcfg->usRefCount; usIndex++)
  {
    PREF pRef = &pRefs[usIndex];

    if (pRef->usD == 0)
    {
      continue;
    }

    cout << pRef->name << "[";
    for (usIndex2 = 0; usIndex2 < pRef->usD; usIndex2++)
    {
      if (usIndex2 == (pRef->usD - 1))
      {
        cout << pRef->pusI[usIndex2];
      }
      else
      {
        cout << pRef->pusI[usIndex2] << ", ";
      }
    }
    cout << "] = ";
    if (usIndex == (pcfg->usRefCount - 1))
    {
      cout << pRef->usBaseAddress;  
    }
    else
    {
      cout << pRef->usBaseAddress << endl;
    }
  }
  goto exit;

  exit:
  {
    free(pArrays);
	free(pRefs);
	return 0;
  }
}

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

394 Mapmakeer .. don't understand.. plz clarify.. ;

Post by helloneo » Fri Jan 06, 2006 6:31 am

http://acm.uva.es/p/v3/394.html

Code: Select all

ONE       1500 2 2 0 3 1 5
ONE       2 4
for this input why the output is 1526..?


my understanding..

C1 = U2-L2 = 4
C2 = array element size = 2
C0 = B - C1*L1 - C2*L2 = 1500 - 4*0 - 2*1 = 1498

ONE[2, 4] = C0 + C1i1 + C2i2 = 1498 + 4*2 + 2*4 = 1514..


plz explain the ouput..
thanks..

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Jan 06, 2006 7:10 am

It's a 4x5 array, within 0..3 and 1..5.
So, [2,4] is 4th element in 3rd row? Or 14th element. Being that the first one is at 1500 and size of element is 2, 1500+2*(14-1) = 1526.

Darko

Temmy_18
New poster
Posts: 1
Joined: Tue Sep 28, 2010 11:47 am

394 mapmaker RTE??

Post by Temmy_18 » Tue Sep 28, 2010 11:54 am

anyone could help, why my code here got RTE? i tested with sample input at home, the output is the same as the sample... thanks

Code: Select all

function trim(s:string): string;
begin
  while s[length(s)] = ' ' do delete(s, length(s), 1);
  trim:= s;
end;

type
  ts10 = string[10];
  trec = record
    nama: ts10;
    lok, uk, dim: longint;
    ia, ib: array [1..10] of longint;
  end;

var
  data: array of trec;
  nama: ts10;
  x,t: array [1..10] of longint;
  n,p,g,h,i,j,k,lok,o,acc,l: longint;
  first: boolean;

begin
  readln(n, p);
  setlength(data, n);
  for i:= 0 to n-1 do begin
    setlength(data[i].nama, 10);
    for j:= 1 to 10 do begin
      read(data[i].nama[j]);
    end;
    read(data[i].lok, data[i].uk, data[i].dim);
    for j:= 1 to data[i].dim do begin
      read(data[i].ia[j], data[i].ib[j]);
    end;
    readln;
  end;

  for i:= 1 to p do begin
    setlength(nama, 10);
    for j:= 1 to 10 do begin
      read(nama[j]);
    end;
    for k:= 0 to n-1 do begin
      if nama = data[k].nama then break;
    end;
    for l:= 1 to data[k].dim do begin
      read(x[l]);
    end;
    readln;

    acc:= 0;
    for g:= 1 to data[k].dim do begin
      t[g]:= x[g]-data[k].ia[g];
      for h:= g+1 to data[k].dim do begin
        t[g]:= t[g] * (data[k].ib[h]-data[k].ia[h]+1);
      end;
      acc:= acc + t[g];
    end;
    lok:= data[k].lok+(acc * data[k].uk);
    write(trim(data[k].nama),'[');

    first:= true;
    for o:= 1 to data[k].dim do begin
      if first= true then begin
        write(x[o]);
        first:= false;
      end else write(', ',x[o]);
    end;
    writeln('] = ', lok);
  end;
end.


Ghaverves
New poster
Posts: 4
Joined: Mon Dec 13, 2010 2:49 pm

394 - Mapmaker

Post by Ghaverves » Thu Dec 16, 2010 2:34 pm

Keep getting WA.
Would appreciate some help,


Test case that I've used:

Code: Select all

    4 7
    ONE       1500 2 2 0 3 1 5
    TWO       2000 4 3 1 4 0 5 5 10
    THREE     3000 1 1 1 9
    FOUR      5000 3 4 0 4 19 22 22 32 9 12
    ONE       2 4
    THREE     7
    TWO       2 0 6
    TWO       3 3 9
    FOUR      1 20 23 11
    FOUR      4 21 31 9
    THREE     8
Output from my code

Code: Select all

ONE[2, 4] = 1526
THREE[7] = 3006
TWO[2, 0, 6] = 2148
TWO[3, 3, 9] = 2376
FOUR[1, 20, 23, 11] = 5678
FOUR[4, 21, 31, 9] = 7484
THREE[8] = 3007

Code: Select all

#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef unsigned int ui;
typedef unsigned long ul;

class data
{
public:
	string name;
	ui B;
	ui CD;
	int D;
	int L[11];
	int U[11];

	ui C(int d)
	{
		ul ans;

		if(d==D)
			return CD;
		else if(d==0)
		{
			ans = B;
			for(int i=1; i<= D; i++)
			{
				ans -= C(i) * L[i];
			}
			return ans;
		}
		else
		{
			return C(d+1) * ( U[d+1] - L[d+1] + 1);
		}
	}
};


int main()
{
	//freopen("input.txt", "r", stdin);
	int N, R;
	cin >> N >> R;

	data *arr = new data[N+1];

	for(int k=0; k<N; k++)
	{
		cin >> arr[k].name;
		cin >> arr[k].B;
		cin >> arr[k].CD;
		cin >> arr[k].D;
	
		for(int j=1; j<=arr[k].D; j++)
		{
			cin >> arr[k].L[j];
			cin >> arr[k].U[j];
		}
	}

	ul answer;
	ul tmpI[11];

	for(int k=0; k<R; k++)
	{
		int i;
		string tmp;
		cin >> tmp;
		for(i=0; arr[i].name!= tmp; i++);

		answer = arr[i].C(0);

		for(int j=1; j<=arr[i].D; j++)
		{
			cin >> tmpI[j];
			answer += arr[i].C(j) * tmpI[j];
		}

		cout << arr[i].name << "[" << tmpI[1];

		for(int j=2; j<=arr[i].D; j++)
		{
			cout<<", " << tmpI[j];
		}

		cout << "] = " << answer << endl;
	}

	delete[] arr;
}

kissu parina
New poster
Posts: 19
Joined: Thu May 20, 2010 8:58 am

Re: 394 mapmaker RTE??

Post by kissu parina » Thu Feb 10, 2011 11:01 am

i guess ur array size is small.increase the array size
one day...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Problem 394, easy in theory but ...

Post by brianfry713 » Sat Nov 05, 2011 2:06 am

There are no more than 1000 arrays in the test input.
Check input and AC output for thousands of problems on uDebug!

ferlin
New poster
Posts: 1
Joined: Fri Mar 14, 2014 10:26 pm

394- Mapmaker, please help

Post by ferlin » Fri Mar 14, 2014 10:43 pm

Hi,

I am not able to understand how the input translates into output , can someone help with these input ONE[2, 4]=1526, TWO[3, 3, 9] = 2376?

Thanks :).

Sample Input

3 4
ONE 1500 2 2 0 3 1 5
TWO 2000 4 3 1 4 0 5 5 10
THREE 3000 1 1 1 9
ONE 2 4
THREE 7
TWO 2 0 6
TWO 3 3 9

Sample Output

ONE[2, 4] = 1526
THREE[7] = 3006
TWO[2, 0, 6] = 2148
TWO[3, 3, 9] = 2376

Post Reply

Return to “Volume 3 (300-399)”