Может ли быть между двумя комнатами больше чем одна дверь?

Whether in a problem 1129 some variants of the answer are possible??

How to avoid TLE in Test#10?

#include<iostream>
#include<cmath>
using namespace std;
void solve ( double a )
{
    double b;
    while ( cin>>b )
        solve(b);
    printf("%.4lf\n",sqrt(a));
}
int main ( )
{
    double a;
    cin>>a;
    solve(a);
}

Please help me, look over my code, I'll be thankfull to anyone who will find mistake in my code, or give me some tests.

var
  h,s,aa,bb:real;
  a:array[1..3,1..2] of integer;
  i,l:integer;


procedure readdata;
begin
  readln(a[1,1],a[1,2],a[2,1],a[2,2]);
  readln(a[3,1],a[3,2],l);
end;

procedure writedata;
begin
  writeln(aa:0:2);
  writeln(bb:0:2);
end;

function d(x1,y1,x2,y2:integer):real;
begin
  d:=sqrt(sqr(x1-x2)+sqr(y1-y2));
end;

procedure square;
var
  p,a1,a2,a3:real;
begin
  a1:=d(a[1,1],a[1,2],a[2,1],a[2,2]);
  a2:=d(a[3,1],a[3,2],a[2,1],a[2,2]);
  a3:=d(a[1,1],a[1,2],a[3,1],a[3,2]);
  p:=(a1+a2+a3)/2;
  s:=sqrt(p*(p-a1)*(p-a2)*(p-a2));
end;

begin
  readdata;
  square;

  h:=d(a[1,1],a[1,2],a[2,1],a[2,2]);

  aa:=s/(0.5*h);
  if d(a[1,1],a[1,2],a[3,1],a[3,2])<aa
  then aa:=d(a[1,1],a[1,2],a[3,1],a[3,2]);
  if d(a[2,1],a[2,2],a[3,1],a[3,2])<aa
  then aa:=d(a[2,1],a[2,2],a[3,1],a[3,2]);

  bb:=d(a[3,1],a[3,2],a[2,1],a[2,2]);
  if d(a[3,1],a[3,2],a[1,1],a[1,2])>bb then
  bb:=d(a[3,1],a[3,2],a[1,1],a[1,2]);
  if (s/(0.5*h))>bb then bb:=(s/(0.5*h));

  aa:=aa-l;
  bb:=bb-l;
  writedata;
end.

Is example in problem right? I think it is not!!!

if there is a route like below:

3 1 2 3

Can I go from station 3 to station 1 directly? I mean, is the route a circle?

What is the minimal value for Ai?

what is the solution for this problem?

#include<stdio.h>
#include<stdlib.h>
#define MAX 1002
int join[MAX][MAX],cont[MAX],used[MAX],win[MAX];
int np,mark,fri;
int tree(int aa)
{
    int i,j,k,mar=0,min1=MAX,min2=MAX;
    used[aa]=1;
    if(cont[aa]==1&&aa!=fri)//!!cout为1可为终点，亦可为起点~！！
    {
       win[aa]=aa;
        return 0;
    }
    for(i=1;i<=np;i++)
    {
        if(join[aa][i]&&!used[i])
        {

            k=tree(i);
            if(!k&&min1>win[i])
            {
                mar=1;
                min1=win[i];
            }
            if(k&&min2>win[i])
                min2=win[i];
        }
    }
    if(mar)
    {
        win[aa]=min1;
            return 1;
    }
    else
    {
        win[aa]=min2;
        return 0;
    }
}

int main()
{
    int i,j,k,mar=0;
    scanf("%d%d",&np,&fri);
    for(i=1;i<np;i++)
    {
        scanf("%d%d",&j,&k);
        join[j][k]=1;
        join[k][j]=1;
        cont[j]++;
        cont[k]++;
    }
    k=tree(fri);
    if(k)printf("First player wins flying to airport %d\n",win[fri]);
    else printf("First player loses\n");
//    system("pause");
    return 0;
}

This is my prog

#include<iostream>
using namespace std;


int a[102][502]={{0}},path[102][502]={{0}};
int n,m;

void matr(int i)
{
    int j;
    int p1[500]={0},p2[500]={0};
    int pre1[500],pre2[500];

       p1[0]=p2[n+1]=10000;

    // left to right
    for(j=1;j<=n;j++)
        if(p1[j-1]+a[i][j]>a[i][j]+a[i-1][j]){p1[j]=a[i][j]+a[i-1][j];pre1[j]=j;}
        else{p1[j]=p1[j-1]+a[i][j];pre1[j]=j-1;}

        //right to left
    for(j=n;j>=1;j--)
        if(p2[j+1]+a[i][j]>a[i][j]+a[i-1][j]){p2[j]=a[i][j]+a[i-1][j];pre2[j]=j;}
        else {p2[j]=p2[j+1]+a[i][j];pre2[j]=j+1;}

        //sravnenie
    for(j=1;j<=n;j++)
    {
        if(p1[j]>p2[j]){a[i][j]=p2[j];path[i][j]=pre2[j];}else{a[i][j]=p1[j];path[i][j]=pre1[j];}
        p1[j]=p2[j]=0;
    }
}

int main()
{
    int i,j,min=10000,mini;


    cin>>m>>n;

    for(i=1;i<=m;i++)
    {
        a[i][0]=a[i][n+1]=10000;
        for(j=1;j<=n;j++)cin>>a[i][j];
    }

    for(i=2;i<=m;i++)matr(i);


    for(i=1;i<=n;i++)
        if(min>a[m][i]){min=a[m][i];mini=i;};

    int k1=m,k2=mini,kol=1,ans[500];

    if(m==1)cout<<mini;else{
    ans[kol]=k2;
    do
    {
        kol++;
        ans[kol]=path[k1][k2];
        if(path[k1][k2]==k2)k1--;else k2=path[k1][k2];
    }while(path[k1][k2]!=0);


    for(i=kol;i>=1;i--)cout<<ans[i]<<" ";}
    return 0;
}

Some people might not know English.
Anyway, it is a Russian website, it has to have a Russian version of anything.
But so far almost one fourth of the tasks or more does not have a Russian version.
All of the tasks that did not have a Russian version two years ago still do not have one.
Is it really so hard for the admins to spend one day translating the tasks into Russian?

Edited by author 31.07.2008 06:35

#include <iostream>
#include <stdlib.h>
long long x[150001],y[150001];
using namespace std;

int main(int argc, char *argv[])
{
    long n,f[101],i,j;
    for(i=0;i<=100;i++) f[i]=0;
    cin>>n;
    for(i=0;i<n;i++)
         {cin>>x[i]>>y[i];
         f[y[i]]=1;}
    for(i=100;i>=0;i--)
       if(f[i]==1)
         for(j=0;j<n;j++)
           if(y[j]==i)
             cout<<x[j]<<" "<<y[j]<<endl;
  system("PAUSE");
  return 0;
}

Funny to say, but once I've read this problem, I remembered
the simplex method we were taught last year.
The classic problem of simplex method is like this:
find min(max)f(X)=C1*X1+C2*x2+c3*x3.. where ci - constants
Also where is a system of conditions:
a11*x1+..<=(>=)b1
a21*x1+..<=(>=)b2 and so on.
The simplex method finds the solution very fast, but it can be a real value, not an integer. There is also a modification of SM called integer SM - it will find an integer solution. Is the problem based on this algo or not?

Hungarian method of weighted matching!
It's interesting that I solved 1449
by first version of program without any optimization.
It,s rather strange because commonly
challange team prepear most difficult tests with respect
to time and memory. Now the problem has junior level.
This is  a pity, because matching frequently using on
various contests.
For information: Let W- weight of maximal matching in A[][]
Graph. Then W- our answer.

subj

0 also answer???

Edited by author 25.02.2006 14:04