the information given by you is good......but in other situations the
text written by you is not so much clear....could you please clearly
post it.....what is "to use logn multiplications"....
Thanks for help
On May 15, 11:50 pm, Davi Costa <daf...@gmail.com> wrote:
> 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 <ritwik.sami1...@gmail.com> 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 <rbharat...@gmail.com> 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 <aamir.cod...@gmail.com> 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
> > > > togoogle-c...@googlegroups.com.
> > > > To unsubscribe from this group, send email to> >
> > > > >google-code+unsubscr...@googlegroups.com<google-code%2bunsubscr...@googlegroups.com>
> > <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
> > togoogle-c...@googlegroups.com.
> > > To unsubscribe from this group, send email
> > > to>google-code+unsubscr...@googlegroups.com<google-code%2bunsubscr...@googlegroups.com>
> > .
> > > 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
> > togoogle-c...@googlegroups.com.
> > To unsubscribe from this group, send email
> > to>google-code+unsubscr...@googlegroups.com<google-code%2bunsubscr...@googlegroups.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
> togoogle-c...@googlegroups.com.to unsubscribe from this group, send email
> togoogle-code+unsubscr...@googlegroups.com.
> 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 google-c...@googlegroups.com.
To unsubscribe from this group, send email to
google-code+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
