Adding FractionsProblem code: ADDFRAC |
All submissions for this problem are available.
You have discovered a new way to add fractions ! Now, the result of adding fractions a/b and c/d is (a + c)/(b + d). Similarly the result of adding 3 fractions a/b, c/d, e/f is (a + c + e)/(b + d + f), and so on. You are given a list of N fractions a_1/b_1, a_2/b_2,...,a_N/b_N. You wonder what for each fraction i is the maximum fraction that you can obtain by adding together some continuous fractions in the list (possibly 1) starting at i ?
For example, let N = 4 and the fractions be 1/1, 4/3, 10/1 and 5/4. The maximum fraction you can obtain by starting at index 1 is 3/1 (1/1 + 4/3 + 10/1). Similarly, the maximum fraction you can obtain by starting at index 2 is 7/2 (4/3 + 10/1). By starting at index 3, the maximum sum you can obtain is 10/1 itself, and by starting at index 4, you can obtain sum 5/4.
Input :
The first line contains T the number of test cases. T test cases follow. The first line of each test case contains N. Each of the next N lines contains a fraction given in the form "a_i/b_i". A blank line seperates two test cases.Output :
For each test case, output N lines. The ith line contains the maximum fraction you can obtain by adding continuous fractions in the list starting at index i. The numerator and denominator of any fraction you output should have gcd 1. Output a blank line after each test case.Sample Input :
2 4 1/1 4/3 10/1 5/4 5 1/3 3/1 2/5 5/6 6/5
Sample Output :
3/1 7/2 10/1 5/4 1/1 3/1 13/16 1/1 6/5
Constraints :
1 <= T <= 5 1 <= n <= 100000 1 <= a_k,b_k <= 100000
| Date: | 2010-03-20 |
| Time limit: | 2s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
HELP
Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:
- Accepted
Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark. - Time Limit Exceeded
Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. - Wrong Answer
Your program compiled and ran succesfully but the output did not match the expected output. - Runtime Error
Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section. - Compilation Error
Your code was unable to compile. When you see this icon, click on it for more information.
If you are still having problems, see a sample solution here.
Can some body plz provide
Can some body plz provide trivial test cases...
still getting WA :(
It's pretty easy to generate
It's pretty easy to generate random ones and find out the real answer with a brute force program that checks all possible subsequences. Much more useful than asking others.
@everyone pls point out why
@everyone
pls point out why i am getting WA. i checked my code for several tst cases and got correct answer.
plese find the bug.
#include<stdio.h>
long int gcd(long int a, long int b)
{
if (b==0)
return a;
else
return (long int)gcd(b,a%b);
}
int main()
{
long t,i,j=0,n,temp,ansa,ansb,ans;
double *a,*b,*stacka,*stackb;
char ch[500];
scanf("%ld",&t);
while(t--)
{
scanf("%ld",&n);
a=(double *) malloc(n*sizeof(double));
b=(double *) malloc(n*sizeof(double));
stacka=(double *) malloc(n*sizeof(double));
stackb=(double *) malloc(n*sizeof(double));
for(i=0;i<n;i++)
{
temp=0;
scanf("%s",ch);
j=0;
while(ch[j]!=' ')
{
if(ch[j]!='/')
temp=temp*10+(ch[j]-'0');
else
{
a[i]=temp;
temp=0;
}
j++;
}
b[i]=temp;
temp=0;
}
for(i=n-1;i>=0;i--)
{
stacka[i]=a[i];
stackb[i]=b[i];
j=i+1;
while((float)(stacka[i]/stackb[i])<(float)((a[j])/(b[j]))&&j<n)
{
stacka[i]+=a[j];
stackb[i]+=b[j];
j++;
}
}
for(i=0;i<n;i++)
{
ansa=stacka[i];
ansb=stackb[i];
ans=gcd(ansa,ansb);
stacka[i]=ansa/ans;
stackb[i]=ansb/ans;
printf("%ld/%ldn",ansa/ans,ansb/ans);
}
printf("n");
}
return 0;
}
hi stephen please help me....
hi stephen please help me.... i think u must find out my error......so please help me...
Somebody please help me
Somebody please help me to execute the program within the time limit!!!,here is the code:
public class Main4
{
public static void main(String args[])throws java.lang.Exception
{
java.io.BufferedReader in=new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
int n=Integer.parseInt(in.readLine());
int ar[][][]=new int[n][100001][2];
for(int i=0;i<n;i++)
{
int N=Integer.parseInt(in.readLine());
for(int j=0;j<N;j++)
{
String str=in.readLine();
java.util.StringTokenizer s=new java.util.StringTokenizer(str,"/");
for(int k=1;k<=2;k++)
ar[i][j][k-1]=Integer.parseInt(s.nextToken());
}
ar[i][N][0]=0;
if(i!=(n-1)){
String s=in.readLine();}
//if(s!="")
//break;
}
System.out.println();
for(int a=0;a<n;a++)
{
int l=0;int passar[][]=new int[100001][2];
for(;l<100001;l++){
if(ar[a][l][0]==0)
break;
else{
passar[l][0]=ar[a][l][0];
passar[l][1]=ar[a][l][1];}}
(new Main4()).solve(passar,l);
System.out.println();
}
}
public static int gcd(int a,int b)
{
if(b==0)
return(a);
else
return(gcd(b,a%b));
}
public static void solve(int a[][],int l)
{
for(int i=0;i<l;i++)
{
int s1=0,s2=0;
int m1=a[i][0],m2=a[i][1];
for(int j=i;j<l;j++)
{
s1=s1+a[j][0];
s2=s2+a[j][1];
if((m1*s2)<(m2*s1))
{
m1=s1;
m2=s2;
}
}
int max2=m2,max1=m1;
if(m1>=m2){
max2=m1;max1=m2;}
int t=gcd(max1,max2);
System.out.println((m1/t)+"/"+(m2/t));
}
}
}
could anyone plss explain
could anyone plss explain this problem.............................???
Only one successful solution