[code deleted]
My first submit got WA#8, my second WA#9, my third got WA#10 of course. I  am going so straight,  so incrementally.  Maybe author made tests in such an amazing increasing-difficulty way.

Edited by moderator 03.12.2019 21:46

I compiled my code on ideone and there I have 0.4 sec for test 1800 10
So I have tle 9. Maybe there are stronger tests?
By the way my program use vectors in long arithmetics. Should I use strings in it?

Edited by author 08.05.2017 22:14

WTF?! I have RE4(Access Violation). I don't understand why?

Use ternary search.

So,  I just wrote solution with C long double and got WA #5 (Laplacian).
Then I just rewrote it in Python with decimal.py and got WA...#3! Then I started to add more precision to decimal and got TLE #3.
Yeah, I use some epsilon constant and add it to determinant  before convert determinant to integer and get its modulo  10**9.

import sys

def reverse(i):
    if len(i) == 1:
        return i
    else:
        return i[len(i)-1]+reverse(i[:len(i)-1])

def getReverseLine(s):
    start = 0
    for i in range(len(s)):
        if (ord(s[i]) < 123 and ord(s[i]) > 64) and (ord(s[i]) < 91 or ord(s[i]) > 96):
            if i == len(s)-1:
                if start < i:
                    s = s.replace(s[start:i+1], reverse(s[start:i+1]))
        else:
            if start < i:
                s = s.replace(s[start:i], reverse(s[start:i]))
                start = i+1
            else:
                start += 1
    return s

lines = []
while True:
    line = sys.stdin.read()
    if line == '':
        break
    lines.append(getReverseLine(line))

text = '\n'.join(lines)

print text

3
6 1 2 5 7 5 2 1
4 1 4 7 4 1
5 2 3 6 5 4 2
my solution:
15 2 5 7 5 2 1 2 3 6 5 4 7 4 1 4 2

2
4 1 2 3 4 1
4 1 2 3 4 1
my solution:
4 1 2 3 4 1

4
1 1 1
1 1 1
1 1 1
1 1 1
my solution:
1 1 1

Are there any test cases for debugging?

Here is my program,I have taken WA on the test of 2, I think it is correct,please tell me what is wrong,please if you can..

program fillword;
var a:array[1..10] of string;
    b,k:array[1..100] of string;
    i,j,n,m,p,t:integer;
    ch:char;
    l,r:string;
begin
 read(n,m,p);
 readln;
 for i:=1 to n do
  readln(a[i]);
 for j:=1 to p do
  readln(b[j]);
 for i:=1 to p do
  for j:=1 to n do
   if b[i]=a[j] then begin t:=t+1; k[t]:=b[i];  break; end;
 for i:=1 to t do
  begin
   r:='';
   l:=k[i];
   for ch:='A' to 'Z' do
    for j:=1 to m do
     if ch=l[j] then r:=r+ch;
   writeln(r);
  end;
end.

BTW: I have used self-implemented high-precision longint to solve this problem.

1000 0 0 -1000 0 0 1000 1000
VISIBLE

1000 -0.000001 0 -1000 0 0 1000 1000
INVISIBLE

1000 0 -0.000001 -1000 0 0 1000 1000
INVISIBLE

1000 0 0.000001 -1000 0 0 1000 1000
VISIBLE

1000 -0.000001 0.000001 -1000 0 0 1000 1000
VISIBLE

1000 -1000 999.999999 -1000 0 0 1000 1000
INVISIBLE

1000 -1000 999.999999 -999.999999 0 0 1000 1000
VISIBLE

-999.999999 -1000 1000 999.999999 0 0 1000 1000
VISIBLE

1 2 1 0 0 0 0 1
VISIBLE

1.000001 2 1 0 0 0 0 1
VISIBLE

0.999999 2 1 0 0 0 0 1
INVISIBLE

1000 0 1000 -0.000001 0 0 0.000001 1000
VISIBLE

1000 0 1000 -0.000002 0 0 0.000001 1000
VISIBLE

1000 0 1000 -0.000003 0 0 0.000001 1000
INVISIBLE

var
  s: array[1..50] of string;
  si, i1, i, c: integer;
  input, output: text;

begin
  {$IFNDEF ONLINE_JUDGE}
  assign(input, 'input.txt');
  reset(input);
  assign(output, 'output.txt');
  rewrite(output);
  {$ENDIF}
  while not seekeof(input) do
  begin
    inc(si);
    read(input, s[si]);
  end;
  c := 1;
  for i := 1 to si do
    for i1 := 1 to length(s[i]) do
    begin
      if c = 0 then s[i][i1] := lowercase(s[i][i1]);
      if (c = 1) and (s[i][i1] <> ' ') and (s[i][i1] <> '-') and (s[i][i1] <> ':') then c := 0;
      if (s[i][i1] = '?') or (s[i][i1] = '.') or (s[i][i1] = '!') then c := 1;
    end;

  for i := 1 to si do
    writeln(output, s[i]);
  {$IFNDEF ONLINE_JUDGE}
  close(input);
  close(output);
  {$ENDIF}
end.

check this.
http://acm.timus.ru/rating.aspx?space=1&num=1102

divide  the matrex into three divisions >> above the diagonal >>> the diagonal>>under the diagonal
simulate more than matrix for insure your answer

All mentioned solutions cause TLE.

Нашел ошибку. =)

Edited by author 12.05.2014 09:33

Is this a problem for counting the number of shortest common superstrings ???

Python3: TLE #8
Python2: AC 0.8 sec
Code is the same.
(Pseudo-vector product)

Edited by author 28.04.2017 17:08

In case anybody wants to see implementation Link is here http://paste.ubuntu.com/13082792/.

Could anyone help me?

Написал лобовой вариант и всё равно WA10! Значит, вывод не верен. Кто может подсказать, как выводить ответ?(Форум не помог)

#define _CRT_SECURE_NO_WARNINGS
#define mk make_pair

#include <string>
#include <map>
#include <iostream>
using namespace std;

typedef map <string, int> mymap;

const int nmax = 100005;

mymap t[4 * nmax];
mymap answer[nmax];
string word[nmax];
int cnt[nmax];
int n, m;
string w_print[11];
int c_print[11];

mymap Search(int L, int R);
int BinaryDown(int L, int R, string s);
int BinaryUp(int L, int R, string s);
mymap Optimal(mymap map1, mymap map2);
void Print(mymap M);
void QSort_W(int L, int R);
void QSort2(int L, int R);
void QSort3(int L, int R);

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> word[i] >> cnt[i];
    QSort_W(1, n);
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        string s;
        cin >> s;
        int L, R;
        L = BinaryDown(1, n, s);
        R = BinaryUp(1, n, s);
        answer[i].clear();
        if (L != -1 && R != -1) answer[i] = Search(L, R);
    }

    for (int i = 1; i <= m; i++)
    {
        Print(answer[i]);
        if(i!=m) cout<<endl;
        if(!(answer[i].empty()) && i!=m) cout<<endl;
    }

    return 0;
}

mymap Search(int L, int R)
{
    mymap res;
    res.clear();
    for(int i=L;i<=R;i++)
    {
        mymap x;
        x.insert(mk(word[i],cnt[i]));
        res=Optimal(res,x);
    }
    return res;
}

void Print(mymap M)
{
    int n = 0;
    for (mymap::iterator it = M.begin(); it != M.end(); it++)
    {
        w_print[++n] = it->first;
        c_print[n] = it->second;
    }
    if (n == 0) return;
    QSort2(1, n);
    for (int i = 1; i <= n;)
    {
        int j = i + 1;
        while (j <= n && c_print[j] == c_print[i]) j++;
        QSort3(i, j - 1);
        i = j;
    }
    for (int i = 1; i<n; i++) cout << w_print[i] << endl;
    cout << w_print[n];
}

void QSort2(int L, int R)
{
    int i, j;
    int X = c_print[(L + R) / 2];
    i = L, j = R;
    while (i <= j)
    {
        while (c_print[i] > X) i++;
        while (c_print[j] < X) j--;
        if (i <= j)
        {
            string Y = w_print[i]; w_print[i] = w_print[j]; w_print[j] = Y;
            int k = c_print[i]; c_print[i] = c_print[j]; c_print[j] = k;
            i++;
            j--;
        }
    }
    if (L < j) QSort2(L, j);
    if (i < R) QSort2(i, R);
}

void QSort3(int L, int R)
{
    int i, j;
    string X = w_print[(L + R) / 2];
    i = L, j = R;
    while (i <= j)
    {
        while (w_print[i] < X) i++;
        while (w_print[j] > X) j--;
        if (i <= j)
        {
            string Y = w_print[i]; w_print[i] = w_print[j]; w_print[j] = Y;
            int k = c_print[i]; c_print[i] = c_print[j]; c_print[j] = k;
            i++;
            j--;
        }
    }
    if (L < j) QSort3(L, j);
    if (i < R) QSort3(i, R);
}


void QSort_W(int L, int R)
{
    int i, j;
    string X = word[(L + R) / 2];
    i = L, j = R;
    while (i <= j)
    {
        while (word[i] < X) i++;
        while (word[j] > X) j--;
        if (i <= j)
        {
            string Y = word[i]; word[i] = word[j]; word[j] = Y;
            int k = cnt[i]; cnt[i] = cnt[j]; cnt[j] = k;
            i++;
            j--;
        }
    }
    if (L < j) QSort_W(L, j);
    if (i < R) QSort_W(i, R);
}

int BinaryDown(int L, int R, string s)
{
    for(int i=L;i<=R;i++) if(s==word[i].substr(0, s.length())) return i;
    return -1;
}

int BinaryUp(int L, int R, string s)
{
    for(int i=R;i>=L;i--) if(s==word[i].substr(0, s.length())) return i;
    return -1;
}


mymap Optimal(mymap map1, mymap map2)
{
    mymap res;
    res.clear();
    if (map1.size() + map2.size() <= 10)
    {
        res = map1;
        for (mymap::iterator it = map2.begin(); it != map2.end(); it++) res.insert(mk(it->first,it->second));
        return res;
    }
    else
    {
        res = map1;
        for (mymap::iterator it = map2.begin(); it != map2.end(); it++)
        {
            if (res.size() < 10) res.insert(mk(it->first, it->second));
            else
            {
                if (res.begin()->second < it->second)
                {
                    res.erase(res.begin());
                    res.insert(mk(it->first, it->second));
                }
            }
        }
        return res;
    }
}

My AC code:

input:
>   3 3
>   1 2 1
>   1 2 1
>   1 3 1
>   -1

output:
>   No solution.

Why not
>   1 2

There are two roads connecting "1" and "2", so the route could be 1 - 2 - 1, with different road 1 - 2 and 2 -1