394 - Mapmaker

brianfry713 · Post by **brianfry713** » Mon Mar 17, 2014 9:45 pm

For tnput:

1 14
ONE       1500 2 2 0 3 1 5
ONE       0 1
ONE       0 2
ONE       0 3
ONE       0 4
ONE       0 5
ONE       1 1
ONE       1 2
ONE       1 3
ONE       1 4
ONE       1 5
ONE       2 1
ONE       2 2
ONE       2 3
ONE       2 4

Output should be:

Code: Select all

ONE[0, 1] = 1500
ONE[0, 2] = 1502
ONE[0, 3] = 1504
ONE[0, 4] = 1506
ONE[0, 5] = 1508
ONE[1, 1] = 1510
ONE[1, 2] = 1512
ONE[1, 3] = 1514
ONE[1, 4] = 1516
ONE[1, 5] = 1518
ONE[2, 1] = 1520
ONE[2, 2] = 1522
ONE[2, 3] = 1524
ONE[2, 4] = 1526

uDebug · Post by **uDebug** » Thu Sep 25, 2014 1:17 pm

arh, brianfry713, Jan,

Thanks for the great test cases.

Turns out the judge's input does not have a case like so

Code: Select all

NAME

In other words, each line which defines an array contains the necessary information after the array name. The information is never not present. So, don't sweat that case.

WR wrote:This problem really IS easy to solve

I didn't necessarily find this problem "easy". Yes, it's straightforward once you understand what's being asked. However, the description took me months to unravel. Every time I'd read it, try to work things out by hand and hit a road block. I found this line especially tricky

Code: Select all

 C_d = C_(d+1)(U_(d+1) - L_(d+1) + 1) for 1 <= d < D

I kept thinking that there might be a typo and that it should read

Code: Select all

 C_d = C_(d+1)(U_(d+1) - L_(d+1) + 1) for 1 <= d <= D

instead. However, this isn't the case. The description is accurate as is. After a lot of trying, I finally understood what the problem's stating.

So, in summary, if you're finding it challenging, you're not alone.

garbage · Post by **garbage** » Tue Dec 30, 2014 5:04 pm

#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#define mx 5000
using namespace std;

int main()
{
string S;
long long index, B, D, N, P, R, LU[mx][5], C[mx][12];

while(cin>>N>>R)
{
map<string, long long>myMap;

for(long long i=1;i<=N;i++)
{
cin>>S>>B>>D>>P;

myMap[S] = P;

for(long long j=1;j<=P;j++)
cin>>LU[j][0]>>LU[j][1];

C[myMap[S]][P]=D;

for(long long j=P-1;j>0;j--)
C[myMap[S]][j] = C[myMap[S]][j+1] * (LU[j+1][1] - LU[j+1][0] + 1);

C[myMap[S]][0] = B;

for(long long j=1;j<=P;j++)
C[myMap[S]][0] -= (C[myMap[S]][j]*LU[j][0]);
}

for(long long i=1;i<=R;i++)
{
cin>>S;

long long L = myMap[S];
long long PA = C[myMap[S]][0];

cout<<S<<"[";
for(long long j=1;j<=L; j++)
{
cin>>index;
cout<<index;
if(j!=L)
cout<<", ";
PA += (index*C[myMap[S]][j]);
}
cout<<"] = "<<PA<<endl;
}
}
return 0;
}

lighted · Post by **lighted** » Wed Dec 31, 2014 12:15 pm

Use code tags.

Input

Code: Select all

5 189
HAPPY     1000 4  4   4 8  1 6  2 5  3 4
GO        8000 3  1   1 9
LUCKY     8300 1  2   1 9  2 8
GUY       9000 4  3   4 8  2 9  3 6
RON       1000 1  2   -1 1  -1 1
HAPPY             4 1 2 3
HAPPY             4 1 2 4
HAPPY             4 1 3 3
HAPPY             4 1 3 4
HAPPY             4 1 4 3
HAPPY             4 1 4 4
HAPPY             4 1 5 3
HAPPY             4 1 5 4
HAPPY             4 2 2 3
HAPPY             4 2 2 4
HAPPY             4 2 3 3
HAPPY             4 2 3 4
HAPPY             4 2 4 3
HAPPY             4 2 4 4
HAPPY             4 2 5 3
HAPPY             4 2 5 4
HAPPY             4 3 2 3
HAPPY             4 3 2 4
HAPPY             4 3 3 3
HAPPY             4 3 3 4
HAPPY             4 3 4 3
HAPPY             4 3 4 4
HAPPY             4 3 5 3
HAPPY             4 3 5 4
HAPPY             4 4 2 3
HAPPY             4 4 2 4
HAPPY             4 4 3 3
HAPPY             4 4 3 4
HAPPY             8 3 5 3
HAPPY             8 4 2 3
HAPPY             8 4 2 4
HAPPY             8 4 3 3
HAPPY             8 4 3 4
HAPPY             8 4 4 3
HAPPY             8 4 4 4
HAPPY             8 4 5 3
HAPPY             8 4 5 4
HAPPY             8 5 2 3
HAPPY             8 5 2 4
HAPPY             8 5 3 3
HAPPY             8 5 3 4
HAPPY             8 5 4 3
HAPPY             8 5 4 4
HAPPY             8 5 5 3
HAPPY             8 5 5 4
HAPPY             8 6 2 3
HAPPY             8 6 2 4
HAPPY             8 6 3 3
HAPPY             8 6 3 4
HAPPY             8 6 4 3
HAPPY             8 6 4 4
HAPPY             8 6 5 3
HAPPY             8 6 5 4
LUCKY             3 5
LUCKY             3 6
LUCKY             3 7
LUCKY             3 8
LUCKY             7 2
LUCKY             7 3
LUCKY             7 4
LUCKY             7 5
LUCKY             7 6
LUCKY             7 7
LUCKY             7 8
LUCKY             9 2
LUCKY             9 3
LUCKY             9 4
LUCKY             9 5
LUCKY             9 6
LUCKY             9 7
LUCKY             9 8
GUY               4 2 3
GUY               4 2 4
GUY               4 2 5
GUY               4 2 6
GUY               4 3 3
GUY               4 3 4
GUY               4 3 5
GUY               4 3 6
GUY               4 4 3
HAPPY             4 4 4 3
HAPPY             4 4 4 4
HAPPY             4 4 5 3
HAPPY             4 4 5 4
HAPPY             4 5 2 3
HAPPY             4 5 2 4
HAPPY             4 5 3 3
HAPPY             4 5 3 4
HAPPY             4 5 4 3
HAPPY             4 5 4 4
HAPPY             4 5 5 3
HAPPY             4 5 5 4
HAPPY             4 6 2 3
HAPPY             4 6 2 4
HAPPY             4 6 3 3
HAPPY             4 6 3 4
HAPPY             4 6 4 3
HAPPY             4 6 4 4
HAPPY             4 6 5 3
HAPPY             4 6 5 4
HAPPY             8 3 2 3
HAPPY             8 3 2 4
HAPPY             8 3 3 3
HAPPY             8 3 3 4
HAPPY             8 3 4 3
HAPPY             8 3 4 4
GO                1
GO                2
GO                3
GO                4
GO                5
GO                6
GO                7
GO                8
GO                9
LUCKY             1 2
LUCKY             1 3
LUCKY             1 4
LUCKY             1 5
LUCKY             1 6
LUCKY             1 7
LUCKY             1 8
LUCKY             2 2
LUCKY             2 3
LUCKY             2 4
LUCKY             2 5
LUCKY             2 6
LUCKY             2 7
LUCKY             2 8
LUCKY             3 2
LUCKY             3 3
LUCKY             3 4
GUY               4 4 4
GUY               4 4 5
GUY               4 4 6
GUY               4 5 3
GUY               4 5 4
GUY               4 5 5
GUY               4 5 6
GUY               4 6 3
GUY               4 6 4
GUY               4 6 5
GUY               4 6 6
GUY               4 7 3
GUY               4 7 4
GUY               4 7 5
GUY               4 7 6
GUY               4 8 3
GUY               4 8 4
GUY               4 8 5
GUY               4 8 6
GUY               4 9 3
GUY               4 9 4
GUY               4 9 5
GUY               4 9 6
GUY               8 4 3
GUY               8 4 4
GUY               8 4 5
GUY               8 4 6
GUY               8 5 3
GUY               8 5 4
GUY               8 5 5
GUY               8 5 6
GUY               8 6 3
GUY               8 6 4
GUY               8 6 5
GUY               8 6 6
GUY               8 7 3
GUY               8 7 4
GUY               8 7 5
GUY               8 7 6
GUY               8 8 3
GUY               8 8 4
GUY               8 8 5
GUY               8 8 6
GUY               8 9 3
GUY               8 9 4
GUY               8 9 5
GUY               8 9 6
GUY               8 3 3
RON -1 -1
RON -1 0
RON -1 1
RON 0 -1
RON 0 0
RON 0 1
RON 1 -1
RON 1 0
RON 1 1

Acc Output

Code: Select all

HAPPY[4, 1, 2, 3] = 1000
HAPPY[4, 1, 2, 4] = 1004
HAPPY[4, 1, 3, 3] = 1008
HAPPY[4, 1, 3, 4] = 1012
HAPPY[4, 1, 4, 3] = 1016
HAPPY[4, 1, 4, 4] = 1020
HAPPY[4, 1, 5, 3] = 1024
HAPPY[4, 1, 5, 4] = 1028
HAPPY[4, 2, 2, 3] = 1032
HAPPY[4, 2, 2, 4] = 1036
HAPPY[4, 2, 3, 3] = 1040
HAPPY[4, 2, 3, 4] = 1044
HAPPY[4, 2, 4, 3] = 1048
HAPPY[4, 2, 4, 4] = 1052
HAPPY[4, 2, 5, 3] = 1056
HAPPY[4, 2, 5, 4] = 1060
HAPPY[4, 3, 2, 3] = 1064
HAPPY[4, 3, 2, 4] = 1068
HAPPY[4, 3, 3, 3] = 1072
HAPPY[4, 3, 3, 4] = 1076
HAPPY[4, 3, 4, 3] = 1080
HAPPY[4, 3, 4, 4] = 1084
HAPPY[4, 3, 5, 3] = 1088
HAPPY[4, 3, 5, 4] = 1092
HAPPY[4, 4, 2, 3] = 1096
HAPPY[4, 4, 2, 4] = 1100
HAPPY[4, 4, 3, 3] = 1104
HAPPY[4, 4, 3, 4] = 1108
HAPPY[8, 3, 5, 3] = 1856
HAPPY[8, 4, 2, 3] = 1864
HAPPY[8, 4, 2, 4] = 1868
HAPPY[8, 4, 3, 3] = 1872
HAPPY[8, 4, 3, 4] = 1876
HAPPY[8, 4, 4, 3] = 1880
HAPPY[8, 4, 4, 4] = 1884
HAPPY[8, 4, 5, 3] = 1888
HAPPY[8, 4, 5, 4] = 1892
HAPPY[8, 5, 2, 3] = 1896
HAPPY[8, 5, 2, 4] = 1900
HAPPY[8, 5, 3, 3] = 1904
HAPPY[8, 5, 3, 4] = 1908
HAPPY[8, 5, 4, 3] = 1912
HAPPY[8, 5, 4, 4] = 1916
HAPPY[8, 5, 5, 3] = 1920
HAPPY[8, 5, 5, 4] = 1924
HAPPY[8, 6, 2, 3] = 1928
HAPPY[8, 6, 2, 4] = 1932
HAPPY[8, 6, 3, 3] = 1936
HAPPY[8, 6, 3, 4] = 1940
HAPPY[8, 6, 4, 3] = 1944
HAPPY[8, 6, 4, 4] = 1948
HAPPY[8, 6, 5, 3] = 1952
HAPPY[8, 6, 5, 4] = 1956
LUCKY[3, 5] = 8317
LUCKY[3, 6] = 8318
LUCKY[3, 7] = 8319
LUCKY[3, 8] = 8320
LUCKY[7, 2] = 8342
LUCKY[7, 3] = 8343
LUCKY[7, 4] = 8344
LUCKY[7, 5] = 8345
LUCKY[7, 6] = 8346
LUCKY[7, 7] = 8347
LUCKY[7, 8] = 8348
LUCKY[9, 2] = 8356
LUCKY[9, 3] = 8357
LUCKY[9, 4] = 8358
LUCKY[9, 5] = 8359
LUCKY[9, 6] = 8360
LUCKY[9, 7] = 8361
LUCKY[9, 8] = 8362
GUY[4, 2, 3] = 9000
GUY[4, 2, 4] = 9004
GUY[4, 2, 5] = 9008
GUY[4, 2, 6] = 9012
GUY[4, 3, 3] = 9016
GUY[4, 3, 4] = 9020
GUY[4, 3, 5] = 9024
GUY[4, 3, 6] = 9028
GUY[4, 4, 3] = 9032
HAPPY[4, 4, 4, 3] = 1112
HAPPY[4, 4, 4, 4] = 1116
HAPPY[4, 4, 5, 3] = 1120
HAPPY[4, 4, 5, 4] = 1124
HAPPY[4, 5, 2, 3] = 1128
HAPPY[4, 5, 2, 4] = 1132
HAPPY[4, 5, 3, 3] = 1136
HAPPY[4, 5, 3, 4] = 1140
HAPPY[4, 5, 4, 3] = 1144
HAPPY[4, 5, 4, 4] = 1148
HAPPY[4, 5, 5, 3] = 1152
HAPPY[4, 5, 5, 4] = 1156
HAPPY[4, 6, 2, 3] = 1160
HAPPY[4, 6, 2, 4] = 1164
HAPPY[4, 6, 3, 3] = 1168
HAPPY[4, 6, 3, 4] = 1172
HAPPY[4, 6, 4, 3] = 1176
HAPPY[4, 6, 4, 4] = 1180
HAPPY[4, 6, 5, 3] = 1184
HAPPY[4, 6, 5, 4] = 1188
HAPPY[8, 3, 2, 3] = 1832
HAPPY[8, 3, 2, 4] = 1836
HAPPY[8, 3, 3, 3] = 1840
HAPPY[8, 3, 3, 4] = 1844
HAPPY[8, 3, 4, 3] = 1848
HAPPY[8, 3, 4, 4] = 1852
GO[1] = 8000
GO[2] = 8003
GO[3] = 8006
GO[4] = 8009
GO[5] = 8012
GO[6] = 8015
GO[7] = 8018
GO[8] = 8021
GO[9] = 8024
LUCKY[1, 2] = 8300
LUCKY[1, 3] = 8301
LUCKY[1, 4] = 8302
LUCKY[1, 5] = 8303
LUCKY[1, 6] = 8304
LUCKY[1, 7] = 8305
LUCKY[1, 8] = 8306
LUCKY[2, 2] = 8307
LUCKY[2, 3] = 8308
LUCKY[2, 4] = 8309
LUCKY[2, 5] = 8310
LUCKY[2, 6] = 8311
LUCKY[2, 7] = 8312
LUCKY[2, 8] = 8313
LUCKY[3, 2] = 8314
LUCKY[3, 3] = 8315
LUCKY[3, 4] = 8316
GUY[4, 4, 4] = 9036
GUY[4, 4, 5] = 9040
GUY[4, 4, 6] = 9044
GUY[4, 5, 3] = 9048
GUY[4, 5, 4] = 9052
GUY[4, 5, 5] = 9056
GUY[4, 5, 6] = 9060
GUY[4, 6, 3] = 9064
GUY[4, 6, 4] = 9068
GUY[4, 6, 5] = 9072
GUY[4, 6, 6] = 9076
GUY[4, 7, 3] = 9080
GUY[4, 7, 4] = 9084
GUY[4, 7, 5] = 9088
GUY[4, 7, 6] = 9092
GUY[4, 8, 3] = 9096
GUY[4, 8, 4] = 9100
GUY[4, 8, 5] = 9104
GUY[4, 8, 6] = 9108
GUY[4, 9, 3] = 9112
GUY[4, 9, 4] = 9116
GUY[4, 9, 5] = 9120
GUY[4, 9, 6] = 9124
GUY[8, 4, 3] = 9544
GUY[8, 4, 4] = 9548
GUY[8, 4, 5] = 9552
GUY[8, 4, 6] = 9556
GUY[8, 5, 3] = 9560
GUY[8, 5, 4] = 9564
GUY[8, 5, 5] = 9568
GUY[8, 5, 6] = 9572
GUY[8, 6, 3] = 9576
GUY[8, 6, 4] = 9580
GUY[8, 6, 5] = 9584
GUY[8, 6, 6] = 9588
GUY[8, 7, 3] = 9592
GUY[8, 7, 4] = 9596
GUY[8, 7, 5] = 9600
GUY[8, 7, 6] = 9604
GUY[8, 8, 3] = 9608
GUY[8, 8, 4] = 9612
GUY[8, 8, 5] = 9616
GUY[8, 8, 6] = 9620
GUY[8, 9, 3] = 9624
GUY[8, 9, 4] = 9628
GUY[8, 9, 5] = 9632
GUY[8, 9, 6] = 9636
GUY[8, 3, 3] = 9528
RON[-1, -1] = 1000
RON[-1, 0] = 1001
RON[-1, 1] = 1002
RON[0, -1] = 1003
RON[0, 0] = 1004
RON[0, 1] = 1005
RON[1, -1] = 1006
RON[1, 0] = 1007
RON[1, 1] = 1008

garbage · Post by **garbage** » Sat Jan 03, 2015 5:02 pm

lighted, thnx for the test cases... Got AC...

anacharsis · Post by **anacharsis** » Mon Apr 27, 2015 8:47 pm

This works fine for all of the sample inputs I can find.
It is throwing a runtime exception when I send it to the judge, though.
Anyone have any clue as to why?

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

class Main {

	void solve() throws IOException {
		InputReader reader = new InputReader( System.in );
		int numArrays = reader.nextInt();
		int numArefs = reader.nextInt();
		Map<String, ArrayRef> nameToRef = new HashMap<String, ArrayRef>();

		for ( int i = 0; i < numArrays; ++i ) {
			ArrayRef ref = new ArrayRef( reader.nextName() );
			nameToRef.put( ref.name, ref );

			ref.setBaseAddress( reader.nextInt() );
			ref.setSizeOfEls( reader.nextInt() );
			ref.setDimensions( reader.nextInt() );

			for ( int j = 0; j < ref.dimensions; ++j ) {
				ref.lowerBounds[j] = reader.nextInt();
				ref.upperBounds[j] = reader.nextInt();
			}
		}

		for ( int i = 0; i < numArefs; ++i ) {
			String name = reader.nextName();
			ArrayRef ref = nameToRef.get( name );

			if ( ref == null ) {
				reader.clear();
				continue;
			}

			int[] idx = new int[ ref.getDimensions() ];
			for ( int k = 0; k < idx.length; ++k ) {
				idx[k] = reader.nextInt();
			}

			System.out.println( ref.prettyPrint( ref.getAddress( idx ), idx ) );
		}
	}

	private static class ArrayRef {
		private String name;
		private int baseAddress;
		private int sizeOfEls;
		private int dimensions;
		private int[] upperBounds;
		private int[] lowerBounds;
		private int[] C;

		public ArrayRef( String name ) {
			this.name = name;
		}

		public void setBaseAddress( int baseAddress ) {
			this.baseAddress = baseAddress;
		}

		public void setSizeOfEls( int sizeOfEls ) {
			this.sizeOfEls = sizeOfEls;
		}

		public int getDimensions() {
			return dimensions;
		}

		public void setDimensions( int dimensions ) {
			this.dimensions = dimensions;
			upperBounds = new int[ dimensions ];
			lowerBounds = new int[ dimensions ];
		}

		public String prettyPrint( int address, int[] idx ) {
			StringBuilder buffer = new StringBuilder( 64 );

			buffer.append( name ).append( '[' );
			for ( int i = 0; i < idx.length; ++i ) {
				buffer.append( idx[i] );

				if ( i < idx.length - 1 ) {
					buffer.append( ", " );
				}
			}

			buffer.append( "] = " ).append( address );
			return buffer.toString();
		}

		public int getAddress( int[] idx ) {
			if ( C == null ) {
				calcOffsets();
			}

			int address = C[0];
			for ( int i = 0; i < idx.length; ++i ) {
				address += C[i + 1] * idx[i];
			}

			return address;
		}

		private void calcOffsets() {
			C = new int[ dimensions + 1 ];
			C[dimensions] = sizeOfEls;

			for ( int i = dimensions - 1; i > 0; --i ) {
				C[i] = C[i + 1] * ( upperBounds[i] - lowerBounds[i] + 1 );
			}

			C[0] = baseAddress;
			for ( int i = 0; i < lowerBounds.length; ++i ) {
				C[0] -= C[i + 1] * lowerBounds[i];
			}
		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;
		private String last;

		public InputReader( InputStream stream ) {
			reader = new BufferedReader( new InputStreamReader( stream ) );
			tokenizer = null;
		}

		public void clear() {
			tokenizer = null;
		}

		public String nextName() throws IOException {
			last = readNextNonEmptyLine();
			tokenizer = new StringTokenizer( last.substring( 10 ) );

			return last.substring( 0, 10 ).trim();
		}

		private String readNextNonEmptyLine() throws IOException {
			String input = reader.readLine();

			while ( input.trim().isEmpty() ) {
				input = reader.readLine();
			}

			return input;
		}

		public String next() {
			while ( tokenizer == null || !tokenizer.hasMoreTokens() ) {
				try {
					tokenizer = new StringTokenizer( reader.readLine() );
				} catch ( Throwable e ) {
					return null;
				}
			}

			return tokenizer.nextToken();
		}

		public int nextInt() {
			String next = next();

			if ( next == null ) {
				return -1;
			}

			return Integer.parseInt( next );
		}

		public static void main( String args[] ) {
			Main solver = new Main();

			try {
				solver.solve();
			} catch ( Throwable t ) {
				t.printStackTrace();
			}
		}
	}
}

javpaw · Post by **javpaw** » Sun Jan 31, 2016 4:14 pm

Hi.

Why the constants (C) in this problem can be stored as integers (int in c++) when for a lot of cases this type is not enough?

I really don't get it, please help me, where in the problem is specified that overflow of int is allowed?

think for example in this entry:

1 1
A 0 1 10 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000
A 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000

C10 = 1
C9 = 1*1M
C8 = 1M*1M
C7 = 1M*1M*1M
....

C1 in this case should be a really big number (10^6)^9 = 10^54, between 1^179 and 2^180

lighted · Post by **lighted** » Sat Jul 15, 2017 2:43 pm

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

Number of arrays is not more than 5.

OJ Board

394 - Mapmaker

Re: 394- Mapmaker, please help

Re: 394 - Mapmaker

Re: 394 - Mapmaker, Getting WA

Re: 394 - Mapmaker

Re: 394 - Mapmaker

Re: 394 - Mapmaker

Re: 394 - OMG what about integer overflow?

Re: 394 - Mapmaker