Page 1 of 2

Problem 394, easy in theory but ...

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

394 Map Maker WA

Posted: 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 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 ;

}

Dear Have u got some solution for Problem 394

Posted: Wed Sep 22, 2004 2:06 pm
tell me i have same problem Wa have u any clue plz help me

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

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

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

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

Posted: 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->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;
}
}
``````

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

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

Posted: 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

394 mapmaker RTE??

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

``````

394 - Mapmaker

Posted: 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 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;
}
``````

Re: 394 mapmaker RTE??

Posted: Thu Feb 10, 2011 11:01 am
i guess ur array size is small.increase the array size

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

Posted: Sat Nov 05, 2011 2:06 am
There are no more than 1000 arrays in the test input.

Posted: 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