My greedy algorithm have 'accepted', but gives wrong answer for this test:

8
a b c
d e f
g i k
b l m
l m i
i k c
d e c
e f k

The number of ways to tile an MxN rectangle with 1x2 dominos is
2^(M*N/2) times the product of
{ cos^2(m*pi/(M+1)) + cos^2(n*pi/(N+1)) } ^ (1/4)
over all m,n in the range 0<m<M+1, 0<n<N+1.

I have found this formula in internet and I would like to
know is there a way to use it for solving this problem?

My first solution printed 2, if first player wins and the number of rocks is even and printed 1 if it's odd. And this solution got WA9. After printing "some variable" mod 3 the solution got AC. But why did my first idea fail?

I realize my idea on Java and Pascal.
On java i got TLe on 22 test, but on Pascal i got AC with time 0.069.
Not good when problem depends on the language.

It's not me posted if you can remove it? Thanks!

Edited by author 24.03.2013 19:47

I test my code at my computer,I got a test which is filled by period string "abcde" and its length is 4000,and my program run only 0.25s.
My computer is:
Memory:3GB
System:Windows XP
CPU:1.66GHZ
But I got tle at #32...Why???
Here is my code.
var
        i,j,xx,ox,t,l:longint;
        s:ansistring;
        f,x:array [1..4010] of longint;
        o:array [0..4010] of boolean;
function pdhw(l,r:longint):boolean;
var
        i:longint;
begin
        if l=r then exit(true);
        for i:=l to (l+r)>>1+1 do
          if s[i]<>s[r+l-i] then exit(false);
        exit(true);
end;
begin
        readln(s);
        l:=length(s);
        for i:=1 to l do
        begin
          f[i]:=maxlongint;
          if pdhw(1,i) then f[i]:=0
          else for j:=1 to i-1 do
                 if (f[i]>f[j]+1)and(pdhw(j+1,i)) then begin
                   f[i]:=f[j]+1;
                   x[i]:=j;
                 end;
        end;
        writeln(f[l]+1);
        xx:=l;
        repeat
          ox:=xx;
          xx:=x[xx];
          if ox=l then o[xx+1]:=true
          else o[xx+1]:=true;
        until xx=0;
        o[1]:=false;
        for i:=1 to length(s) do
          if o[i] then write(' ',s[i])
          else write(s[i]);
end.

AC at 0.015 145 KB :)

How come i can write very simple counter to be AC this without any algorithm?

what the algo of this problem? please^_^

Could anyone help me to programming this problem?
1197. Lonesome Knight

If you're outputting C or C++ codes, then the followings might help:

1. Each line in your program can't be too long. (I chose to add a line break every 950 characters.) Having lines with length exceeding the compiler's limit will make you WA on test 1.

2. Lengths of any string constant (or array?) should be shorter (no longer?) than 65536 bytes. This is yet another unreasonable compiler limitation. Going over the length limit will make you WA on test 3.

I think the statements of this problem must have a full description of compilers used to compile outputs of solutions, otherwise it's nearly impossible to find out what does "WA1" mean. Not to mention that it's just plain wrong to use some magical non-standard-compatible compiler, that accepts "<iostream.h>" and "cout<<i" without using "std" namespace and so on.

Please add to statements hints about code formatting your compiler accepts, don't turn this wonderful problem to boring technical problem "Archiver or Satisfy Our Compiler"

I think, it doesn't make any sense to create a difficult and tricky solution, to use e, etc. At first I thought, that bruteforce algorithm will be TLE, but it's AC 0.187 (a bit long, but not even close to 2 seconds). So, try bruteforce.

Edited by author 18.03.2013 20:26

Edited by author 18.03.2013 20:26

Edited by author 18.03.2013 20:26

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int main()
{
      #ifndef ONLINE_JUDGE
            freopen("input.txt", "rt", stdin);
            freopen("output.txt", "wt", stdout);
            #endif

    int n,m,y;
    long double x;
    long double time;
    vector< long double >vec;

    cin >> n >> m >> y;
    if( n <= 0 || n >= 999)
        exit(1);
    if( m <= 1 || m >= 999)
        exit(1);
    if( y <= 0 || y >= 99)
        exit(1);

    for( x = 0; x < m; x++)
    {
        time = pow(x, n);
        if( (unsigned long)time % m == y)
            vec.push_back(x);
    }
    if( vec.size() == 0)
        cout << "-1";

    else
    {
    for( unsigned int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << " ";
    }
    }

    return 0;
}

Maybe it's only me who is of this opinion, but the statement of the problem is really equivocal. The expressions "If Leonid is wrong in his assumptions" and "Leonid assumes that the work experience of each pilot is in the range from 1 to 50 years" obviously led me to the misunderstanding of the problem itself, as I supposed that if the graph is disconnected the answer would be -1, because Leonid might be wrong in his assumptions in case if the difference in ages between pilots from two different connected components exceeds 50 years. Therefore it would be better to say "It is known that the work experience of each pilot is in range from 1 to 50 years" as it makes people understand that this is a required restriction.

I would be very grateful if authors avoided such tricky and equivocal expressions in their statements. Thank you for the time spent in order to look through this post.

What is the trick of problem 7?
I tried a file of 250000 numbers 2^31-1 and got the answer 2147483647.0
So this is right.
I tried 1 0 and got 0.0
There was no TLE but a wrong answer.

I've tested all inputs from other themes, but still got wa in 3rd. Help, please!
The algorithm based on the half-invariant idea.

#include <iostream>
#include <fstream>
#include <string>
#include <math.h>
#include <sstream>
using namespace std;


int main(){
    int n, m;
    cin >> n >> m;
    bool **e = new bool*[2*n];
    for (int i=0; i<2*n; i++){
        e[i] = new bool[2*n];
        for (int j=0; j<2*n; j++){
            e[i][j] = false;
        }
    }
    int v1, v2;
    for (int i=0; i<m; i++){
        cin >> v1 >> v2;
        int tmp;
        if (v1 > v2){
            tmp = v1;
            v1 = v2;
            v2 = tmp;
        }
        e[v1-1][v2-1] = true;
        e[v2-1][v1-1] = true;
    }
    int inv=0;
    for (int i=0; i<n; i++){
        for (int j=i+1; j<n; j++){
            if (e[i][j]) inv++;
            if (e[n+i][n+j]) inv++;
        }
    }
    int *t =new int[2*n];
    for (int i=0; i<2*n; i++){
        t[i] = i;
    }
    while (inv > 0){
        int s = 0;
        for (int i=0; i<n; i++){
            int i_out = 0;
            int i_in = 0;
            for (int k=0; k<n; k++){
                if (e[t[i]][t[k]] || e[t[k]][t[i]]){
                    i_in++;
                }
                if (e[t[i]][t[k+n]] || e[t[k+n]][t[i]]){
                    i_out++;
                }
            }
            for (int j=n; j<2*n; j++){
                int j_out = 0;
                int j_in = 0;
                for (int k=0; k<n; k++){
                    if (e[t[k+n]][t[j]] || e[t[j]][t[k+n]]){
                        j_in++;
                    }
                    if (e[t[k]][t[j]] || e[t[j]][t[k]]){
                        j_out++;
                    }
                }
                if (e[t[i]][t[j]] || e[t[j]][t[i]]){
                    j_out--;
                    j_out--;
                }
                if (i_in + j_in > i_out + j_out){
                    s++;
                    inv -= (i_in + j_in - i_out - j_out);
                    int tmp = t[i];
                    t[i] = t[j];
                    t[j] = tmp;
                }
                if (s == 1) break;
            }
            if (s == 1) break;
        }
        if (s == 0){
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }
    string tour1, tour2;
    tour1 = "";
    tour2 = "";
    for (int i=0; i<n; i++){
        for (int j=i+1; j<n; j++){
            if (t[i]>t[j]){
                int tmp = t[i];
                t[i] = t[j];
                t[j] = tmp;
            }
            if (t[i+n]>t[j+n]){
                int tmp = t[i+n];
                t[i+n] = t[j+n];
                t[j+n] = tmp;
            }
        }
    }
    for (int i=0; i<n; i++){
        std::ostringstream ostr;
        ostr << (t[i]+1);
        std::string theNumberString = ostr.str();
        tour1 = tour1 + theNumberString + " ";
    }
    for (int i=0; i<n; i++){
        std::ostringstream ostr;
        ostr << (t[n+i]+1);
        std::string theNumberString = ostr.str();
        tour2 = tour2 + theNumberString + " ";
    }
    cout << tour1 << endl << tour2 << endl;
    return 0;
}

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

int main()
{
        unsigned long long int in[320000];
        int count = 0;
        while (scanf("%llu",&in[count]) != EOF) count++;
        while (count > 0){
                printf("%.4Lf\n",sqrtl(in[count-1]));
                count--;
                }
        return 0;
}

Edited by author 21.03.2013 17:19

I am getting wrong answer for test case 12 again and again. Any idea where can be the problem or what can be the test case?