import java.util.Scanner;


public class Test {

    public static void main(String[] args) {

Scanner in = new Scanner(System.in);
float b = 0;
float a = in.nextInt();

in.close();


if ( a >= 1) {

    b =  ((a + 1) /2) * a;



    System.out.println((int)b);}

else


{
    b = ((-a + 1) /2) * -a;

System.out.println((int)-b+1);}

}}

Edited by author 28.12.2013 05:22

this is a shape of sample#1: ('B'=Black, '.'=white)
B...B
.B...
..B..

you must count all the streak which not belong to the streak with size more than current streak, therefor the cell's (1,2) & (2,1) & (3,2) must'nt count because they are belong to streak (1,2)->(1,4) & (2,1)->(2,2) & (3,1)->(3,2).

here some test for problem:
//////////////////////////
input:
5 5 2
1 2
3 3

output:
12
//////////////////////////
input:
5 5 4
1 2
5 3
3 1
4 4

output:
12
//////////////////////////
input:
1 1 0

output:
1
//////////////////////////
input:
1 1 1
1 1

output:
0
/////////////////////////
input:
5 5 12
1 2
1 4
2 1
2 3
2 5
3 2
3 4
4 1
4 3
4 5
5 2
5 4

output:
13
//////////////////////////////
I hope can help you.
GOOD LUCK!

My method of making graph connected works nearly by O(N^2). Are there any classic algorithmes for such problem?

I have submit my solution, where I have used the system of disjoint sets. But it has WA 1 :))
What is another way to solve this problem???

type t=record
     x,y:real;
     end;

function dlina(x1,y1,x2,y2:real): real;
begin
 dlina:=sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
end;


var n,i:integer; x,y,p,cos,r:real; mas:array[1..103] of t;
Begin
readln(n,r);
p:=0;
for i:=1 to n do begin
  readln(mas[i].x,mas[i].y);
  if i>1 then p:=p+dlina(mas[i-1].x,mas[i-1].y,mas[i].x,mas[i].y);
end;
p:=p+dlina(mas[1].x,mas[1].y,mas[n].x,mas[n].y);



p:=p+2*3.14159*r;
writeln(p:1:2);

end.

#include <stdio.h>
int main()
{
   long int k,a,n;
   scanf("%ld",&n);
   while(n--)
   {


   scanf("%ld",&k);
   a=1;
   while(k-a>0)
    k=k-(a++);
   if(k==1)
    printf("1\n");
   else
    printf("0\n");
   }
}






Edited by author 27.12.2013 01:54

if((8*(input) - 7) -> integer)
 cout << 1;
else
 cout << 0;

help!I need the test data.

For this problem,when I used G++,I got AC,but when I used GCC,I got WA so many times.
Why?
#include<stdio.h>
#include<math.h>
int main()
{
     double b[3000000];
     int n=0;
     double temp;
     while(scanf("%lf",&temp)!=EOF)
          b[n++]=sqrt(temp);
     for(int i=n-1;i>=0;i--)
          printf("%.4lf\n",b[i]);
     return 0;
}

Edited by author 26.12.2013 18:14

Taking hints from the forum I am using dynamic programming with bitmasking. But I cannot understand how to memoize the results as the number of subproblems are very large. ie.
2^n * m
that is 2^20 * 120.
I am getting Memory limit exceeded. Is there a better way to define the states of the dp?

It is very easy problem, i think complexity estimation 192 is overestimation.
Very simple search was accepted:

        static bool Solve(IEnumerable<Tuple<int, int>> limitations, int[] proposedOrder)
        {
            foreach (Tuple<int, int> limitation in limitations)
            {
                int less = limitation.Item1;
                int greater = limitation.Item2;
                if (less == greater)
                    return false; // wrong rule

                foreach (int currentSubj in proposedOrder)
                {
                    if (currentSubj == greater)
                        return false; // first is greater, so rule is contradicted
                    if (currentSubj == less)
                        break; // first is smaller, so rule is satisfied, go to next one
                }
            }
            return true; // all rules was satisfied
        }

program ytr;
var n,i,p,d,t,min:longint; a:array[1..100000] of longint; b:boolean;
begin
readln(n); t:=-1; b:=true; p:=1;
for i:=1 to n do
     begin
     read(a[i]); if b then begin min:=a[i]; b:=false; end;
     inc(t);
     if a[i]<min then begin p:=i-t; d:=t; t:=0; min:=a[i]; end;
     if (i=n) and (t>d) then p:=i-t;
     end;
write(p);
end.

I have solved this problem using heap:)
Please, give me advise, how to solve this problem without structures and etc.

Что-то пошло не так, да?
var
   radius,otvet:real;  //радиус шляпок и ответ
   first_y:real; //  "новый" у
   second_y:real;//   "старый" у
   first_x:real; //  "новый" х
   s_x:real;//   "старый" х
   one_y:real; //самый первый у
   one_x:real; //самый первый х
   l:real; //длина одной черты
   numbers,a,b:integer;  //кол-во гвоздей и две переменные для циклов
begin
   read (numbers);  //прочитал кол-во гвоздей
   read (radius);   //прочитал радиус шляпок
   read(one_x);
   read(one_y);   //прочитал значение х и у первой точки (сохранил в
   // отдельной переменной для конечной линии)
   read(first_x);
   read(first_y); //прочитали значение х и у второй точки
   b:=numbers-2;  //для цикла
   l:=sqrt((one_x-first_x)*(one_x-first_x)+(one_y-first_y)*(one_y-first_y));
   //вычислил длину первой линии
   otvet:=otvet+l; //и прибавил к ответу
   for a:=1 to b do begin
         s_x:=first_x; //перераспределение точек
         second_y:=first_y;
         read(first_x);      //аналогично
         read(first_y);
l:=sqrt((s_x-first_x)*(s_x-first_x)+(second_y-first_y)*(second_y-first_y));
         otvet:=otvet+l;
   end;
   l:=sqrt((one_x-first_x)*(one_x-first_x)+(one_y-first_y)*(one_y-first_y));
   otvet:=otvet+l;
   otvet:=round(100*otvet)/100; //округлил ответ до 0.01
   l:=radius*2*3.14; //вычислил длину одной окружности
   otvet:=otvet+l;  // и прибавил ее к ответу

   writeln(otvet); //вывел ответ
end.
На первом же тесте неправильный ответ
Помогите

#include <stdio.h>
#include <math.h>

int main(void)
{
    int i = 0;
    unsigned long long a;
    double b[1024];

    while (EOF != scanf("%Ld", &a))
    {
        b[i++] = sqrt(a);
    }

    while (i--)
        printf("%.4f\n", b[i]);

    return 0;
}

give me some tests
))

Please remember, that:
1. I recommend you to use the most accurate floating-point type you have (C# = decimal, Pascal = extended etc.)

2. use constant:
s = 0.70710678118654752440084436210485

3. Some tests have no '0' symbol.

4. (For notebook owners) Remember, that the author of the statement said to use computer digit keys (not telephone digit keys!).
So the numbers are situated in such order:

7 8 9
4 5 6
1 2 3

If you got TLE, try change adjacency matrix to edge list.

Did you use DP to solve this problem?
How did you do it?