Unless you are using a very old compiler/computer, int is a 32 bit integer, the range is [-2147483648, 2147483647].
And even if they were 16 bit, the range would be [-32768, 32767]. About the "logn multiplication" I think he meant O(log n) exponentiation. Type "fast exponentiation" in Google, and you should get more information. Carlos Guía On Sat, May 15, 2010 at 5:13 PM, Aamir Khan <[email protected]> wrote: > 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 <[email protected]> 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 <[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 > [email protected]. > > > > > To unsubscribe from this group, send email to> > > > [email protected]<google-code%[email protected]> > <google-code%[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 > [email protected]. > > > > To unsubscribe from this group, send email to> > [email protected]<google-code%[email protected]> > <google-code%[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 > [email protected]. > > > To unsubscribe from this group, send email to> > [email protected]<google-code%[email protected]> > <google-code%[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 > [email protected] unsubscribe from this group, send email > [email protected]<togoogle-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.
