please, help me...
my code:

#include <iostream>

using namespace std;



int main()
{
    int n,m[16],k;
    char c[48][20],v[16][20],ch[3][20];
    cin>>n;
    for(int i=0;i<n*3;i++)
        cin>>c[i];
    for(int i=0;i<n;i++)
    {
        cin>>k;
        m[i]=k;
    }
    k=(m[0]-1)*3;
    if((strcmp(c[k],c[k+1])<=0)&&(strcmp(c[k],c[k+2])<=0)){strcpy(v[0],c[k]);}
    if((strcmp(c[k+1],c[k])<=0)&&(strcmp(c[k+1],c[k+2])<=0)){strcpy(v[0],c[k+1]);}
    if((strcmp(c[k+1],c[k])<=0)&&(strcmp(c[k+1],c[k+2])<=0)){strcpy(v[0],c[k+1]);}
    for(int i=1;i<n;i++)
    {
        k=(m[i]-1)*3;
        if((strcmp(c[k],c[k+1])<=0)&&(strcmp(c[k],c[k+2])<=0))
        {
            strcpy(ch[0],c[k]);
            if(strcmp(c[k+1],c[k+2])<=0)
            {
                strcpy(ch[1],c[k+1]);
                strcpy(ch[2],c[k+2]);
            }
            else
            {
                strcpy(ch[2],c[k+1]);
                strcpy(ch[1],c[k+2]);
            }
        }

            if((strcmp(c[k+1],c[k])<=0)&&(strcmp(c[k+1],c[k+2])<=0))
            {
                strcpy(ch[0],c[k+1]);
                if(strcmp(c[k],c[k+2])<=0)
                {
                    strcpy(ch[1],c[k]);
                    strcpy(ch[2],c[k+2]);
                }
                else
                {
                    strcpy(ch[2],c[k]);
                    strcpy(ch[1],c[k+2]);
                }
            }

                if((strcmp(c[k+2],c[k])<=0)&&(strcmp(c[k+2],c[k+1])<=0))
                {
                    strcpy(ch[0],c[k+2]);
                    if(strcmp(c[k],c[k+1])<=0)
                    {
                        strcpy(ch[1],c[k]);
                        strcpy(ch[2],c[k+1]);
                    }
                    else
                    {
                        strcpy(ch[2],c[k]);
                        strcpy(ch[1],c[k+1]);
                    }
                }

        if(strcmp(v[i-1],ch[0])<=0)
        {
            strcpy(v[i],ch[0]);
        }
        else
        {
            if(strcmp(v[i-1],ch[1])<=0)
            {
                strcpy(v[i],ch[1]);
            }
            else
            {
                if(strcmp(v[i-1],ch[2])<=0)
                {
                    strcpy(v[i],ch[2]);
                }
                else
                {
                    cout<<"IMPOSSIBLE";
                    return 0;
                }
            }
        }

    }
    for(int i=0;i<n;i++)
    {
        cout<<v[i]<<endl;
    }
    return 0;
}

Am nevoie e ajutor, va rog io

Tags: dynamic programming

But most solution of the problem use a greedy algo

On the 11-(10-1)th of Febr(10-2)uary, 2006(10-3) the conte(10-4)st "Timus (10-5)Top Coders(10-6): First Ch(10-7)allenge" i(10-8)s held!
The exemple of this problem is wrong,isn't it?

Sorry , have found bug.

Edited by author 24.04.2009 03:03

I have WA on the test 25. Who can help me?

Interestingly enough the problem can be solved with simple simulation. Just simulate the process, choosing random directions and random initial positions while you are within the time limit and you will get accepted.
I really doubt this is the correct solution, so I was wondering what is the real one?

I get WA#1
here is my code

#include <cstdlib>
#include <iostream>

using namespace std;
int i, j, n, k, say, a[101];

int main(int argc, char *argv[])
{
            cin >> n >> k;

                for( i = 0; i < n ; i++ )
                    cin >> a[ i ];
                   if( n%k != 0)
                    say = n/k + 1;
        else
            say = n/k;

                for( j = 0; j < say; j++ ){
                        cout << a[ j ];
                        i = j + say;
                        while( i < n){

                            cout <<" "<< a[ i ];
                            i += say;
                        }
                        if( j < say-1 )
                        cout << endl;
                        }



    return 0;
}

Which of these formulas correct for this problem
1. M(A) + M(B) - M(AB)
2. M(A)*M(B/A)

Is empty string is a substring of the whole string?
Is whole string is a substring of the whole string?

Here's my code. It gets WA11.
Algo: the rightmost number of the current subarray[i..j]
 is a root of a subtree. The left branch includes those and only those numbers which are less than root; right branch -
numbers greater than root. So if we swap these branches in our array and process them recursively we'll get the desired answer.

Example:
 1 7 5 (left br.)  21 22 27 25 20 (right br.) 10 (root)

1 (lb) 7 (rb) 5 (rt)
empty (lb) 21 22 27 25 (rb) 20 (rt)
21 22 (lb) 27 (rb) 25 (rt)
21 (lb) empty (rb) 22 (rt)

result:
 27 21 22 25 20 7 1 5 10

proc "tree" does all the work.
del is the delimiter of the branches.
I've used the most primitive algo to swap
the subarrays to simplify the solution.


program parliament;

{$APPTYPE CONSOLE}

var n,i:integer;
    a,t:array[1..100000] of integer;


procedure tree(i,j:integer);
var q,del:integer;
begin
 if j>=i then begin
  del:=j-1;
  while (del>=i) and (a[del]>a[j]) do dec(del);
   for q:=del+1 to j-1 do
    t[q+i-del-1]:=a[q];
   for q:=i to del do
    t[q+j-1-del]:=a[q];
   for q:=i to j-1 do a[q]:=t[q];
   tree(i,j-del-1); tree(j-del,j-1);
 end;
end;


begin

 fillchar(t,sizeof(t),0);
read(n);
 for i:=1 to n do read(a[i]);
 tree(1,n);
 for i:=1 to n do write(a[i],' ');
end.

How much testcase there are in the input.

i've got wrong answer.but why?all works in 100% but i've got a wrong answer

Edited by author 28.09.2010 21:28

InFile - d.in
OutFile - d.out
1 second 4 MiB

find a number that is more than N and sum of numbers=S.

C++

I've got AC already.
I had WA on 11th test first, but then i changed the size of char array from 1000 to 1001... That changed ny WA on AC!! Guess, the true size of array is 1001 in 11th test case. Can post my solution...

Can you give me some test my program got WA

Here is my code:

#include <iostream>

using namespace std;

//long int _wants[200002];
//long int _nums[100001];
long int n;

long int *_wants;
long int *_nums;

int main()
{
   cin>>n;
   _wants = new long int[2*n];
   _nums = new long int[n];

   for (long int i=0; i<n; i++) cin>>_wants[i];

   for (long int i=0; i<n; i++)
   {
      _nums[i]=_wants[i];
      _wants[i]-=i+1;
      _wants[i+n]=_wants[i]-n;
   }

   long int _max=_wants[0];
   long int _pos=1;
   long int _count=1;
   for (long int j=0; j<n; j++)
   {
      if (_wants[j]>-n)
      {
         _count=1;
         for (long int i=j+1; i<2*n; i++)
         {
            if (_wants[i]==_wants[j])
            {
               _wants[i]=-n;
               _count++;
            }
         }
         _wants[j]=_count;
         if (j==0) _max=_wants[j];
         else if (_wants[j]>_max)
         {
            _max=_wants[j];
            _pos=j-(_nums[j])+2;
         }
      }
   }

   if (_pos<=0) _pos+=n;

   cout<<_pos<<endl;
   return 0;
}

My algo is following: we take the input twice, like this: for "4 1 2 3" - "4 1 2 3 4 1 2 3". For each standing in array of meanings we count arr[i]-i . For students standing in a right way to answer counting gives same results. Then we count a number of each difference in our array of 2*n elements, but only for meanings in left half of arr (and write it to the beginning of the arr). After that we will have the length of the longest sequence and its beginning position. There's no problem to say who must be first.

I found out that for n=99999 there's a TL. But why? This algo is enough fast...

Edited by author 25.10.2010 13:15