10994 - Simple Addition

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

Moderator: Board moderators

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

Post by Ankur Jaiswal » Sat Apr 01, 2006 4:10 pm

i got a direct formula for the second grp numbers (i.e the numbers not ending in 0) but i am not able to get the formula for the numbers ending in 0...So, i got TLE.
my output is correct.
i am using following code for the numbers ending in 0 -

Code: Select all

for(i=temp;i<=q;i+=10){
                        p=i;
                        while(p%10==0)
                                p/=10;
                        ans+=p%10;
                }

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Sun Apr 09, 2006 5:42 pm

U can modify the formula as follows:

function()
{

............
............
while(n)
{
m = n%10;
n = n/10;
s1 += ( ( m * (m+1) ) / 2 );
s2 += (double)n * 45;

}


return (s1 + s2);

}
-------------------------------------
When u call the function

just
if(p)
sum = function(q)-function(p-1)
else
sum = function(q)


Hope TLE will mitigate..... this time :wink:

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

Post by Ankur Jaiswal » Wed May 03, 2006 11:44 am

Thanx a lot for providing such a simple alternative but now i am getting WA :(

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Aug 05, 2006 7:07 am

Ankur Jaiswal wrote:Thanx a lot for providing such a simple alternative but now i am getting WA :(
Try these test cases:

Code: Select all

0 0
0 1
0 2
0 3
1 1
1 2
1 3
2 2
2 3
3 3
0 2147483647
4868141 2147483647
2147483646 2147483647
2147483647 2147483647
0 1697831704
1 1697831704
5874571 5874571
8547855 8547856
100580521 1989930148
155996425 1206496545
147550223 1536716708
707325775 1340801806
1040075891 1420810599
1714064943 1984493018
686413674 1329025269
736919653 1524063966
71724731 579366154
166786016 735362579
1002657859 1541865667
784743773 2037402352
-7 -7
My AC's output:

Code: Select all

0
1
3
6
1
3
6
2
5
3
10737418158
10713077499
13
7
8489158466
8489158466
1
11
9446748140
5252500596
6945832429
3167380180
1903673541
1352140396
3213057997
3935721558
2538207103
2842882808
2696039024
6263292902

User avatar
Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

Post by Spykaj » Sat Oct 07, 2006 3:21 pm

Thanks, good tests ;] i have acc.

kintu
New poster
Posts: 6
Joined: Sun Mar 18, 2007 11:31 am
Location: In home

Why CE????

Post by kintu » Wed Jun 27, 2007 8:41 am

/* Remove Whole Messege as no help come */
Last edited by kintu on Thu Jun 28, 2007 1:56 pm, edited 1 time in total.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Re: Why CE????

Post by little joey » Wed Jun 27, 2007 12:42 pm

kintu wrote: But what hell happen to Online Judge.
Well, not very much lately...

About your problem: untyped numeric constants, consisting of digits only, are translated by the compiler in to integers, which have a range [-2^31..2^31>. The number 4.5 billion is outside this range, so it issues an error.

Add a type to the constant by using the proper suffix, and it will be fine. "4500000000ll" will do.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

kintu
New poster
Posts: 6
Joined: Sun Mar 18, 2007 11:31 am
Location: In home

Post by kintu » Wed Jun 27, 2007 2:45 pm

well, as i know befire that long long type integer have a range= 2^64
Which is in the range of 4.5billion
So, what type problem has occured here, i can't understand.
And by-
Add a type to the constant by using the proper suffix, and it will be fine. "4500000000ll" will do.
what you want to do, i can't understand. Please can you explain where to modify my code???

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

Post by annhy » Thu Jun 28, 2007 12:23 pm

Martin Macko wrote:Try these test cases:

Code: Select all

0 0
0 1
0 2
0 3
1 1
1 2
1 3
2 2
2 3
3 3
0 2147483647
4868141 2147483647
2147483646 2147483647
2147483647 2147483647
0 1697831704
1 1697831704
5874571 5874571
8547855 8547856
100580521 1989930148
155996425 1206496545
147550223 1536716708
707325775 1340801806
1040075891 1420810599
1714064943 1984493018
686413674 1329025269
736919653 1524063966
71724731 579366154
166786016 735362579
1002657859 1541865667
784743773 2037402352
-7 -7
My AC's output:

Code: Select all

0
1
3
6
1
3
6
2
5
3
10737418158
10713077499
13
7
8489158466
8489158466
1
11
9446748140
5252500596
6945832429
3167380180
1903673541
1352140396
3213057997
3935721558
2538207103
2842882808
2696039024
6263292902
Thanks Macko, I got AC. :D

For someone still getting WA: note the overflowing cases!!

hosnayen
New poster
Posts: 4
Joined: Mon Dec 28, 2009 8:41 pm

Re: 10994 Compile Error

Post by hosnayen » Wed Sep 01, 2010 8:54 pm

Can any1 help me ... :( where is my fault.. it seems to be ok.. or give me some critical input..
here is my code... thanks in advance :)

Code: Select all

/*
	Author : Hosnayen Alam Siddiquee.
	University of Science & Technology Chittagong (USTC)
	CSE- 11th Batch
	E-mail: hosnayen_alam@yahoo.com
	Bangladesh	                          Date:	02/08/2010
*/

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>                     // n(n+1)/2
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>

using namespace std;

int main(){

 long long p,q;
 long long ans1,ans2;

 while(scanf("%lld%lld",&p,&q)==2){

  if(p < 0 && q < 0) break;

  p=p-1;
  
  ans1=0,ans2=0;

  ans1=(p/10)*45 + (p%10)*(p%10+1)/2  + (p/10)*(p/10+1)/2;

  ans2=(q/10)*45 + (q%10)*(q%10+1)/2  + (q/10)*(q/10+1)/2;


  printf("%lld\n",ans2 - ans1);

   
 }
 return 0;
}

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 10994 Compile Error

Post by sazzadcsedu » Thu Sep 02, 2010 3:13 pm

Do you think your algorithm is right??.I don't know how did you derive this formula.Your formula
is not correct.try this

Code: Select all

input:
100 123
122 1112
-1 -1

Actual output:
100
4951

your output:
129
10595

And this problem is in volume CIX, not in volume I.So use volume CIX.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re:

Post by DD » Wed Mar 16, 2011 12:17 am

Martin Macko wrote:
Ankur Jaiswal wrote:Thanx a lot for providing such a simple alternative but now i am getting WA :(
Try these test cases:

Code: Select all

0 0
0 1
0 2
0 3
1 1
1 2
1 3
2 2
2 3
3 3
0 2147483647
4868141 2147483647
2147483646 2147483647
2147483647 2147483647
0 1697831704
1 1697831704
5874571 5874571
8547855 8547856
100580521 1989930148
155996425 1206496545
147550223 1536716708
707325775 1340801806
1040075891 1420810599
1714064943 1984493018
686413674 1329025269
736919653 1524063966
71724731 579366154
166786016 735362579
1002657859 1541865667
784743773 2037402352
-7 -7
My AC's output:

Code: Select all

0
1
3
6
1
3
6
2
5
3
10737418158
10713077499
13
7
8489158466
8489158466
1
11
9446748140
5252500596
6945832429
3167380180
1903673541
1352140396
3213057997
3935721558
2538207103
2842882808
2696039024
6263292902
Thanks for your test case, I got some bugs from my program by this.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

dotnet12
New poster
Posts: 4
Joined: Fri Aug 17, 2012 9:43 pm

#10994- Need help

Post by dotnet12 » Fri Aug 17, 2012 9:49 pm

The solution is correct but it exceeds time limit so what can I do about it? :( :( Please tell me anyone. Here is my solution:



#include <stdio.h>

int fu(int ab)
{

if(ab%10>0 && ab>0)
{
return ab%10;
}
else
{
return ab/10;
}
}

int S(int a,int b)
{
int ans=0,i;
for(i=a;i<=b;i++)
{
ans+=fu(i);

}
printf("%d", ans);
return 0;
}


int main()
{
int in1,in2,ans;
while((scanf("%d %d",&in1,&in2)==2) && (in1!=-1 && in2!=-1))
{

if(in1>in2)
{
S(in2,in1);

}
else
{
S(in1,in2);

}

}
return 0;


}

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

Re: #10994- Need help

Post by brianfry713 » Sat Aug 18, 2012 1:29 am

Brute force won't work here, you'll need to come up with a faster solution.
Check input and AC output for thousands of problems on uDebug!

dotnet12
New poster
Posts: 4
Joined: Fri Aug 17, 2012 9:43 pm

Re: #10994- Need help

Post by dotnet12 » Sat Aug 18, 2012 3:10 am

can u give 1? :D :D

Post Reply

Return to “Volume 109 (10900-10999)”