I have solved it by reduction to a graph exploration task.
Each vertex consists of three parameters (i, j, pr).
Where i, j denote number of card at the top of each pile and pr denotes previous state.  pr is also a "used"  array.  So,  if pr[N] [N] =none,  then impossible.  Otherwise  just recover answer using pr.  You can also have in your state additional parameter diff denotes difference between red and black cards.  I have used instead additional two arrays diff11 and diff2 denote difference between first i cards in first pile and in the second pile respectively.  There is an edge iff difference at the next step would be not greater than one (abs) ,  obviously.

//I have correct in the IDE, what's wrong?

import java.io.IOException;
import java.util.Scanner;

public class VasyaCare{
    public static void main(String[] args) throws IOException {
    VasyaCare vasya_care = new VasyaCare();
    Scanner scn = new Scanner(System.in);
    int n = scn.nextInt();
    try{                               // Check
            if(n < 10){
        double[] b = vasya_care.setScore(n);
        double median = vasya_care.getMedian(b);
        if(median==3){
            System.out.println("None");
        }
        else if(median==5){
            System.out.println("Named");
        }
        else if(median >= 4.5){
            System.out.println("High");
        }
        else if(median < 4.5){
            System.out.println("Common");
        }
        }
        else throw new IOException("Please, type number from 1 to 10!");
    }
    catch(Exception e){e = new IOException();}
    }


    double getMedian(double[] b{          // calculate median score of exam
    int sum = 0;
    for(int i = 0; i < b.length; i++){
        sum = (int) (sum + b[i]);
    }
    return (double)sum/b.length;
    }

    double[] setScore(int n){            // forming list scores
    Scanner scn = new Scanner(System.in);
    double[] b = new double[n];{
        for(int j = 0; j < n; j++){
            int m = scn.nextInt();
            if(m<3 || m > 5){
                System.out.println("Type score from 3 to 5: ");
                j--;
            }
            else if (m>=3 && m<=5){
                b[j] = m;
            }
        }
    }
    return b;
    }
}

// Thank you for your attention!

Let unsigned long long total_cost=0.
For every edge E in tree total_cost +=cost_of_all_paths_lies_on_edge(E).
double ans=2.0*total_cost/n/(n-1) is overflow and and WA#19.
================
Let double ans = 0.
For every edge E in tree ans+=2.0*cost_of_all_paths_lies_on_edge(E)/n/(n-1).
That is AC.
===========
Maybe if not multiply by two in the first scenario there is also AC,  I have not tested.

Could anyone help me?

5
AAAAA
ans:5.000

6
CBDCBD
ans:3.600

6
DDADDD
ans:2.000
They helped me to solve this problem~
Hope they can help you
o(∩_∩)o...

0-1 bfs on graph with 2 * n verticles.

how to solve this problem?
construct suffix tree for N times and then LCP or there is easier and faster way?

Is it possible to solve this problem using suffix automata? I got TL5.
But I think that O(N * K) solution have to work faster. Am I wrong? Thanks.

PS. Got AC with KMP O(N * K).

Edited by author 26.08.2015 00:30

//#define LOCAL
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 250000+10

int N;
char str1[MAXN], str2[MAXN];
char temp[MAXN*2];

int kmp(char* s, char* t, int pos);
void get_next(char* t, int* next, int t_len);
int main()
{
#ifdef LOCAL
    freopen("1423_String_Tale_2.in", "r", stdin);
    freopen("1423_String_Tale_2.out", "w", stdout);
#endif

    scanf("%d", &N);
    scanf("%s%s", str1, str2);

    int s1_len = strlen(str1);
    int s2_len = strlen(str2);

    if(s1_len != s2_len){
        printf("%d\n", -1);
        return 0;
    }

    strcpy(temp, str1);
    strcat(temp, str1);
    int ans;
    ans = kmp(temp, str2, 0);
    if(ans != 0 && ans != -1)
        printf("%d\n", s1_len-ans);
    else
        printf("%d\n", ans);

    return 0;
}

int kmp(char* s, char* t, int pos)
{
    int s_len = strlen(s);
    if(pos<0 || pos>s_len-1){
        fprintf(stderr, "%s", "Error: invalid pos.");
        system("pause");
    }

    int t_len = strlen(t);
    int *next = (int*)malloc(sizeof(int) * t_len);
    get_next(t, next, t_len);

    int i = pos;
    int j = 0;

    while(i<s_len && j<t_len){
        if(j<0 || s[i]==t[j]){
            i++;
            j++;
        }
        else
            j = next[j];
    }

//    free(next);
    if(j >= t_len)
        return i-t_len;
    else
        return -1;
}

void get_next(char* t, int* next, int t_len)
{
    next[0] = -1;
    int j = 0;
    int k = -1;
    while(j < t_len){
        if(k==-1 || t[j]==t[k]){
            j++;
            k++;
            next[j] = k;
        }
        else
            k = next[k];
    }
}

###############################################
Can anyone tell me WHY???

Edited by author 11.07.2017 19:31

Please, give me some hints on how to solve it. Thanks in advance.

I have got a verdict Compiler Failed on Clang compiler.  Never have got such a verdict.  Every other compiler submit gets AC. Can't post code here because it is a working solution.

I was trying to do the following.
Construct suffix automation for each command.
Binary search for length of each key substring.
Binary search works as follows.
For each substring of command of len (lower_bound+upper_bound) /2 check whether it is a substring of another command.

Check my submissions and learn how evil the problem is!

Use unordered map and unordered set.
max_load_factor(0.25)
reserve (1<<x)

Could someone explain this idea?
tbl[0] = 1;
for (int i = 1; i <= N; i++)
{
    for (int j = N; j >= i ; j--)
    {
            tbl[j] += tbl[j-i];
    }
}
cout<<tbl[N]-1<<endl;

I had a MLE 7 test - I split the tree into 3 parts
And choose the best 3 answers
Accepted 0.593 !!!!

-------------------------
Enough for the division into 2 parts

Edited by author 30.07.2011 10:18

#include <iostream>
#include <vector>
#include <queue>
#define INF (1<<29)
using namespace std;

struct Arista
{
    int hasta,costo;
};

Arista armar(int h,int c)
{
    Arista ar;
    ar.hasta=h;
    ar.costo=c;
    return ar;
}

struct Grafo
{
    int suma=0;

    vector <vector <Arista>> adj;
    vector <int> dist;
    vector <bool> visitado;
    bool encontro=false;

    int nodos,aristas;
    int S,F;

    void leer()
    {
        cin >> nodos >> aristas;
        adj.resize(nodos+1);
        dist.resize(nodos+1,INF);
        visitado.resize(nodos+1,false);

        int desde,hasta,costo;
        for(int c=0; c<aristas; c++)
        {
            cin >> desde >> hasta >> costo;
            adj[desde].push_back(armar(hasta,costo));
        }

        cin >> S >> F;
        dist[S]=0;
    }

    void bdfs(int nodo, int padre)
    {

        visitado[nodo]=true;

        for(int c=0; c<adj[nodo].size(); c++)
        {
            int vecino=adj[nodo][c].hasta;
            int costo=adj[nodo][c].costo;
            if(dist[vecino]>dist[nodo]+costo&&visitado[vecino]==false)
            {
                dist[vecino]=dist[nodo]+costo;
                bdfs(vecino,nodo);
            }
        }
    }


    void start()
    {
        if(dist[F]<INF) cout << dist[F];
        else cout << "No solution";
    }

};

int main()
{
    Grafo g;
    g.leer();
    g.bdfs(g.S,-1);
    g.start();
    cout << endl;
    return 0;
}


BFS+DFS
Some test, guys?

j-1 bit must be 1 if prefix of the string could be cut by j palindroms. in notation 9-->1110 , but 9 must be 10000000, isn`t it???

I was using QUEUE.
It was Memory limit exceed #8 or something similar.
Replaced queue by simple an static array of one million elements.
I was using state struct.
There are three members of unsigned char type.
So,  with C limitations, I got AC with 16 MB.