Take a look at the numbers 11010010001 "1".So we have 1 at
position 1,2,4,7,and so on and because every time one 0 is addesd this numbers increses like sum of the numbers from 1,2,3,4,..+n  +1; so sum of this sequance 1+2+3+...n=n(n+1)/2. And look at our sequence  2+4+7+...n=n(n+1);
And from here you can get this formula (sqrt(8*n-7)-1)/2




Edited by author 10.08.2009 16:54

Excuse me.. But how could you found out that formula?

Thank you very much!I got AC!

Excuse me, but how sum of (1+2+3+...+n) can be less than (2+4+7+...+n)?

Excuse me, but how I can use your formula?

I have another way to explain this. That's not a correct one, but I got A anyway:
The indexes of the "1" are 1,2,4,7,11,..., which are 1+(0), 1+(1), 1+(1+2), 1+(1+2+3), ... , 1+((k+1)*k/2), ...
Those are "partial sums" of the sequence (1,2,3,4,5,...,k,...)
We have an input index N and we are not sure, if there is some X for which N == 1+((X+1)*X/2).
You'll have to find this X via some arithmetical operations (you can even ignore some numbers in formulas). As if X is an index in the sequence (1,2,3,4,5,...,k,...), you should find out, if it is an Integer number. Too many info, i think.

just use this logic
if
(Math.sqrt((8*(num))-7)-1)/2))%1==0
print "1"
else
print "0"

and watch the range of the input ;D

please help me, Me programm 3 test time limit exceeded..
Program is this

package acm.timus.ru;

import java.util.Scanner;

public class N_1209 {
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int i=1,a=0,k=0;
    for (int j=1; j<=n; j++) {
       a=sc.nextInt();
       if (i<a) {
           while(i<a){ k++; i+=k; }
       }else{
           while(i>a){ i-=k; k--; }
       }
       if (i==a) { System.out.print("1"+" "); }
       else{System.out.print("0"+" ");}

    }
  }
}

Hi
Here is the correct formula: (sqr(n)+n+2)/2 (for n from 0 to ...)
If one needs I'll explain it.

Edited by author 06.05.2014 21:12

Thank u for your clever explanation!