Who know O(H*W) or, O(H*W*5) algo ???

С 20 не проходит 15 тест!!!

PS. У меня тесты проходит
PSS. базовые)

#include<iostream>
#include<vector>
using namespace std;

int test(int a);
vector<int> list;
//vector<int> answers;

int main()
{
    list.push_back(0);
    list.push_back(1);
    int N;
    cin >> N;
    while (N != 0)
    {
        cout << test(N);
    //    answers.push_back(test(N));
        cin >> N;
    }
    //for (int i = 0; i < answers.size(); i++)
    //    cout << answers[i] << endl;
    return 0;
}

int test(int a)
{
    int i = 2;
    if (a < list.size() && a % 2 == 0)
        return list[a - 1];
    else if (a < list.size() && a % 2 != 0)
        return list[a];
    else if (a >= list.size())
        i = list.size();
    for (i; i <= a; i++)
    {
        if (i % 2 == 0)
            list.push_back(list[i / 2]);
        else
            list.push_back(list[i / 2] + list[i / 2 + 1]);
    }
    if (a % 2 == 0)
        return list[a - 1];
    else
        return list[a];
}

Edited by author 11.01.2017 16:19

Edited by author 11.01.2017 16:21

the same c++ code was accepted when I used visual studio, but gave TLE 8 with g++ 9 (or g++ 9, C11)

i try to solve it with kruskal and it gives me wa6 can anyone help me?

type
 Ta=record
 x,y:extended;
end;

var a,b,c:Ta;
    ab,ac,bc,p,s,h,m:extended;
    l:extended;

    function max(a,b:extended):extended;
    begin
     if a-b>0 then max:=a else max:=b;
    end;

begin
 readln(a.x,a.y,b.x,b.y);
 readln(c.x,c.y,l);

 ac:=sqrt(sqr(a.x-c.x)+sqr(a.y-c.y));
 ab:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
 bc:=sqrt(sqr(b.x-c.x)+sqr(b.y-c.y));
 p:=(ab+ac+bc)/2;
 s:=sqrt(p*(p-ac)*(p-ab)*(p-bc));

 if ab=0 then h:=ac else h:=2*s/ab;

 if h-l>0 then          writeln(h-l:0:2)          else writeln('0.00');

m:=max(ac,bc);
 if m-l>0 then writeln(m-l:0:2) else writeln('0.00');
end.

Edited by author 03.08.2008 16:37

import java.util.Scanner;


public class Problem_1348 {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int ax,ay,bx,by,cx,cy,l;
        double ac,bc,ab,x,min,A,B,C,h;
        x=h=0;
        ax=in.nextInt();
        ay=in.nextInt();
        bx=in.nextInt();
        by=in.nextInt();
        cx=in.nextInt();
        cy=in.nextInt();
        l=in.nextInt();

        ab= Math.sqrt( (bx-ax)*(bx-ax)+(by-ay)*(by-ay) );
        ac =Math.sqrt( (cx-ax)*(cx-ax)+ (cy-ay)*(cy-ay) );
        bc= Math.sqrt( (cx-bx)*(cx-bx) + (cy-by)*(cy-by) );
        A=ac; B=bc; C=ab;

        x=(A*A-B*B+C*C)/(2*C);
       h= Math.sqrt((A*A-x*x));
         min=h;


          if(A>B){
            if(min-l<0)System.out.printf("%.2f",0.00); else System.out.printf("%.2f",min-l);
            System.out.println();
            if(A-l<0)System.out.printf("%.2f",0.00);else System.out.printf("%.2f",A-l);
        }else{
            if(min-l<0)System.out.printf("%.2f",0.00); else System.out.printf("%.2f",min-l);
            System.out.println();
            if(A-l<0)System.out.printf("%.2f",0.00);else System.out.printf("%.2f",B-l);
        }

    }
 }

Edited by author 06.05.2014 16:57

#include <iostream>
#include <string.h>
int main() {
    char grif[1001][202],sliz[1001][202],huff[1001][202],rave[1001][202],name[202],group[20];
    int n,i,gcur=0,scur=0,hcur=0,rcur=0;
    std:: cin >> n;
    while( n>=0 )
    {
                  std:: cin.getline(name,202);
                  std:: cin.getline(group,20);

                                if(!strcmp(group,"Slytherin"))  { strcpy(sliz[scur],name); scur++; }
                                if(!strcmp(group,"Hufflepuff")) { strcpy(huff[hcur],name); hcur++; }
                                if(!strcmp(group,"Gryffindor")) { strcpy(grif[gcur],name); gcur++; }
                                if(!strcmp(group,"Ravenclaw"))  { strcpy(rave[rcur],name); rcur++; }

                  --n;
    }

    std::cout<<"Slytherin:\n";
    for( i=0; i<scur; ++i ) std:: cout << sliz[i] << '\n';
    std::cout<<'\n';

    std::cout<<"Hufflepuff:\n";
    for( i=0; i<hcur; ++i ) std:: cout << huff[i] << '\n';
    std::cout<<'\n';

    std::cout<<"Gryffindor:\n";
    for( i=0; i<gcur; ++i ) std:: cout << grif[i] << '\n';
    std::cout<<'\n';

    std::cout<<"Ravenclaw:\n";
    for( i=0; i<rcur; ++i ) std:: cout << rave[i] << '\n';
    std::cout<<'\n';

    return 0;
    }

#include <iostream>
using namespace std;
int main() {
    int n, res = 0;
    cin >> n;
    if (n < 0) {
        for (int i = -2; i >= n; i--) {
            res = res + i;
            }
        cout << res;
    }
    else {
        for (int i = 1; i <= n; i++) {
            res = res + i;
        }
        cout << res;
    }
    return 0;
}

Very short,AC in 0.484s. Not so fast as I expected.

Please someone tell me where is the wrong in my code.

#include <iostream>
#include <queue>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
using namespace std;
struct dott{
    int x;
    int y;
};
int main()
{
    char str[8];
    gets(str);
    if(strlen(str) <= 2){
        int a, b, n;
        n = atoi(str);
        bool XY[200][200];
        memset(XY, 0, sizeof(XY));
        struct dott center;
        cin>>a>>b;
        center.x = a;
        center.y = b;
        for(int i=2; i<=n; i++){
            cin>>a>>b;
            XY[a][b] = 1;
        }
        queue<dott> qu;
        qu.push(center);
        cout<<center.x<<" "<<center.y<<"\n";
        while(!qu.empty()){
            dott pix = qu.front();
            qu.pop();
            if(XY[pix.x + 1][pix.y] == 1){
                cout<<"R";
                center.x = pix.x + 1;
                center.y = pix.y;
                qu.push(center);
                XY[pix.x + 1][pix.y] = 0;
            }
            if(XY[pix.x][pix.y + 1] == 1){
                cout<<"T";
                center.x = pix.x;
                center.y = pix.y + 1;
                qu.push(center);
                XY[pix.x][pix.y + 1] = 0;
            }
            if(XY[pix.x - 1][pix.y] == 1){
                cout<<"L";
                center.x = pix.x - 1;
                center.y = pix.y;
                qu.push(center);
                XY[pix.x - 1][pix.y] = 0;
            }
            if(XY[pix.x][pix.y - 1] == 1){
                cout<<"B";
                center.x = pix.x;
                center.y = pix.y - 1;
                qu.push(center);
                XY[pix.x][pix.y - 1] = 0;
            }
            if(!qu.empty()){
                cout<<",\n";
            }
            else{
                cout<<".";
            }
        }
    }
    else{
        int a, b, count=0;
        bool XY[200][200];
        memset(XY, 0, sizeof(XY));
        struct dott centre;
        char *s;
        s = strtok(str," ");
        a = atoi(s);
        s = strtok(NULL," ");
        b = atoi(s);
        XY[a][b] = 1;
        centre.x = a;
        centre.y = b;
        queue<dott> qu;
        qu.push(centre);
        string str[200];
        for(int i=0; ;i++){
            cin>>str[i];
            if(str[i] == "."){
                break;
            }
            count++;
        }
        for(int i=0; i<count; i++){
            dott S = qu.front();
            qu.pop();
            for(int j=0; j<str[i].size(); j++){
                if(str[i][j] == 'R'){
                    XY[S.x+1][S.y] = 1;
                    centre.x = S.x+1;
                    centre.y = S.y;
                    qu.push(centre);
                }
                if(str[i][j] == 'T'){
                    XY[S.x][S.y+1] = 1;
                    centre.x = S.x;
                    centre.y = S.y+1;
                    qu.push(centre);
                }
                if(str[i][j] == 'L'){
                    XY[S.x-1][S.y] = 1;
                    centre.x = S.x-1;
                    centre.y = S.y;
                    qu.push(centre);
                }
                if(str[i][j] == 'B'){
                    XY[S.x][S.y-1] = 1;
                    centre.x = S.x;
                    centre.x = S.y-1;
                    qu.push(centre);
                }
            }

        }
        cout<<count+1<<"\n";
        for(int i=0; i<100; i++){
            for(int j=0; j<100; j++){
                if(XY[i][j] == 1){
                    cout<<i<<" "<<j<<"\n";
                }
            }
        }
    }
    return 0;
}

Edited by author 09.01.2017 17:37

Please someone tell me where maximum people make mistake in this problem.

Or please provide some hints.

#include<stdio.h>
#include<string.h>
char s[100];
bool map[200][200],bo;
int n,m,x,y,xx,yy,a[11000],b[11000],c,zy;
void find(int xx,int yy,int xy)
{
    bool l,r,s,x;
    l=r=s=x=false;
    map[xx][yy]=false;
    if (map[xx+1][yy]) {printf("R");map[xx+1][yy]=false;c++;a[c]=xx+1;b[c]=yy;}
    if (map[xx][yy+1]) {printf("T");map[xx][yy+1]=false;c++;a[c]=xx;b[c]=yy+1;}
    if (map[xx-1][yy]) {printf("L");map[xx-1][yy]=false;c++;a[c]=xx-1;b[c]=yy;}
    if (map[xx][yy-1]) {printf("B");map[xx][yy-1]=false;c++;a[c]=xx;b[c]=yy-1;}
    if (xy==c) return;
    printf(",\n");
    if (xy<c)
      find(a[xy+1],b[xy+1],xy+1);

}
int main()
{
    memset(map,false,sizeof(map));
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    gets(s);
    if (strlen(s)==1)
    {
        n=s[0]-48;
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d",&x,&y);
            if (i==1)
            {
              xx=x;
              yy=y;
            }
            map[x][y]=true;
        }
        a[1]=xx;
        b[1]=xx;
        c=1;
        printf("%d %d\n",xx,yy);
        find(xx,yy,1);
        printf(".\n");
    }
    else
    {
        x=s[0]-48;
        y=s[2]-48;
        map[x][y]=true;
        zy=1;
        c=1;
        while (true)
        {
          gets(s);
          if (s[0]=='.') break;
          for (int i=0;i<=strlen(s);i++)
          {
             if (s[i]=='R')
             { c++;a[c]=x+1;b[c]=y;
               map[x+1][y]=true;
             }
             else
             if (s[i]=='T')
               {map[x][y+1]=true;c++;a[c]=x;b[c]=y+1;}
             else
             if (s[i]=='L')
               {map[x-1][y]=true;c++;a[c]=x-1;b[c]=y;}
             else
             if (s[i]=='B')
               {map[x][y-1]=true;c++;a[c]=x;b[c]=y-1;}
           }
           zy++;
           x=a[zy];
           y=b[zy];
        }
        printf("%d\n",zy);
        for (int i=1;i<=10;i++)
          for (int j=1;j<=10;j++)
            if (map[i][j]) printf("%d %d\n",i,j);
    }
}

I feel wonderful.:)

Can anybody explain me why one program can have different execution time with the same code?
My friend with my code got 0.015 but I got 0.031.

Oops =)
I send it one more time and get 0.015.
Maybe it because of server...

Edited by author 22.11.2010 21:59