I know the meaning of this problem,but I just can't find a good way to solve it!!
So who can tell me ?
Thank you!
I use C++

Edited by author 06.09.2010 20:15

MY ALGO TIME CONSUMED IS(250+128)*N unit

my method is:

divide distance between [0,32000] to 128 sector
each sector is total of stars that occured in that portion
hence for each x, level x calcute of bottom formula
level = sector[x/250]+ Xpivot[i] that i=int(x/250)*250 to x
in last update value of all sector that indexs greater than this sector index;

{$N+}
Program Mars_satellites;

 Var
   cos_,x,a,b,c,d:Double;

Begin
  Readln(a,b,c,d);
  If (a*b-c*d)=0 Then
  Begin
    Write('Impossible');
  End
  Else
  Begin
    cos_:=a*a+b*b-c*c-d*d;
    cos_:=cos_/(2*a*b-2*c*d);
    x:=a*a+b*b-2*a*b*cos_;
    x:=sqrt(x);
    x:=round(1000*x);
    Write('Distance is ',x:0:0,' km.');
  End;
End.

I don't know what's wrong, but it seems that i get wrong answer on test 11. Do you have any idea what it contains?

Hey, everybody! I'd like to ask for a test data of this problem similar to test #8. I've read through the discussions and passed all the test data given in earlier topics but still got stuck at #8. Any help will be appreciated!!


Edited by author 07.04.2012 14:05

wa #21. Can anybody help me?

Program P1;
Var
  Map: Array[1..100,1..100] of Integer;
  S,G,F: Array[1..100] of Integer;
  A,I,B,J,N,M,K,L,P,R: Integer;

Begin
  Readln(N,M);
  For A:=1 to N do
    For B:=1 to N do
      Map[A,B]:=16000;

  For I:=1 to M do begin
    Read(L);
    For J:=1 to L do
      Read(S[J]);
    For A:=1 to L do
      For B:=1 to L do
        Map[S[A],S[B]]:=1;
  End;

  For A:=1 to N do
    For B:=1 to N do
      For I:=1 to N do
        If Map[A,B]>Map[A,I]+Map[I,B] then Map[A,B]:=Map[A,I]+Map[I,B];

  Read(K);
  A:=0;
  For I:=1 to K do begin
    Readln(G[I],S[I],F[I]);
    A:=A+G[I];
  End;

  P:=0;
  R:=P;
  For I:=1 to N do begin
    P:=0;
    For J:=1 to K do begin
      If I=S[J] then begin P:=P+G[J]; continue; End;
      If Map[I,S[J]]=16000 then begin P:=0; Break; End;
      If (Map[I,S[J]]*4>=G[J]) and (F[J]=0) then begin P:=0; Break; End;
      If F[J]=1 then begin P:=P+G[J]; Continue; End;
      P:=P+G[J]-Map[I,S[J]]*4;
    End;
    If P>R then begin
      R:=P;
      L:=I;
    End;
  End;
  If R<>0 then Writeln(L,' ',A-R)
          else Writeln(0);
End.

try this test case

dfadfmmmmfad

Correct answer

dfadad

Hope this helps...

Could somebody give me 12 test ?

Sory for bad my English...

Some incorrect algorythm has a wrong "Accept"
test:
6
9 8 6 5 4 1

here is my program it works right on the first test on my PC but here it fails!!! I even don't know what's the problem.
I hope that the first test is the same as in the text, otherwise there's really something wrong with the pro.

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

#define MaxN 50010
#define MaxLogN 20
#define MaxM 75010

vector< pair<int,int> > list[MaxN];
int pr1[MaxN][MaxLogN];                    //array of 2^i -th ancestor with the cost
int pr2[MaxN][MaxLogN];

int tin[MaxN];
int tout[MaxN];
int used[MaxN];

int l=MaxLogN;

int timer=0;

void dfs(int v, int p, int cost)
{
    used[v]=1;

    tin[v]=timer;
    timer++;

    pr1[v][0]=p;
    pr2[v][0]=cost;

    for(int i=1; i<l; i++)
    {
        pr1[v][i]=pr1[pr1[v][i-1]][i-1];
        pr2[v][i]=pr2[v][i-1] + pr2[pr1[v][i-1]][i-1];
    }

    for(int i=0; i<list[v].size(); i++)
    {
        if(used[list[v][i].first]==0)
            dfs(list[v][i].first,v,list[v][i].second);
    }

    tout[v]=timer;
    timer++;
}

int upper(int a,int b)
{
    if(tin[a]<=tin[b] && tout[b]<=tout[a]) return 1;
    return 0;
}

int lca(int a,int b)
{
    //a - ancestor
    if(upper(a,b)==1)
    {
        int i=0;
        while(upper(pr1[b][i],a)==0 && i<l) i++;

        i--;

        if(pr1[b][i+1]==a) return pr2[b][i+1];

        return pr2[b][i]+lca(a,pr1[b][i]);
    }
    //b - ancestor
    if(upper(b,a)==1)
        return lca(b,a);

    for(int i=0; i<l; i++)
    {
        if(upper(pr1[a][i],b)==1)
        {
            if(i==0)
                return pr2[a][i]+lca(pr1[a][i],b);
            return(pr2[a][i-1]+lca(pr1[a][i-1],b));
        }
    }

}

int main()
{

    memset(used,0,MaxN*sizeof(used[0]));
    memset(pr1,0,MaxN*MaxLogN*sizeof(pr1[0][0]));
    memset(pr2,0,MaxN*MaxLogN*sizeof(pr2[0][0]));

    /*freopen("INPUT.txt","r",stdin);
    freopen("OUTPUT.txt","w",stdout);*/

    int n,m;

    cin>>n;
    for(int i=0; i<n-1; i++)
    {
        int a,b,w;
        cin>>a>>b>>w;

        list[a].push_back(make_pair(b,w));
        list[b].push_back(make_pair(a,w));

    }

    dfs(0,0,0);

    cin>>m;

    int ans[MaxM];
    for(int i=0; i<m; i++)
    {
        int a,b;
        cin>>a>>b;
        ans[i]=lca(a,b);
    }

    for(int i=0; i<m-1; i++)
        cout<<ans[i]<<"\n";
    cout<<ans[m-1];

}

Thanks

01.01 21.59
04.23 11.22
Answer: 5

12.00 15.00
20.00 21.00
Answer: 1

23.58 00.43
22.27 03.10
Answer: 2

12.00 15.00
01.02 03.07
Answer: 0

01.01 10.59
04.23 04.22
Answer: 5

23.42 01.14
08.10 17.51
Answer: 4

I use long long int with MinGW and have right answer for the input of 1000000000.Why it is still wrong?
Here is my C code.
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int sum(int a);
int main()
{
    int count[10],i,j,base=0;        //use count[2] to count [9] to store the number of digits
    long long int n,product=0;
    for(i=0;i<10;i++)
        count[i]=0;
    scanf("%lld",&n);
    if(n==1)
        printf("%d\n",1);
    else if(n==0)
        printf("%d\n",10);
    else{
    for(i=9;i>1;i--){
        while(n%i==0){
            n/=i;
            count[i]++;
        }
    }
    if(n==1){
  /*      for(i=2;i<=9;i++){
            for(j=0;j<count[i];j++){
                printf("%d",i);
            }
        }
  */
        for(i=9;i>=2;i--){
            product=product+i*sum(count[i])*pow(10,base);
            base=base+count[i];
        }
        printf("%lld",product);
    }
    else
        printf("%d",-1);
    printf("\n");
    }
    system("pause");
    return 0;
}

int sum(int a)
{
    int term=1,i,result=0;
    for(i=0;i<a;i++){
        result+=term;
        term*=10;
    }
    return result;
}

Hi. What is the answer to 1A "window" or "aisle"?

I have checked all known numbers - result is right. When I submit code, system writes: Wrong answer. Where is error? Thank You!

using System;

class Program
{
    static void Main()
    {
        int a = int.Parse(Console.ReadLine());
        int r = 0;
        if (a <= System.Math.Abs(10000))
        {
            if (a > 1)
            {
                for (int i = 1; i <= a; i++)
                {
                    r += i;
                }
            }
            if (a < 1)
            {
                for (int i = 1; i >= a; i--)
                {
                    r += i;
                }
            }
            Console.WriteLine(r);
        }
        else
            throw new Exception("Wrong number");
    }
}

please, someone explain the test case. i don't get how it is 540.0

Statement of problem is incorrect!
I think, that many users agree with me.
Fix it or "fix" author of this problem.
He is very crazy man(IMHO)

Just "norm" matrix after every calculating (a[i][j] make 1 if it was positive) or you will have overflow