After my wrong AC tests were added
(Thanks to Fyodor Menshikov).
Many authors lost AC.The problem was with division to negative divisors.
(Example)
1/2
/
-1/3
Good luck!

My answer for the sample is
3
3 1 4 2
3 2 3 4
4 1 3 4 2
or
3
3 1 4 2
4 1 3 4 2
3 2 3 4
Can anyone give me the 1st test?

I have no idea what's wrong...
I am using DFS (something like euler-cycle detection); checking for self-loop edges; output format is right, tho it returns little bit different for sample test:
3
3 1 2 4
4 1 2 4 3
3 2 4 3

Please, any ideas about wa#1?

oh, i forgot to add that i am doing dfs for every connected component separately!

Edited by author 15.06.2010 03:05

Edited by author 28.08.2011 02:03

 var
  a:array[0..1000,1..3] of real;

  x,y,x0,y0:real;
  n,i,j,k:integer;
begin
  readln(x0,y0);
  readln(n);
  fillchar(a,sizeof(A),0);
  for i:=1 to n do begin
    readln(x,y,a[i,3]);
    x:=x-x0;y:=y-y0;
    a[i,1]:=x;a[i,2]:=y;
  end;
  for i:=1 to n-1 do for j:=i+1 to n do if a[i,1]*a[j,2]-a[i,2]*a[j,1]
>0 then begin
    a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];
  end;
  writeln(0);
  for i:=1 to n do begin
    writeln(a[i,3]:0:0);
  end;
  writeln(0);
end.

if you have MLE just change all int's to short's :)

i got wa on test 7
my answer 3 9
oficial answer 3 5
3 5 can be optain only if we move(not remove or op 6) the two pegs of shelf nr 8 and cut 2 from the plank
none of the 6 op alows us to do so.
Am I wrong?

i use O(n^4) and got AC in .062 s, if you have a better algo, plz explain to me, plz ,plz, plz ....

sorry for my poor english.
GOOD LUCK!!!

No DP! Just 2 BFS for each connected component.

I was completely mad of it!
 (By the way ,my English is poor.)

Can anyone help me?
This is my code wich has Crash on the 4th test:
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Globalization;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            System.Threading.Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;
            NumberFormatInfo nfi = NumberFormatInfo.InvariantInfo;
            String[] str = Console.ReadLine().Split(new char[] { ' ', '\n', '\t' }, StringSplitOptions.RemoveEmptyEntries);
            int n = int.Parse(str[0], nfi);
            int r = int.Parse(str[1], nfi);
            double length = 0;

            if (n == 1)
            {
                length += r * Math.PI * 2;
                Console.Write(String.Format(nfi, "{0:F2}", length));
                return;
            }
            double[][] mat = new double[n][];
            for (int i = 0; i < n; i++)
                mat[i] = new double[2];

            for (int i = 0; i < n; i++)
            {
                String[] str1 = Console.ReadLine().Split(new char[] { ' ', '\n', '\t' }, StringSplitOptions.RemoveEmptyEntries);
                mat[i][0] = Double.Parse(str1[0], nfi);
                mat[i][1] = Double.Parse(str1[1], nfi);
            }

            for (int i = 0; i < n; i++)
            {
                if (i == n - 1)
                {
                    length += Math.Sqrt((mat[i][0] - mat[0][0]) * (mat[i][0] - mat[0][0]) + (mat[i][1] - mat[0][1]) * (mat[i][1] - mat[0][1]));
                    break;
                }
                length += Math.Sqrt((mat[i][0] - mat[i + 1][0]) * (mat[i][0] - mat[i + 1][0]) + (mat[i][1] - mat[i + 1][1]) * (mat[i][1] - mat[i + 1][1]));
            }
            length += r * Math.PI * 2;

            Console.Write(String.Format(nfi, "{0:F2}", length));
        }
    }
}

S - it is a line
Create a matrix
F[i][j] is a decision with i on j a symbol
If S[i] it is a closing bracket, F[i][j] =1 + F[i+1][j]
If S[i] a closing bracket that is two cases:
1) We add a closing bracket - 1 + min(F[i+1][k] + F[k+1][j]), where i<k<=j
2) Is in line closing - min(F[i+1][k-1], F[k+1][j]), where S[k] = S[i] and i<k<=j

Why i have CE http://acm.timus.ru/ce.aspx?id=3325544

Please Help me, i get WA #11 many times.
My solution in Java
1) For each "phone number" get list neighbours
2) use PriorityQueue to find shortest path
3) print path
For calculations with "phone number" use Long
for init max_time use 10^12
I can send my solution on mail.
Sorry for my english.

well, i like prim better

Why wrong answer???
#include <iostream>
#include <cmath>
#include <sstream>
#include <vector>
#include <iomanip>
using namespace std;
int main()
{
    double ans;
    string s;
    vector <double> vect;
    int i;
    i=0;
    while(cin>>s){
    stringstream ss;
    ss<<s;
    ss>>ans;
    vect.push_back(sqrt(ans));

}
for(int i=vect.size();i>=0;i--)
cout<<setprecision(5)<<vect[i]<<endl;
return 0;
}

#include<iostream>
using namespace std;
const int maxn=105;
int count[maxn]; int g[maxn][maxn]; int n;int q; int cost[maxn][maxn]; int f[maxn][maxn]; int visit[maxn];
void init( )
{
            cin>>n>>q;
            for(int i=1;i<n;i++)
            {
                        int a,b,c;
                        scanf("%d %d %d",&a,&b,&c);
                        g[a][++count[a]]=b;
                        cost[a][b]=c;
                        g[b][++count[b]]=a;
                        cost[b][a]=c;
            }
            //memset(f,-10000,sizeof(f));
}
void dfs(int x)
{
            visit[x]=1;
            if(count[x]==0)
            {

                        return ;
            }
            for(int i=1;i<=count[x];i++)
            {
                        int child=g[x][i];
                        if(visit[child]==0){
                                    dfs(child);
                        for(int j=q;j>=0;j--)
                                    for(int k=q-j-1;k>=0;k--)
                                    {
                                                f[x][k+j+1]=max(f[child][k]+f[x][j]+cost[x][child],f[x][k+j+1]);

                                    }
                        }
            }
}
void print( )
{
            cout<<f[1][q]<<endl;
}
int main( )
{
            freopen("in.txt","r",stdin);
            init( );
            dfs(1);
            print( );
            return 0;
}