I used Tarjan Algo, based on DFS and union-find sets, but got Crash AV #3. I made a extreme data myself, like a chain from Node #0. And it really crashed with DEV-C++. I tried to enlarge the size of stack, but it seemed workless. After debugging for so long, I still can't explain why it got stuck at Node #49xxx (The program works on every "smaller data"). Do I have to make a "stack" myself? No, I came up with an idea--randomize. And with that I ACed with no difficulty.
Here is the thing, maybe you picked Node #0 as the root of the tree, but why not change to a random one? I think data #3 is such a data that will make the first algo crash.
Sorry for my poor English, btw.

subj

Странно, но со struct работает и у меня; но не на сервере. У меня libc6.

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

struct Node // РЕШЕНИЕ: ЗДЕСЬ НУЖНО ПИСАТЬ class. Компилятор тимуса ругается почему-то.
{
    public:
    Node* prev;
    double info;
};

int main()
{
    Node* p = NULL;
    Node* node;
    double d;
    while(scanf("%lf",&d)!=EOF)
    {
        node = new Node;
        node->info = sqrt(d);
        node->prev = p;
        p = node;
    }

    while (p != NULL)
    {
        printf("%.4lf\n", p->info);
        p = p->prev;
    }
    return 0;
}

Edited by author 31.12.2009 03:44

I have got AC for this problem but my solution is quite inefficient

http://acm.timus.ru/status.aspx?space=1&num=1119&author=82952

It takes me 0.156 seconds to compute the answer, but there are many ppl who got solution in 0.015 secs.If possible please email me one of the efficient solution (C++ one).my email address is pjas002@aucklanduni.ac.nz

Thanks

Would anyone happen to know what test #12 is, or otherwise suggest something similar? Because I keep getting Time limit exceeded on it.

Thanks in advance.

http://vkontakte.ru/club1916204
All russians users vkontakte.ru go in this group)

Please give me some test or hint.

#include <stdio.h>
#include <math.h>
int main(){

freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
double x[102],y[102];
double d1,d2;
int i,star=0,k,m,n,j;
double s,r,pi=2*acos(0);

scanf("%d",&k);

for(m=0;m<k;m++){
    s=0;
scanf("%d %Lf",&n,&r);

for(i=0;i<n;i++)
scanf("%Lf %Lf \n",&x[i],&y[i]);
for(j=0;j<n-1;j++){
    d1=abs(x[j]-x[j+1]);
d2=abs(y[j]-y[j+1]);
s=s+sqrt(d1*d1 + d2*d2);

}
  d1=abs(x[0]-x[n-1]);
d2=abs(y[0]-y[n-1]);
s=s+sqrt(d1*d1 + d2*d2);

s=s+(n*pi*r)/2;

if(star==0) star=1;
else printf("\n");
printf("%.2Lf",s);
}
return 0;
}

using System;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string razd=":;, -";
            string kp=".!?";
            string dig = "0123456789";
            string[] input = Console.In.ReadLine().Split(
            new char[] {  '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);
            int cnt = 0;
            int ns = 0;
            int nb = 0;
            for (int i = 0; i < input.Length; i++)
            {
                string s = input[i];
                for (int j = 0; j < s.Length; j++)
                {
                    if ((s[j] >= 'A' && s[j] <= 'Z') || (s[j]>='a' && s[j]<='z') || dig.IndexOf(s[j])>=0)
                    {
                        nb++;
                        if (ns == 0) ns++;
                        if (nb == 1 && ns == 1 && (s[j] >= 'a' && s[j] <= 'z')) cnt++;
                        if ((s[j] >= 'A' && s[j] <= 'Z') && nb > 1) cnt++;
                    }
                    if (razd.IndexOf(s[j]) >= 0)
                    {
                        nb=0;
                        if (ns > 0) ns++;
                    }
                    if (kp.IndexOf(s[j])>=0)
                    {
                        ns = 0;
                        nb = 0;
                    }
                }
                nb = 0;
            }
            Console.WriteLine(cnt.ToString());
            Console.ReadKey();
        }
    }
}

What the answer to test:

    m    k    n
12    3    2    18

I got 53 and WA

I really don't like to do it, but i just can't find what is wrong in my code... In my pc it works pretty fine.. but, i got WA 4#...

my bugged code:

==========================================================

#include <iostream>

using namespace std;

void reordena(int *numeros[],int difzero,int num)
{
    int rdn1,rdn2,aux;

    rdn1 = rand() % difzero;
    rdn2 = rand() % difzero;

    aux = numeros[num][rdn1];
    numeros[num][rdn1] = numeros[num][rdn2];
    numeros[num][rdn2] = aux;
}

void permuta(int *numeros[],int num,int tam)
{
    int cont,cont2,aux,difzero=0,resp=0;
    int mult;
    long int contador=0;

    for(cont=0;cont<tam-1;cont++)
    {
        for(cont2=0;cont2<tam-1;cont2++)
        {
            if(numeros[num][cont2]==0)
            {
                aux = numeros[num][cont2];
                numeros[num][cont2] = numeros[num][cont2+1];
                numeros[num][cont2+1] = aux;
            }
        }
    }

    for(cont=0;cont<tam;cont++)
    {
        if(numeros[num][cont]!=0) difzero++;
    }

    mult=1;
    for(cont=difzero-1;cont>=0;cont--)
    {
        aux=(numeros[num][cont]*mult);
        resp+=aux;
        mult*=10;
    }

    while(resp%7!=0)
    {
        reordena(numeros,difzero,num);
        mult=1;
        resp=0;
        for(cont=difzero-1;cont>=0;cont--)
        {
            aux=(numeros[num][cont]*mult);
            resp+=aux;
            mult*=10;
        }
        contador++;
        if(contador>=1000000)
        {
            numeros[num][0]=0;
            resp=0;
        }
    }

}


int main()
{
    int N,cont,**numeros,*tam;
    char aux[200];

    cin >> N;

    if(N<0) exit(0);
    if(N>10000) exit(0);

    tam = new int[N];
    numeros = new int*[N];
    for(cont=0;cont<N;cont++)
    {
        numeros[cont] = new int[20];
    }

    for(cont=0;cont<N;cont++)
    {
        cin >> aux;
        tam[cont] = strlen(aux);
        if(tam[cont]>20)
        {
            exit(0);
        }

        for(int cont2=0;cont2<tam[cont];cont2++)
        {
            numeros[cont][cont2]=aux[cont2]-'0';
        }

        permuta(numeros,cont,tam[cont]);
    }

    system("cls");
    for(cont=0;cont<N;cont++)
    {
        for(int cont2=0;cont2<tam[cont];cont2++)
        {
            if(numeros[cont][0]==0)
            {
                if(cont2==0) cout << "0";
            }
            else if(numeros[cont][cont2]!=0) cout << numeros[cont][cont2];
        }
        if(cont!=N-1) cout << endl;
    }


    delete [] numeros;
    delete [] tam;

    return 0;
}

========================================================

please, help if you can =/

May be anybody knows, what is specific of the second test? All my examples work correctly, but the second test...... }:-/

Many times my code was reviewed and rewatched, but still WA7.
Could anybody help? What wrong with code? May be this algorithm gives not the optimal path?

int main()
{
    double r, a;
    std::cin >> r >> a;
    // first, walk to the edge of the island
    double s = r;
    // total angle of undiscovered edge
    const double a_left = 360.0 - 2.0*a;
    // hops count on 2*a "arc" line
    const int full_hops = (int)(a_left / (2.0*a));
    s += range(r, to_rad(2.0*a)) * full_hops;
    // remaining angle to hop
    double a_rem = a_left - full_hops * (2.0 * a);
    s += range(r, to_rad(a_rem));
    std::cout << std::fixed << std::setprecision(12) << s << std::endl;
}

я решаю через количество пересечений графиком  синуса ось ох, вроде алгоритм правильный а преодолеть третий тест не могу. помогите пожалуйста!!!

1) если число k простое, то результат: k/2 2
пример:
>31
15 2
2)если число k является степенью двойки, то результат: k 1
пример:
>1024
1024 1
3)остальные числа перебором(перебирать а1-первый элемент арифметичиской прогрессии) и через квадратное уравнение находить p.
P.S. AC    0.031 137 КБ

#include <iostream.h>
long int fac(long int k)
{
    int i,total=1;
    if(k==0)
    {
        return 1;
    }
    for(i=1;i<=k;i++)
    {
        total*=i;
    }
    return total;
}
int main()
{
    long int n,total=0,i;
    cin>>n;
    {
        if(n<14)
        {
            for(i=2;i<=n;i++)
    {
        total+=fac(n)/fac(n-i);
    }
            cout<<total<<endl;
        }
    }
    if(n>14&&n<17)
    {
        for(i=2;i<=n;i++)
    {
        total+=fac(n)/fac(n-i);
    }
        cout<<total<<endl;
    }
    if(n==14)
    {
        cout<<"87178291200"<<endl;
    }
    if(n==17)
    {
        cout<<"355687428096000"<<endl;
    }
    if(n==18)
    {
        cout<<"6402373705728000"<<endl;
    }
    if(n==19)
    {
        cout<<"121645100408832000"<<endl;
    }
    if(n==20)
    {
        cout<<"2432902008176640000"<<endl;
    }
    if(n==21)
    {
        cout<<"51090942171709440000"<<endl;
    }
    return 0;
}

WHY??????????

Is it really appropriate to translate 'целые числа' as 'whole numbers'?

#include <cstdlib>
#include <iostream>

//----------Funkcje----------------------------
long long nwd(long long a, long long b)
{
  if (b>=1) nwd(b, a%b);
  if (b=0) return a;
}


using namespace std;

//---------------Program------------------------------------
int main(int argc, char *argv[])
{
    int n;
    long long tab[1002]={0};
    //printf("Dla ilu liczb chcesz policzyc NWD?: \n");
    scanf("%d", &n);
    //printf("Podaj liczby: \n");
    for (int i=0;i<n;i++) scanf("%I64d", &tab[i]);
    long long wynik=tab[0];
    for (int i=0;i<n-1;i++) {
      wynik=nwd(tab[i],tab[i+1]);
      tab[i+1]=wynik;
    }

    //printf("NWD wynosi %I64d \n", wynik);
    printf("%I64d", wynik);

    system("PAUSE");
    return EXIT_SUCCESS;
}