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

Обсуждение задачи 1915. Руины титанов: воссоздание былого

Maybe an interesting idea to solve this
Послано DR. Zhihua Lai 28 окт 2012 03:08
Instead of copying actually data, we might put a marked-number (index to copy) in the array.
For example,

            if (x > 0)
            {
                stack[q ++] = x;
            }
            else
            if (x == -1)
            {
                int y = stack[q - 1];
                if (y > 0)
                {
                    System.out.println(y);
                    q--;
                }
                else
                {
                    y = -y;
                    System.out.println(stack[y]);
                    stack[q - 1] = -(y - 1);
                    if (y == 0)
                    {
                        q--;
                    }
                }
            }
            else
            {
                stack[q] = -(q - 1); // negative numbers mean a copy.
                q ++;
            }

of course, this doesn't work for multiple continuous copy (e.g. 0, 0, 0 ..).
Re: Maybe an interesting idea to solve this
Послано Bogatyr 29 окт 2012 17:06
I pursued this idea at first before I noted the easier approach based on the input constraints.   The problem with storing markers representing copies in the stream is that it gets complicated when you have many combinations of partially consumed copies which are then copied, over and over again.  You basically need a tree to represent the state, and the tree must be walked when popping, which takes longer.   There probably is a simplified partial implementation of this, but given the constraints of the problem, it's not necessary.
Re: Maybe an interesting idea to solve this
Послано DR. Zhihua Lai 14 ноя 2012 15:35
I agree.
It gets complicated when there are copies inside copies.. so, this is not necessary because there are simpler and straightforward solutions.