## 394 - Mapmaker

Moderator: Board moderators

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

### Problem 394, easy in theory but ...

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

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 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++)
{
}

}
}

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]; ///////
}

}

}

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

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
Contact:
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
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
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
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
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->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))
{
}
else
{
}
}
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.. ;

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
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??

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
setlength(data, n);
for i:= 0 to n-1 do begin
setlength(data[i].nama, 10);
for j:= 1 to 10 do begin
end;
for j:= 1 to data[i].dim do begin
end;
end;

for i:= 1 to p do begin
setlength(nama, 10);
for j:= 1 to 10 do begin
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
end;

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

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 tmpI[11];

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

for(int j=1; j<=arr[i].D; j++)
{
cin >> 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??

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 ...

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

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