У меня программа получила AC, хотя на тест 1999 выдавала ответ 1991... мне кажется, что это не совсем верно...

I got WA on Test 16,but I don't know why.

Interesting, most people hit WA2 then AC, but I skipped WA2 and jumped right to WA3, seem to be the first to hit it.   Can't find the error....switched to java & BigInteger thinking numerical overflow in c++ may be the issue but still WA3.   Argh.

I've read it for 15 min..AC at the first time...
sort all the integer to a descending sequence.
repeat for n-1 times:
combine a[1] and a[2](2sqrt(xy))
delete(a[1],a[2])
insert the new real number into the sequence
and remember to keep the descending.

print the final a[1].

4
1
4
5
6
ans: 17

-->  1,4    4
<-- 1        1
--> 1,5     5
<-- 1        1
--> 1,6     6
               17

My code...

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

struct LAN
{
    int somay;
    char **IP;
    char **Sub;
};

int ChungMang(int a, int b, LAN *L);
void Dijkstra(LAN *L, int d[], int prev[], int label[], int dau, int cuoi, int somang,int &kq);
void Show(int dau, int cuoi, int prev[]);

void main ()
{
    int somang;
    cin>>somang;
    LAN *L;
    L= new LAN[somang+1];
    for(int i =1;i<=somang;i++)
    {
        cin>>L[i].somay;
        L[i].IP=new char*[L[i].somay];
        L[i].Sub=new char*[L[i].somay];
        for(int j = 0;j<L[i].somay;j++)
        {
            L[i].IP[j]=new char[100];
            L[i].Sub[j]=new char[100];
            cin>>L[i].IP[j]>>L[i].Sub[j];
        }
    }
    int dau, cuoi;
    cin>>dau>>cuoi;
    int d[91];
    int prev[91];
    int label[91];
    int kq=1;
    Dijkstra(L,d,prev,label,dau,cuoi,somang,kq);
    if(kq==0)
        return;
    cout<<"Yes\n";
    Show(dau,cuoi,prev);
}
void Init(int d[], int prev[], int label[], int n, int dau)
{
    for(int i=1; i<=n;i++)
    {
        d[i]=-1;
        prev[i]=-2;
        label[i]=1;
    }
    d[dau]=0;
}
void Dijkstra(LAN *L, int d[], int prev[], int label[], int dau, int cuoi, int somang,int &kq)
{
    Init(d,prev,label,somang,dau);
    while(label[cuoi]==1)
    {
        int iMin = -1;
        int v = -1;
        for(int i=1;i<=somang;i++)
        {
            if(label[i]==1 && d[i]!=-1&&(d[i]<iMin||iMin==-1))
            {
                iMin = d[i];
                v=i;
            }
        }
        if(iMin == -1)
        {
            cout<<"No";
            kq =0;
            break;
        }
        d[v]=iMin;
        label[v]=0;
        for(int j=1;j<=somang;j++)
        {
            if(label[j]==1&& ChungMang(v,j,L)==1)
            {
                d[j]=d[v]+1;
                prev[j]=v;
            }
        }
    }
}
int Test(char *IP3, char *IP4, char *Sub3, char *Sub4)
{
    char *IP1 = IP3;
    char *IP2=IP4;
    char *Sub1= Sub3;
    char *Sub2=Sub4;
    int i=0;
    int nIP=0;
    int nSub=0;
    while(nIP!=3)
    {
        if(IP1[i]=='.')
            nIP++;
        i++;
    }
    nIP=i;
    i=0;
    while(nSub!=3)
    {
        if(Sub1[i]=='.')
            nSub++;
        i++;
    }
    nSub=i;
    IP1[nIP]='\0';
    IP2[nIP]='\0';
    Sub1[nSub]='\0';
    Sub2[nSub]='\0';
    if(strcmp(IP1,IP2)==0&&strcmp(Sub1,Sub2)==0)
        return 1;
    return 0;
}

int ChungMang(int a, int b, LAN *L)
{
    int giong=0;
    for(int i=0;i<L[a].somay;i++)
    {
        for(int j = 0;j<L[b].somay;j++)
        {
            if(Test(L[a].IP[i],L[b].IP[j],L[a].Sub[i],L[b].Sub[j]))
                return 1;
        }
    }
    return 0;
}
void Show(int dau, int cuoi, int prev[])
{
    int temp[100];
    int i=99;
    int k = cuoi;
    cout<<dau;
    while (k != dau)
    {
        temp[i]=k;
        k=prev[k];
        i--;
    }
    for(int j = i+1;j<100;j++)
    {

            cout<<" "<<temp[j];
        cout<<endl;
    }
}

this kind of problems are easy,, i guess they exist to build up your confidence. xD

then check carefully your solution for n=3 :)

i found my mistake :)

Edited by author 15.10.2012 19:23

Edited by author 15.10.2012 19:23

What is wrong with my code? I can't figure out by myself:(

Some people talking about some tricky case. What is it?

I dont know if I use the array with size 131072 I get result "access violation" if I use the size 131073 I get the result "stack overflow" so how I get the right way to resolve the problem, sorry for my bad english;

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

int main()
{
    int index = -1;
    double stack[131073];
    while(scanf("%lf", &stack[++index]) != EOF);
    for(; top > 0;printf("%.4lf\n", sqrt(stack[--index])));
    return 0;
}

Edited by author 07.12.2012 09:36

Why this contest is absent in archive of competitions:
http://acm.timus.ru/monitor.aspx?id=61
?

And why I was disqualified from it?
I am very advanced mathematician so why the fact that I solved problems A and B during the contest so bothered admins? It's complete lawlessness :(

N=12 Q=26 not 34.

My solutions is stack overflow in test 9. Help me, please.

Could anyone give me the test#6?
godsuriyel@gmail.com
thanks!

I want some tips or tests