You should take care about (long int) cast, because in c++ most compilers
uses the int precision the same as long int precision (32 bits), if you need
more you should use (long long int).
Also using the function pow to exponentiate integers is a very bad ideia. It
first change it to double, use some expensive routines, return a double and
then you cast back to integer, what can cause lots of precision problems and
lost of speed.
In the specific case of base 2 just shift the bits, like
2^0 = 1<<0 = 1b = 1
2^1 = 1<<1 = 10b = 2
2^2 = 1<<2 = 100b = 4
.
.
.
In other situations you should check this recurrence relation
[image: x^n= \begin{cases} 1, & \mbox{if } n = 0 \\ x \cdot \left(
x^{\frac{n-1}{2}} \right)^2, & \mbox{if } n \mbox { is odd} \\ \left(
x^{\frac{n}{2}} \right)^2, & \mbox{if }n\mbox{ is even} \end{cases}]
to use logn multiplications.
On Sat, May 15, 2010 at 3:15 PM, tonka <[email protected]> wrote:
> why the heck will you write such a clumsy and lengthy code??? take a
> look at my code:
> #include<iostream.h>
> #include<fstream.h>
> #include<conio.h>
> #include<math.h>
> #include<stdio.h>
> #include<string.h>
>
> void main()
> {
> int t,flag=0,n;
> long int k;
> ifstream fi("A-large.in",ios::binary|ios::in);
> ofstream fo("outputlar.out",ios::out);
> fi>>t;
> for(int t_c=0;t_c<t;t_c++)
> {
> fi>>n>>k;
> if(((k+1)%(long int)pow(2,n))==0)
> fo<<"Case #"<<(t_c+1)<<": "<<"ON"<<endl;
> else
> fo<<"Case #"<<(t_c+1)<<": "<<"OFF"<<endl;
> }
> fi.close();
> fo.close();
> getch();
> }
>
> This works for the large input also.
>
>
> On May 14, 7:49 pm, Bharath Raghavendran <[email protected]> wrote:
> > I found one mistake : If b < PD, you are returning 0. Why is that?
> > Lets say you have 4 switches, PD = 16. If b = 15, the answer should be
> ON.
> >
> > Other than that, there are many ways you can improve your code.
> > 1.
> > dont use double. It will remove accuracy in many places. 10^8 will come
> > within 4 bytes (usually int suffices this. else use long int).
> >
> > 2.
> > To calculate 2^n, you can use the left shift operator. "int PD = 1<<n"
> will
> > put 2^n into PD.
> >
> > 3.
> > To check if b gives reminder PD -1, you don't need to run a loop. You can
> do
> > "if (b%PD == PD-1)"
> >
> > On 13 May 2010 10:47, Aamir Khan <[email protected]> wrote:
> >
> >
> >
> >
> >
> > > #include <cmath>
> > > #include <cstdio>
> > > #include <iostream>
> > > using namespace std;
> >
> > > #define _CRT_SECURE_NO_WARNINGS
> > > #define For(i,a,b) for (long i(a),_b(b); i <= _b; ++i)
> >
> > > char buf[1024*1024];
> >
> > > bool isEven(long a,long b)
> > > { bool result=0;
> > > if(b%2==0)
> > > result=0;
> > > else
> > > {
> > > double ad=0.00;
> > > for(int j=0;j<=30;j++)
> > > {
> > > if(int(ad)==a)
> > > { break;}
> > > ad=ad+1.00;
> > > }
> > > long PD=long(pow(2.00,ad));
> > > if(b<PD)
> > > result=0;
> >
> > > else
> > > {
> > > for(long i=PD;i<=100000000;i+=PD)
> > > {
> > > if(b==i-1)
> > > {
> > > result=1;
> > > break;
> > > }
> > > }
> > > }
> > > }
> > > return result;
> > > }
> >
> > > int main() {
> > > freopen("A-large.in", "rt", stdin);
> > > freopen("output_Snapper_Chain.txt", "wt", stdout);
> >
> > > gets(buf);
> > > long size=atoi(buf);
> >
> > > For(test, 1, size)
> > > {
> > > // cout<<"No. of loops"<<test;
> > > long N;
> > > long K;
> >
> > > scanf("%d%d", &N, &K);
> > > // cout<<"N"<<N<<"K"<<K;
> >
> > > bool res=isEven(N,K);
> > > if(res)
> > > printf("Case #%d: ON\n", test);
> > > else
> > > printf("Case #%d: OFF\n", test);
> > > }
> > > exit(0);
> > > }
> >
> > >
> ---------------------------------------------------------------------------
> ------------------------------------------------
> > > SNAPPER CHAIN:
> > > Can anybody tell me the errors in the code.....i have done this
> > > problem using the simple concept which i know....it is not giving
> > > right output....
> >
> > > Brief explanation of code:
> > > i have first converted the long taken from file into the double using
> > > for loop..then using pow function i have found 2^N and then found
> > > whether k==2^N-1;
> >
> > > _____
> > > Aamir
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "google-codejam" group.
> > > To post to this group, send email to [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected]<google-code%[email protected]>
> <google-code%2bunsubscr...@googlegr oups.com>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/google-code?hl=en.
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> "google-codejam" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> [email protected]<google-code%[email protected]>
> .
> > For more options, visit this group athttp://
> groups.google.com/group/google-code?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "google-codejam" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<google-code%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/google-code?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
