394 - Mapmaker

[WR]

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]

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]

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

[Jan]

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

[arh]

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]

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.

[WR]

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]

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]

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]

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]

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]

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]

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

[brianfry713]

There are no more than 1000 arrays in the test input.

[ferlin]

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