815 - Flooded!

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: 815 compile error

Post by CDiMa » Tue Sep 07, 2004 9:48 am

Gazi Shaheen Hossain wrote: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.
Gazi Shaheen Hossain wrote:[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
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sat Sep 18, 2004 3:52 am

I believe

void main()

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

smile2ka10
New poster
Posts: 13
Joined: Wed Oct 26, 2005 10:14 pm
Location: Iran
Contact:

Post by smile2ka10 » Thu Nov 03, 2005 2:16 am

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Re: 815 - Flooded!

Post by Darko » Thu Feb 28, 2013 9:11 pm

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
New poster
Posts: 8
Joined: Sun Oct 05, 2014 5:53 pm

Re: 815 - Flooded!

Post by damien_g » Mon Jun 29, 2015 4:22 pm

This problem is completely horrible :evil:

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
New poster
Posts: 1
Joined: Sun Jul 05, 2015 7:38 am

Re: 815 - Flooded!

Post by LoktopicSonarius » Sun Jul 05, 2015 7:55 am

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

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;
	}
}

Post Reply

Return to “Volume 8 (800-899)”