ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1501. Чувство прекрасного

WA9, give tests please!
Послано Vasily Slesarev 25 май 2011 23:16
Hello, I use DP and get WA9.
Please give tests.
Re: WA9, give tests please!
Послано trn 20 июн 2011 13:20
pls give me solution.

Edited by author 29.06.2011 15:01
Re: WA9, give tests please!
Послано Vasily Slesarev 24 июн 2011 23:23
#include <vector>
#include <string>
#include <iostream>

using std::vector;
using std::cin;
using std::cout;
using std::string;
using std::pair;


int main()
{
    int count;
    string first_pile, second_pile;

    cin >> count;
    cin >> first_pile >> second_pile;

    vector<vector<pair<int, int> > > possibility(count + 1);
    for (int i = 0; i <= count; ++i) {
        possibility[i].resize(count + 1);
    }
    possibility[0][0].first = 1;
    possibility[0][0].second = 0;
    for (int i = 1; i <= count; ++i) {
        if (possibility[i - 1][0].first == 0) {
            possibility[i][0].first = 0;
        } else {
            if (first_pile[i - 1] == '0') {
                if (possibility[i - 1][0].second <= 0) {
                    possibility[i][0].first = 1;
                    possibility[i][0].second = possibility[i - 1][0].second + 1;
                } else {
                    possibility[i][0].first = 0;
                }
            } else {
                if (possibility[i - 1][0].second >= 0) {
                    possibility[i][0].first = 1;
                    possibility[i][0].second = possibility[i - 1][0].second - 1;
                } else {
                    possibility[i][0].first = 0;
                }

            }
        }
        if (possibility[0][i - 1].first == 0) {
            possibility[0][i].first = 0;
        } else {
            if (second_pile[i - 1] == '0') {
                if (possibility[0][i - 1].second <= 0) {
                    possibility[0][i].first = 2;
                    possibility[0][i].second = possibility[0][i - 1].second + 1;
                } else {
                    possibility[0][i].first = 0;
                }
            } else {
                if (possibility[0][i - 1].second >= 0) {
                    possibility[0][i].first = 2;
                    possibility[0][i].second = possibility[i - 1][0].second - 1;
                } else {
                    possibility[i][0].first = 0;
                }

            }
        }
    }
    for (int i = 1; i <= count; ++i) {
        for (int j = 1; j <= count; ++j) {
            possibility[i][j].first = 0;
            if (possibility[i - 1][j].first != 0) {
                if (first_pile[i - 1] == '0') {
                    if (possibility[i - 1][j].second <= 0) {
                        possibility[i][j].first = 1;
                        possibility[i][j].second = possibility[i - 1][j].second + 1;
                        continue;
                    }
                } else {
                    if (possibility[i - 1][j].second >= 0) {
                        possibility[i][j].first = 1;
                        possibility[i][j].second = possibility[i - 1][j].second - 1;
                        continue;
                    }
                }
            }
            if (possibility[i][j - 1].first != 0) {
                if (second_pile[j - 1] == '0') {
                    if (possibility[i][j - 1].second <= 0) {
                        possibility[i][j].first = 2;
                        possibility[i][j].second = possibility[i][j - 1].second + 1;
                        continue;
                    }
                } else {
                    if (possibility[i][j - 1].second >= 0) {
                        possibility[i][j].first = 2;
                        possibility[i][j].second = possibility[i - 1][j].second - 1;
                        continue;
                    }
                }
            }
        }
    }
    if (possibility[count][count].first == 0) {
        cout << "Impossible\n";
//        cin >> count;
        return 0;
    }
    vector<int> answer(0);
    int i = count, j = count;
    while ((i != 0) || (j != 0)) {
        answer.push_back(possibility[i][j].first);
        if (possibility[i][j].first == 1) {
            --i;
        } else {
            --j;
        }
    }
    for (int k = answer.size() - 1; k >= 0; --k) {
        cout << answer[k];
    }
//    cin >> count;
    return 0;
}
Re: WA9, give tests please!
Послано Vasily Slesarev 24 июн 2011 23:24
But I think, it is difficult to understand it.)
Re: WA9, give tests please!
Послано trn 28 июн 2011 13:27
4
1010
0110


22221111

Edited by author 29.06.2011 15:00