Thanks! I was confused about this before seeing your post.

You lie. In problem segment is [ai, bi].

Ошибка где-то тут:




string line;
bool check(int s,int e)
{
    string temp;
    for(int i=s; i<=e; i++)
        temp.push_back(line[i]);
    string temp2=temp;
    reverse(temp.begin(),temp.end());
    if(temp==temp2)
        return true;
    return false;
}
int dp[4005][4005];
int palindrome(int s,int e)
{
    if(s>=e)
        return 0;
    if(dp[s][e]!=-1)
        return dp[s][e];
    int ans=(1<<30);
    for(int i=s; i<e; i++)
        if(check(s,i))
        {
            ans=min(ans,1+palindrome(i+1,e));

        }
    return dp[s][e]=ans;
}
vector<string>anss;
void print(int s,int e)
{
    int b=palindrome(s,e);
    if(b==1)
    {
        string temp;
        for(int i=s; i<e; i++)
            temp.push_back(line[i]);
            anss.push_back(temp);

        return;
    }
    for(int i=s; i<e; i++)
        if(b==1+palindrome(i+1,e))
        {
             string temp;
           for(int j=s;j<=i;j++)
             temp.push_back(line[j]);
            anss.push_back(temp);

           print(i+1,e);
           break;
        }

}
int main()
{
    cin>>line;
    int len;
    len=line.size();
    anss.clear();
    memset(dp,-1,sizeof dp);
    cout<<palindrome(0,len)<<endl;
    print(0,len);
    len=anss.size();
    for(int i=0;i<len-1;i++)
        cout<<anss[i]<<" ";
    cout<<anss[len-1]<<"\n";



}

Edited by author 22.08.2018 12:26

Edited by author 22.08.2018 12:26

I had WA #1 as I printed loops. In other words, if my program had to output a path of length K it would print
1 1
1 2
2 2
2 3
...
(K - 1) (K - 1)
(K - 1) K

Having deleted them, I secured my AC :P

i don't think it's only about IO. i suppose they used not linked list (or just list in c++), but array with 2 iterators + didn't copy the data when there are already more then n - #of_moves elements in array/list

def prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

k = int(input())
for i in range(k):
    n = int(input())
    count = 0
    for f in range(2, 100):
        if prime(f) == True:
            count += 1
        if count == n:
            break
    print(f)


I have same problem

I haven't solved this problem yet. The table that you see right after "The frame consists of the following characters:" statement tells you how you should read these special characters.

I tried to generate the sample input, but not sure if it is correct since these are unprintable characters (atleast with my local PC encoding) and I cannot really verify it.

Nevertheless, here is my attempt to generate it. It looks rugged, but that is because of encoding issues. You should probably output it on your own PC with the program below.


..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
...........ÚÄÄÄÄÄ¿................................
...........³.....³................................
....ÚÄÄÄÄÄij.....³..........ÚÄ¿...................
....³......³.....³..........³.³...................
....³......³.....³..........ÀÄÙ...................
....³......³....Ú³ÄÄÄÄ¿.............ÚÄ¿...........
....³......ÀÄÄÄÄÄÙ....³.............³.³...........
....³......³....³.....³.............ÀÄÙ...........
....³......³....³.....³.........ÚÄÄ¿..............
....ÀÄÄÄÄÄÄÙ....³.....³.........³..³..............
................³.....³.........³..³..............
................ÀÄÄÄÄÄÙ.........ÀÄÄÙ..............
..................................................
..................................................


and the program that output it. It reads squares as in output sample and draws a board.


struct square {
  int x, y, a;
  square() = default;
  square(int x, int y, int a) : x(x), y(y), a(a) {}
};

void solve(std::istream &in, std::ostream &out) {
  std::vector<square> squares;
  int n;
  in >> n;
  for (int i = 0; i < n; ++i) {
    int x, y, a;
    in >> x >> y >> a;
    squares.emplace_back(x, y, a);
  }
  unsigned char board[20][50];
  for (int i = 0; i < 20; ++i) {
    for (int j = 0; j < 50; ++j) {
      board[i][j] = '.';
    }
  }
  for (square sq : squares) {
    board[sq.y][sq.x] = 218; // top-left
    board[sq.y][sq.x + sq.a - 1] = 191; // top-right
    board[sq.y + sq.a - 1][sq.x] = 192; // bottom-left
    board[sq.y + sq.a - 1][sq.x + sq.a - 1] = 217; // bottom-right
    for (int x = sq.x + 1; x < sq.x + sq.a - 1; ++x) {
      board[sq.y][x] = 196; // top edge
      board[sq.y + sq.a - 1][x] = 196; // bottom edge
    }
    for (int y = sq.y + 1; y < sq.y + sq.a - 1; ++y) {
      board[y][sq.x] = 179; // left edge
      board[y][sq.x + sq.a - 1] = 179; // right edge
    }
  }
  for (int i = 0; i < 20; ++i) {
    for (int j = 0; j < 50; ++j) {
      out << board[i][j];
    }
    out << '\n';
  }
}


int main() {
  solve(std::cin, std::cout);
}


As for reading it. I think you used char, while you need unsigned char or int for this problem. You can use getchar() that returns int or read into unsigned char s[SIZE]


Edited by author 20.08.2018 20:13

Edited by author 20.08.2018 20:13

Edited by author 20.08.2018 20:13

Edited by author 20.08.2018 20:19

Edited by author 20.08.2018 20:26

Edited by author 20.08.2018 20:34

As the frame defined by the tripple (X, Y, A) will have such vertices:
(X, Y)
(X, Y + A - 1)
(X + A - 1, Y)
(X + A - 1, Y + A - 1)

Ask for Admin

My AC program also gives this result.

I don't think the tests for the problem are very hard. Using Haskell my program solves this in about 0.5 secs but gets an AC in .031 secs (which I think is the lowest time you can get now), so they could definitely make the problems harder.

The frame is a square=。=

you can try to to it with stack instead of recursion

Maybe that's because you didn't calculate the right shortest-path with the least boots changed(that is, your first number of the output is wrong, but the other one is right). I've got WA7 because I used only one bfs to calculate both values. 2 bfs should be used. (BTW, some of my classmates said only one bfs could also work??? I'm not sure about this.

You should try to look up on the Internet how to find Fibonacci number with matrix exponentiation. The level of material should be accessible to a high school student if you are willing to spend couple of hours getting comfortable with new notations/definitions. There's not much theory behind this. You also need to know how to do fast exponentiation (i.e. in O(lon n) instead of O(n)) and use Long arithmetics (like BigInteger in Java).

Don't know if still relevant =), but the first test is different from sample.
It's a single-level test.

Edited by author 18.08.2018 08:24