10375 - Choose and divide

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

Moderator: Board moderators

vardiar
New poster
Posts: 2
Joined: Tue Oct 04, 2005 5:46 pm
Contact:

10375

Post by vardiar » Tue Oct 04, 2005 5:51 pm

wht is wrong about this code to GET 25 WA????
//10375
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
void main()
{
long long m1,n1,m2,n2;
while(cin>>m1>>n1>>m2>>n2)
{
long long c1=m1-n1;
long long c2=m2-n2;
vector<long long>s;
vector<long long>m;
s.push_back(m1);
s.push_back(c2);
s.push_back(n2);
m.push_back(m2);
m.push_back(c1);
m.push_back(n1);
sort(s.begin(),s.end());
sort(m.begin(),m.end());
long long sj[3];
sj[0]=s[0];
sj[1]=s[1];
sj[2]=s[2];
long long mj[3];
mj[0]=m[0];
mj[1]=m[1];
mj[2]=m[2];
vector<long double> so;
for(long long i=s[0];i>m[0];i--)
{
so.push_back(i);
}
for(long long i=s[1];i>m[1];i--)
{
so.push_back(i);
}
for(long long i=s[2];i>m[2];i--)
{
so.push_back(i);
}
vector<long double> ma;
for(long long i=m[0];i>s[0];i--)
{
ma.push_back(i);
}
for(long long i=m[1];i>s[1];i--)
{
ma.push_back(i);
}
for(long long i=m[2];i>s[2];i--)
{
ma.push_back(i);
}
long double sorat=1;
int v=0;
for(int i=0;i<so.size();i++)
{
sorat*=so;
if(sorat>ma[v] && v<ma.size())
{
sorat/=ma[v];
v++;
}
}
for(int i=v;i<ma.size();i++)
{
sorat/=ma;
}
printf("%.5lf\n",sorat);
}
}

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Log is possible

Post by mpi » Mon Mar 10, 2008 12:18 am

This problem can be solved using log and long double

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10375 - Choose and Divide

Post by stcheung » Wed Jan 07, 2009 7:01 am

If you are using Java and keep getting WA, you might want to try using C/C++. At first I converted the program in the 1st thread into a Java program. I also took the suggestion in the 2nd thread and converted the 6 loops into a single loop. However that got me WA whether I use Math.log10 or Math.log. Then I tried implementing the exact same thing in C++ and got AC.

tkcn
New poster
Posts: 5
Joined: Wed Apr 02, 2008 3:42 pm

Re: 10375 - Choose and Divide

Post by tkcn » Fri May 28, 2010 4:38 pm

stcheung wrote:If you are using Java and keep getting WA, you might want to try using C/C++. At first I converted the program in the 1st thread into a Java program. I also took the suggestion in the 2nd thread and converted the 6 loops into a single loop. However that got me WA whether I use Math.log10 or Math.log. Then I tried implementing the exact same thing in C++ and got AC.
Hello.
I was trying to solving this problem using Java.
It's just like stcheung said, I jsut got WA.
Finally I try to using BigDecimal and got AC.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10375 - Choose and Divide

Post by plamplam » Thu Jul 14, 2011 7:32 pm

First of all, you can't get AC with double. You must use long double to get Accepted and remember you can't use log or ln for this problem as this would cause precision error. (May be it is possible to solve this using log or ln by adding/subtracting or looping less, but I wouldn't recommend using it).
Some test cases in case you get stuck:

Code: Select all

9999 5000 9999 5256
1271 18 1922 18
156 45 156 46
5600 2800 5595 2795
9191 19 9189 19
9876 1234 9899 1222

Code: Select all

521350.34067
0.00056
0.41441
32.05724
1.00415
713086555.90808
Cheers :)
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

AbyssalGreed
New poster
Posts: 9
Joined: Mon Aug 25, 2014 5:25 am

Re: 10375 - Choose and Divide

Post by AbyssalGreed » Wed Sep 03, 2014 10:08 am

Code: Select all

import java.io.*;
import java.lang.*;
import java.math.*;
import java.util.*;
import java.text.*;

class Main
{
	public static void main(String args[])throws Exception
	{
		Scanner sc = new Scanner(new File("input.txt"));
		DecimalFormat df = new DecimalFormat("0.00000");
		while(sc.hasNext())
		{
			
			long num1 = sc.nextLong();
			long num2 = sc.nextLong();
			long num3 = sc.nextLong();
			long num4 = sc.nextLong();
			
			BigDecimal fact1 = new BigDecimal("1");
			for(int a=1; a<=num1; a++)
			{
				fact1 = fact1.multiply(BigDecimal.valueOf(a));
			}
		
			BigDecimal fact2 = new BigDecimal("1");
			for(int a=1; a<=num2; a++)
			{
				fact2 = fact2.multiply(BigDecimal.valueOf(a));
			}
		
			BigDecimal fact3 = new BigDecimal("1");
			for(int a=1; a<=num3; a++)
			{
				fact3 = fact3.multiply(BigDecimal.valueOf(a));
			}
		
			BigDecimal fact4 = new BigDecimal("1");
			for(int a=1; a<=num4; a++)
			{
				fact4 = fact4.multiply(BigDecimal.valueOf(a));
			}
			
			long difnum1num2 = num1-num2;
			BigDecimal difnum1 = new BigDecimal("1");
			for(int a=1; a<=difnum1num2; a++)
			{
				difnum1 = difnum1.multiply(BigDecimal.valueOf(a));
			}
			
			long difnum3num4 = num3-num4;
			BigDecimal difnum2 = new BigDecimal("1");
			for(int a=1; a<=difnum3num4; a++)
			{
				difnum2 = difnum2.multiply(BigDecimal.valueOf(a));
			}
			
			BigDecimal num = factor1(fact1,fact2,difnum1);
			BigDecimal den = factor2(fact3,fact4,difnum2);
			BigDecimal qou = num.divide(den, 20, RoundingMode.CEILING);
			if(qou.compareTo(BigDecimal.valueOf(0.00000000000000000001))==0)
				System.out.println(df.format(qou));
			else
				System.out.println(String.format("%.5f",qou));
		
		}	
	}	
	
	static BigDecimal factor1(BigDecimal fact1, BigDecimal fact2, BigDecimal difnum1)
	{
		BigDecimal _fact1 = new BigDecimal("1");
		_fact1 = fact1.divide(fact2.multiply(difnum1), 10, RoundingMode.CEILING);
		return _fact1;
		
	}
	static BigDecimal factor2(BigDecimal fact3, BigDecimal fact4, BigDecimal difnum2)
	{
		BigDecimal _fact2 = new BigDecimal("1");
		_fact2 = fact3.divide(fact4.multiply(difnum2), 10, RoundingMode.CEILING);
		return _fact2;
	}	
}

here's my code.. and i don't know this is TLE.. I tried to compile and runs in 1.120 sec, but submitting it in UVA OJ gives me TLE..
can anybody help??

thanks in advance!!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10375 - Choose and Divide

Post by brianfry713 » Wed Sep 03, 2014 6:59 pm

Don't read from a file.
Check input and AC output for thousands of problems on uDebug!

AbyssalGreed
New poster
Posts: 9
Joined: Mon Aug 25, 2014 5:25 am

Re: 10375 - Choose and Divide

Post by AbyssalGreed » Thu Sep 04, 2014 1:45 am

I've change it to System.in before submiiting.. it's still TLE.. hehe!! oopss! sorry if I forgot to change that in my code!!! my faullt!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10375 - Choose and Divide

Post by brianfry713 » Thu Sep 04, 2014 7:31 pm

Next time post the code you'd actually submit.
Try using BufferedReader and BufferedWriter.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 103 (10300-10399)”