815 - Flooded!

[CDiMa]

Can anyone help me?
the code given below (for 815 in c++) gives me compile error
[cpp]
void main()[/cpp]

c++ expects main to return int. g++ doesn't compile if you don't change the return type of your main function.

[cpp]
double sqr[900],water,dif,under,count,lebel;
[/cpp]

You use count as a subscript for the sqr array so you must declare it as int or cast it to an int when used as a subscript.

Ciao!!!

Claudio

[yiuyuho]

I believe

void main()

is ok for the uva judge. I use it all the time.

[smile2ka10]

there are some I/O that might help...

Input:

• 3 3
  25 37 45
  51 12 34
  94 83 27
  10000
  3 3
  25 37 45
  51 12 34
  94 83 27
  100000
  3 1
  -6
  -5
  -4
  300
  3 1
  -6
  -5
  -4
  301
  3 1
  -6
  -5
  -4
  100
  0 0

Expected Output:

• Region 1
  Water level is 46.67 meters.
  66.67 percent of the region is under water.
  
  Region 2
  Water level is 156.44 meters.
  100.00 percent of the region is under water.
  
  Region 3
  Water level is -4.00 meters.
  66.67 percent of the region is under water.
  
  Region 4
  Water level is -4.00 meters.
  100.00 percent of the region is under water.
  
  Region 5
  Water level is -5.00 meters.
  33.33 percent of the region is under water.

[Darko]

This one has some precision issues - Can't we remove all the cases where Java and C produce different answers?

I just recoded my Java solution in C and got it accepted (after several WAs in Java).

Carlos' comment should probably read "If there is an exact answer of 1.225 you should print 1.22 and not 1.23", because Java will round half up and not half even. I am not sure what Pascal does.
The example given by Carlos is the same in both Java and C (1.235->1.24).

Reminds me of Cows (358). Blah.

[damien_g]

This problem is completely horrible

My code is right on all the input I found (including uDebug), but I keep getting WA for a precision error, even if I'm only using long long!
Can you help me please ?

Here's my code :

Code: Select all

Removed after AC

EDIT:
For those getting WA and using integers, be careful with the roudnings : you need a lot of precision to round well --> integers are in fact impossible to use !

[LoktopicSonarius]

Hello others,

I've been at this problem for hours now. I'm just bloody tired.

I've redone various parts of this code without any success. I'm not sure if there's an error due to the logic or the rounding.

Could anyone please help me? This is seriously frustrating.

The class IOMonster is a quick I/O handler I wrote for these contests. It's actually running fine and without error. All the input is being read normally.

The load method basically calls StringBuilder.append() inside of IOMonster2.

Any questions about my code and I'll answer them. Thank you anyone for your help.

If any of the admins are reading, I beg of you, tell me whether this is a formatting error or a logical one. It would help all too much.

For anyone who wants the Source code to IOMonster2, I can send you the Java file on request.

Code: Select all

package UVA_Online;

import java.io.IOException;
import java.math.BigDecimal;
import java.util.Arrays;

import Tools.IOMonster2;

public class UVA_OnlineJudge_00815
{
	public static boolean debugging = false;

	public static IOMonster2 io;

	public static boolean writtingToFile = false;
	public static String outputURL = "output.txt";
	
	public static int region = 1;
	public static long width, length, waterVolume;
	public static long[] plotHeights, sum;

	public static void main(String[] args) throws IOException {
		io = new IOMonster2(writtingToFile, outputURL, false);

		while((width = io.nextLong()) != 0 && (length = io.nextLong()) != 0)
		{			
			initPlotHeights();
			initSum();
			
			waterVolume = io.nextLong();
			
			float waterLevel = calcWaterLevel();
			String waterLevelString = formatDecimal(waterLevel);
			String regionCovered = formatDecimal(regionCovered(waterLevel));
			
			io.load(String.format("Region %d\n", region++));
			io.load(String.format("Water level is %s meters.\n", waterLevelString));
			io.load(String.format("%s percent of the region is under water.\n\n", regionCovered));
		}

		io.printLoad();
		io.endIO();
	}
	
	public static String formatDecimal(float percent)
	{
		BigDecimal bd = new BigDecimal(Float.toString(percent));
		bd = bd.setScale(2, BigDecimal.ROUND_HALF_EVEN);
		return String.format("%.2f", bd.doubleValue());
	}
	
	public static int plotsCovered(float waterLevel)
	{
		for(int i = plotHeights.length - 1; i >= 0; i--)
		{
			if(plotHeights[i] < waterLevel)
			{
				return i + 1;
			}
		}
		
		return 0;
	}
	
	public static float regionCovered(float waterLevel)
	{
		if(waterLevel >= plotHeights[plotHeights.length - 1])
		{
			return (float) 100.0;
		}
		
		int plots = 0;
		
		for(int i = 0; i < plotHeights.length; i++)
		{
			if(plotHeights[i] <= waterLevel)
			{
				plots++;
			}
			
			if(plotHeights[i] > waterLevel)
			{
				break;
			}
		}
		
		return (float) ((1.0 * (plots) * 100.0) / (plotHeights.length));
	}
	
	public static int numberOfLevels()
	{
		int levels = 1;
		
		for(int i = 1; i < plotHeights.length; i++)
		{
			if(plotHeights[i] != plotHeights[i - 1])
			{
				levels++;
			}
		}
		
		return levels;
	}
	
	public static void initSum()
	{
		sum = new long[numberOfLevels()];
		sum[0] = 0;
		
		int sumIndex = 0;
		long deltaLevel, plotsCovered;
		
		for(int i = 1; i < plotHeights.length; i++)
		{
			if(plotHeights[i] != plotHeights[i - 1])
			{
				sumIndex++;
				
				deltaLevel = plotHeights[i] - plotHeights[i - 1];
				plotsCovered = plotsCovered(plotHeights[i]);
				
				sum[sumIndex] = sum[sumIndex - 1] + (deltaLevel * plotsCovered * 100);
			}
		}
		
		if(debugging)
		{
			io.print("SUM: " + Arrays.toString(sum) + "\n");
		}
	}
	
	public static void initPlotHeights() throws IOException
	{
		plotHeights = new long[(int) (width * length)];
		
		for(int i = 0; i < plotHeights.length; i++)
		{
			plotHeights[i] = io.nextLong();
		}
		
		Arrays.sort(plotHeights);
		
		if(debugging)
		{
			io.print(Arrays.toString(plotHeights) + "\n");
		}
	}
	
	public static float calcWaterLevel()
	{
		if(waterVolume >= sum[sum.length - 1])
		{
			waterVolume -= sum[sum.length - 1];
			
			return (float) (plotHeights[plotHeights.length - 1] + ((float) waterVolume / (100.0 * plotHeights.length)));
		}
		
		int index = 0;
		
		while(sum[index++] <= waterVolume)
		{
			
		}
		
		waterVolume -= sum[--index];
		
		float waterLevel = (float) (getHeightOfLevel(index) + (1.0 * waterVolume / (100.0 * plotsCovered(getHeightOfLevel(index)))));
		
		if(debugging)
		{
			io.print(String.format("Water level (%.2f) passed up to level %d.\n", waterLevel, index));
		}
		
		return waterLevel;
	}
	
	public static long getHeightOfLevel(int level)
	{
		if(level == 1)
		{
			return plotHeights[0];
		}
		
		for(int i = 1; i < plotHeights.length; i++)
		{			
			if(level == 1)
			{
				return plotHeights[i];
			}
			
			if(plotHeights[i] != plotHeights[i - 1])
			{
				level--;
			}
		}
		
		return 0;
	}
}