Thanks for the site problem, a very interesting and exciting)) Passed with PD + Segment tree.

Edited by author 16.06.2012 05:41

Edited by author 16.06.2012 05:42

So my algo is to have a vector of pairs(value and index),
sort them(used usual <algorithm> sort), and then binary
searched each request - first by value, and if value was
correct, by index.

The program ACed, on G++11 compiler with 0.921 time. when
I removed the inclusion of <cstdlib>, it ACed with
0.859(and same on G++14). But funny thing is, on
Visual C++ 2010, it ACed with 0.593s time, which is
astounding(to me at least) because the difference is
quite noticeable(25% drop).

So I guess if you are getting TLE, it's worth a try
to run it with Visual C++ - you might get a pass this way.

Edited by author 17.01.2015 15:10

My Accepted solution #6069000 will fail if you add all permutations of test 32 as separate tests.

Can any one see what's the issue?

        static void Main(string[] args)
        {
            string input = Console.In.ReadToEnd();

            var valid = new char[] { '1', '2', '3', '4', '5', '6', '7', '8', '9', '0' };
            var sb = new StringBuilder();
            var numbers = new Stack<string>();
            for (int i = 0; i < input.Length; i++ )
            {
                if(valid.Contains(input[i]))
                {
                    sb.Append(input[i]);
                }
                else if(sb.Length > 0)
                {
                    numbers.Push(sb.ToString());
                    sb.Clear();
                }
            }

            NumberFormatInfo nfi = NumberFormatInfo.InvariantInfo;
            foreach(var n in numbers)
            {
                double sqrt = Math.Sqrt(double.Parse(n, nfi));
                Console.WriteLine(string.Format(nfi, "{0:F4}", sqrt));
            }

        }

Hello everyone. I always receive time limit on Test №21. Could you give any hints? Maybe  this task requires special data structure (I try to represent tree as list of edges or adjacency list) or there is interesting algorythm? Thanks for reading.

* Clarification in problem statements: For any pair of crossroads no two segments of the same category connect these crossroads.
* Tests not satisfing this condition are corrected.
* The first test is changed to the sample from the problem statements.
* New time limit is 2.5 seconds (old time limit was 3 seconds).
* New memory limit is 64 MB (old memory limit was 16 MB).
* New tests are added

All solutions are rejudged. More than 100 authors lost AC during this rejudge.

Give me some test. Or give me test 10!

Edited by author 14.02.2007 18:59

Is there a class or sth that can both read integers and single chars? Somebody please give me some example code. Thanks!

Please help me .this code failed at test case 5
#include <stdio.h>
int main() {
int n,k;
scanf ("%d\n%d" ,&n,&k);
int l, pos;
 l = n % 2 ;

if ( l != 0 || n < 1 || k < 1 || k > n     || n > 50 )
{
   printf("invalid input");
}
else
{
   if (n != 2 )
   {
 if ( k <= n/2  )
   {
   pos  = n/2 - k ;
   printf("%d", pos);
   }
   else
   {
   pos = k - ((n/2) + 1 );
    printf("%d", pos);
   }
    }
}
if ( n == 2 )
{
  pos = 0;
  printf("%d", pos);

}
return 0;
}

used:
...
for(i=1;i<=S;i++)
for(j=i;j<=S;j++)
...
But the result is 'Time limit exceeded'.  Please help, why 'Time limit exceeded'?

Hi, guys!
Can't move throw #11 test. Need help.
I just have build tree, and in every step removing smallest leaf.
At last, I count sum of left leaf's weight and print it.
But, algorithm don't pass at #11 test.
Thanks

what is test #3; 3 or what?
don't you think that when n>0 answer is (n*(n+1))/2?
                     when n<0 answer is (-((n*(n-1))/2-1))?
                     when n=0 or n=1  answer is 1  ?



Edited by author 14.01.2015 14:52

please change the wording of the statement:
"there should be at most k Rocks of pairwise different colors among the Rocks taken from the Cave" would be much better read if it is changed to "there should be at most k Rocks of different colors among the Rocks taken from the Cave."

in other words, the word 'pairwise' should be removed to make the statement clear.

Edited by author 14.01.2015 05:20

Edited by author 14.01.2015 05:21

I tried greedy approach during the contest, but got failed.
Idea was in bombing the city (even if it has been already destroyed) with the most number of remained cities in a radius. But WA#14.

Please, would you share any AC idea?

is file handling is necessary in this problem or not?..

for input "10000 9999 10" my prog gives "1.(0001)".
But I have WA#1.
help me!

Edited by author 25.12.2006 11:40

For the case,
2794 6083 23

2794/6083, I get
0.4593128390596745027124 (in decimal)

But when I convert 0.ACM from base 23, I get
0.459275088353744 (in decimal)

Where is the mistake ?

#include <iostream>
using namespace std;
int main()
{
    int n ;
    cin>>n ;
    int f,s,l ;
    for(int i=0;i<n;i++)
    {
        cin>>s ;
        if(i==0)
        {
            l=s ;
            f=1 ;
        }
        else if(l!=s)
        {
            cout<<f<<" "<<l<<" " ;
            f=1 ;
            l=s ;
        }
        else
        f++ ;

    }
    cout<<f<<" "<<l ;
}

1. If we regard the start airport as the root,it is clear that the graph is a tree.
2. If start from all the leaf airport that from one airport could win, start from this airport suerly will lose. Otherwise,he could win.
3. We use a flag to record start from one airport will win or not.Just DFS to obtain all flag.
In this way,you could get AC in O(e).
Is there any better way to solve this problem?
I think the answer is yes.
So,could you write down your thought?

Hi, What is the test 9??