SPOJ.com - Problem UOFTAB

UOFTAB - The Foxens Treasure

#ad-hoc-1

Marlin engaged Dory, last April and they decided to marry in next November. Unfortunately, Dory is not like normal girls who their dowry is money, rings or furniture! She has many pictures of fishes and she wants a program that draws boxes around the fishes in the images. Time is passing and Marlin’s program just process the image and output some data that could be used to find the correct locations of these boxes. Please help him to save his marriage dream.

Marlin outputs for every image:

2 integers H and K.
A 2D matrix M of integer values from 1 to K.
T integer vectors V_i, each of length K. Each vector is coupled with an integer value X_i.

A Score Evaluator function is used to calculate the score of any box in the image, such that the higher box score, the more confidence in the box to tightly contain a fish. Hence, Marlin targets the box with the highest score that contains a fish.

Given 4 corners of box B, the function works as following:

Construct vector V that has the frequencies of the values in M corresponding to B.
Calculate the score as: Score = H + $\sum_{1}^{T}[X_i * (V.V_i)]$, where (a.b) means the dot product.

Input

The first line of input contains an integer S that represents the number of test cases, then S test cases follow. Each test case start with a line of 5 numbers R C H K T, where R and C are number of rows and columns for the matrix. K, T and H are as described in the problem. R lines follow each with C numbers corresponding to the matrix. Then T lines for the vectors follow each line starts with X of that vector, then K numbers of the vector.

1 ≤ R, C, H ≤ 100, 1 ≤ K ≤ 500, 0 ≤ T ≤ 500, 0 ≤ G ≤ 100 and -5 ≤ X ≤ 5. G is the range of values for vectors V_i.

Output

For each test case, output on a single line “Case #K:” where K is the number of the test case, followed by a single integer which is the score of the box with highest to have a fish.

Example

Input:
1
3 4 7 3 2
1 1 2 2
1 2 2 3
2 3 1 3
-3 1 1 2
4 7 2 10

Output:
Case #1:
234

Explanation:

Let's evaluate the first 2x2 box which is:

1 1
1 2

1 occurred 3 times, 2 occurred 1 time and 3 occurred 0 times.

Then the frequencies vector is [3 1 0] and its function evaluation is:

7 + (- 3 * ([3 1 0]. [1 1 2]) + 4 * ([3 1 0].[7 2 10]) ) = 7 + (-12 + 92) = 87

Submit solution!

hide comments

< Previous 1 2 Next >

	zxcghoul2009: 2023-10-31 22:36:52 I have different description for this task. Input The first line of input contains an integer S that represents the number of test cases, then S test cases follow. Each test case start with a line of 5 numbers R C H K T, where R and C are number of rows and columns for the matrix. K, T and H are as described in the problem. R lines follow each with C numbers corresponding to the matrix. Then T lines for the vectors follow each line starts with X of that vector, then K numbers of the vector. 1 ≤ R, C, H ≤ 100, 1 ≤ K ≤ 500, 0 ≤ T ≤ 500, 0 ≤ G ≤ 100 and -5 ≤ X ≤ 5. G is the range of values for vectors Vi. Output For each test case, output on a single line “Case #K:” where K is the number of the test case, followed by a single integer which is the score of the box with highest to have a fish.
	kumar_anubhav: 2020-06-08 09:30:38 What is the meaning of - "At the start of your treasure-nabbing attempt, the ith Fox is exactly Oi (0 <= Oi < Ai + Si) hours into its cycle". I am not able to understand please help me so that I can better understand the problem.
	malcolm_123ssj: 2020-05-16 07:41:02 There are N (1 <= N <= 4) Foxen guarding a certain valuable treasure, which you'd love to get your hands on. The problem is, the Foxen certainly aren't about to allow that - at least, not while they're awake. Fortunately, through careful observation, you've seen that each Fox has a regular sleep cycle. In particular, the ith Fox stays awake for Ai (1 <= Ai <= 23) hours, then sleeps for Si (1 <= Si <= 23) hours, repeating this pattern indefinitely (2 <= Ai + Si <= 24) . At the start of your treasure-nabbing attempt, the ith Fox is exactly Oi (0 <= Oi < Ai + Si) hours into its cycle. There are T (1 <= T <= 20) scenarios as described above. For each one, you'd like to determine how soon all of the Foxen will be simultaneously asleep, allowing you to grab their treasure, or if this will simply never happen. Input First line: 1 integer, T For each scenario: First line: 1 integer, N Next N lines: 3 integers, Ai, Si, and Oi, for i = 1..N Output For each scenario: 1 integer, the minimum number of hours after the start to wait until all of the Foxen are asleep during the same hour. If this will never happen, output the string "Foxen are too powerful" (without quotes) instead. Made it easy for your eyes to see and your brain to think. Last edit: 2020-05-16 07:44:27
	darker__space: 2019-12-22 16:16:15 i was getting wrong answer just becoz i was printing "endl/ \n"at last case....what d freAK
	sayan_244: 2019-12-17 11:38:40 Allow scripts to load for the math formats. You can check it from the Address bar
	jprm2: 2019-10-09 14:13:34 POOR FORMATTING OF THE QUESTION NOT CLEARLY UNDERSTANDABLE
	aryan29: 2019-06-03 12:40:31 I dont know why only this question is not opening properly in my browse
	nadstratosfer: 2017-12-25 05:46:26 Spent a little while breaking it down, then just coded what I had figured out - worked on the first try. I love when this happens, and such problems tend to inspire elegant solutions also.
	vengatesh15: 2017-03-04 18:16:14 Really Foxens are too powerful...
	raghav12345: 2016-01-30 11:10:37 ac in 1 go :) simply apply same method given in explaining

Submit solution!

Added by:	SourSpinach
Date:	2013-05-17
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own problem, used in the 2012 UofT ACM Tryouts