First, Anatoly's tip helped me (see "WA#4 - I don't know why" thread).

Another one tip for those receiving WA with "swear correct algo": I've multiplyed whole input data to some koef (tried 500, 800) and divided result by this koef before printing — got AC while without it got WA on 8-th test. It's all about error of calculations.

And, of course, I've used double, not float.

AB, AC, BC - Vectors.
r - Radius.
Arctangent(y, x) - Coprocessor function FPATAN, calculates an angle between vectors A(x, y) and X(1, 0)(using y and x coordinates of the A point).

My algorithm:

d = Abs(VectorMultiply(AC, BC)) / AB
if (d >= r) then Write(Length(AB))
else begin
    s1 = Sqrt(Length(AC) * Length(AC) - r * r)
    angle1 = Arctangent(Sqrt(Length(AC) * Length(AC) -
             d * d), d) - Arctangent(s1, r);
    s2 = Sqrt(Length(BC) * Length(BC) - r * r)
    angle2 = Arctangent(Sqrt(Length(BC) * Length(BC) -
             d * d), d) - Arctangent(s2, r);
    s = r * (angle1 + angle2)
    Write(s1 + s + s2)
end

-----

Am I wrong?

Can it be solved with monte carlo alogrithm?
I used 10^6 points for checking and got WA at test #10. Then changed number of points to 10^5 and still get WA#10.

Edited by author 19.10.2004 02:09

1000 => 501501000
500  => 62875500
333  => 18629685
1    => 3
3    => 30
4    => 60
But Wa#5

Edited by author 28.10.2006 17:09

Can somebody tell me the possible reason of this WA?
Or at least what figure is in that test?

I would be very thankful!

3 2

please, give me some tests.

give me some tests

Please, give me test №8

i tried to solve this problem with dp. O(N*2) time and O(N) memory:
here is my code
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int  n;

string s,t;

string Longest_common_substr(void)
{

    int place;

    int longest=0;

    vector<int> m(n);

    for(int i=0;i<n;i++)
    {
        for(int j=n-1;j>=0;j--)
        {
            if(s[j]==t[i])
            {
                if(j!=0)m[j]=m[j-1]+1;
                else m[j]=1;
            }
            else m[j]=0;

            if(m[j]>longest)
            {
                longest=m[j];
                place=j-longest+1;
            }
            if(longest==n)return s.substr(place,longest);
        }
    }
    if(longest==0)return "";
    else return s.substr(place,longest);



}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie();
    cin>>n;
    cin>>s;
    cin>>t;
    cout<<Longest_common_substr()<<endl;
    return 0;
}

can you please suggest any modifications?

trick?

I have WA 1 but on my computer all ok. Is first test not like in statement?

num = int(input())

arr = []

for i in range(num):
    arr.append([])
    for j in range(num):
        arr[i].append([])

check = 1

for i in range(num-1,-1,-1):
    x = 0
    y = i
    while y != num:
        arr[x][y] = check
        check += 1
        y += 1
        x += 1

for i in range(1,num,1):
    x = i
    y = 0
    while x != num:
        arr[x][y] = check
        check += 1
        y += 1
        x += 1

string = ''

for i in range(num):
    for j in range(num):
        string += (str(arr[i][j]) + ' ')
    print(string)
    string = ''

num = int(input())
arr = []
for i in range(num):
    temp_arr = input().split(' ')
    arr.append(temp_arr)
string = ''
for i in range(num):
        k = i
        j = 0
        while k >= 0:
                string += (arr[k][j] + ' ')
                k -= 1
                j += 1
for i in range(1,num,1):
        k = num - 1
        j = i
        while j != num:
                string += (arr[k][j] + ' ')
                k -= 1
                j += 1
print(string)

Edited by author 27.07.2013 13:58

Edited by author 27.07.2013 13:58

The problem say that "It is guaranteed that during the experiment each time a coin was to be removed the stack was not empty."
But when I submit such a brute force code:
--------------------
        if (x > 0) a[t++] = x;
        else if (x == 0) {
            if (t + t < maxn) {
                copy(a, a + t, a + t);
                t += t;
            }
        }
        else printf("%d\n", a[--t]);
--------------------
It crashed at #42. Then, I modified the last "else branch" into:
--------------------
        else if (t) printf("%d\n", a[--t]);
--------------------
I got WA at #42.

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
char v[53];int ch[53];
char vi[53][5],*punt=NULL,vf[53],vc[53],vp[53],*a,vt[53],chr[3];
int maxl=0,maxt=0,k,b,max2,l=0;
int n,j=0,i,ind;

main()
{
    gets(v);
    n=strlen(v);
    if(n==1){cout<<v;}
    else{



        for(i=0;i<n-1;i++)
            {   // carga inicial
               vi[i][0]=v[i] ;
               vi[i][1]=v[i+1] ;
               ch[i]=0;


            }

        for(i=0;i<n-1;i++)
        {
            punt=strstr(v,vi[i]);


            if(punt!=NULL)
                {
                    ch[punt-v]++;


                }
        }
        for(i=0;i<n-1;i++)
        {

            if(ch[i]>maxt)
                    {
                        maxt=ch[i];
                        ind=i;

                    }



        }
        strcpy(vc,vi[ind]);
        strcpy(vp,v);

        punt=strstr(v,vi[ind]);
        i=0;
 strcpy(vf,vi[ind]);
        if (maxt!=0)
        {  while(1)

        {




            b=1;

            punt=strstr(v,vf);
            chr[0]=punt[2+l];

            strcat(vf,chr);



           k=2+l;
           k++;
           l++;
           if(l==strlen(punt))break;
           max2=0;
           strcpy(vp,v);
           while(1)
               {
                    punt=strstr(vp,vf);



                    if(punt!=NULL)
                        {

                            j=strlen(punt);

                            for(i=0;i<j-1;i++)
                            {
                                vp[i]=punt[i+1];
                            }
                            vp[i]='\0';



                            max2++;
                            if (max2>=maxt)
                            {
                                maxt=max2;
                                strcpy(vc,vf);
                                b=0;

                            }




                        }
                        if(punt==NULL)break;


                }
                if(b==3) break;


        }





        }
cout<<vc;

    }}

New tests were added to the problem. First tests were replaced with examples from the problem statements. 106 authors have lost AC after the rejudge.

I have used manacher'a algorithm   and tried all the test cases discussed in these discussions and getting correct solution....
I have used manacher for even and odd palindromes separately and found the longest and if longest comes again... as in the same length..take the smaller start..
but now,... I got WA #7 ...I initially faced some problem in compilation too..please suggest some test case

P.S. : m doing while(getline(cin,string))  and also tried while(cin>>string)
is something to be done here...please suggest

What in test #8?

Edited by author 25.07.2013 00:58