powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Шарики(задача по программированию)
25 сообщений из 93, страница 2 из 4
Шарики(задача по программированию)
    #39194228
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima Tа максимум дважды по каждой ячейке пройтись придется
откуда взялось утверждение "максимум дважды"

а если:

3011102222201113

схлопнули 11 и 222
после этого можем схлопнуть 000
потом можем схлопнуть 333

Как это сделать "максимум дважды" - мне не понять. Без рекурсии и списков - как два пальца обосновать. Но за один или "максимум дважды", мне не представить
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194242
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsevа если:
3011102222201113
Недопустимое значение.

Похоже ты ТЗ невнимательно прочитал
ванмомас намбаванЕстественно, непрерывных цепочек из трех и более одноцветных шаров в начальный момент может быть не более одной .
А у тебя их три.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194245
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мне почему-то эта задача напомнила клеточные автоматы. Там невозможно никак
спрогнозировать состояние вселенной на шаге N+2 до тех пор пока ты до конца
не воспроизведешь шаг N+1.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194246
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тогда да. Беру свои слова обратно. Два прохода.

Один найти цепочку, второй от цепочки в две стороны.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194248
Фотография CEMb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid KudryavtsevЭто как?
вырезаешь из цепочки первую тройку,
1. ставишь 2 указателя на границах
по очереди ходишь от них влево-вправо, до тех пор, пока есть одинаковые.
как только насчитал 3 одинаковые штуки - вырезал, перешёл к шагу 1
в конце сложил 2 строчки
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194258
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
CEMbLeonid KudryavtsevЭто как?
вырезаешь из цепочки первую тройку,
1. ставишь 2 указателя на границах
по очереди ходишь от них влево-вправо, до тех пор, пока есть одинаковые.
как только насчитал 3 одинаковые штуки - вырезал, перешёл к шагу 1
в конце сложил 2 строчки
Мне кажется в конце надо еще раз искать "первую тройку".
Доказать не могу но кажется что можем случайно пропустить еще
одну эпоху схлопываний.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194263
Фотография NekZ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тред не читал @ сразу отвечал

ИМХО ничего не нужно схлопывать в памяти (реаллоцтровать).
1. Выделяем массив под шарики.
2. Ищем место "схлопа" (3 шарика подряд одинакового цвета).
3. Запускаем "волны" в обе стороны со счётчиками (как от камня, брошенного в воду).

Единственная заминка может быть именно этими "волнами", которые должны быть как-то синхронизированы и двигаться параллельно. Если одна "волна" "заглохла" (упёрлась в границу), то другой уже продолжать двигаться не имеет смысла, потому что на её пути никогда не встретится 3 одинаковых шарика подряд (из условий задачи по игре, не может быть в один момент времени сразу 2 и более набора шариков для схлопывания).
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194280
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Краевой случай. Для 1000 элементов и количества троек ( 1000/(3+1) = 250) разделённых
одним шариком нам нужно контролировать 500 волн (по две волны на тройку).

Где эту информацию хранить? В отдельных структурах или в самом списке?
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194292
Фотография NekZ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мне до сих пор не даёт покоя, что это компьютерная игра.
"В одной компьютерной игре игрок выставляет в линию шарики разных цветов. Когда образуется непрерывная цепочка из трех и более шариков одного цвета, она удаляется из линии."
Вы тащите шарик в линию мышкой.
То есть, как только появляется последовательность из 3-х шариков, она тут же схлопывается и тянет за собой остальные по цепочке. Не может получиться так что в один момент времени будет сразу две и более последовательности в это линии.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194350
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Lines, Coloris, Zuma. Тысячи их.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194387
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonКраевой случай. Для 1000 элементов и количества троек ( 1000/(3+1) = 250) разделённых
одним шариком нам нужно контролировать 500 волн (по две волны на тройку).

Где эту информацию хранить? В отдельных структурах или в самом списке?
Не надо хранить 500, смотри по другому:
1. находим цепочку, назначаем ее краями дырки
2. проверяем края дырки на расширяемость, если расширяется - расширяем и снова п.2.
3. возвращаем размер дырки.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194393
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пора делать макет.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194410
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TmaytonКраевой случай. Для 1000 элементов и количества троек ( 1000/(3+1) = 250) разделённых
одним шариком нам нужно контролировать 500 волн (по две волны на тройку).

Где эту информацию хранить? В отдельных структурах или в самом списке?
Не надо хранить 500, смотри по другому:
1. находим цепочку, назначаем ее краями дырки
2. проверяем края дырки на расширяемость, если расширяется - расширяем и снова п.2.
3. возвращаем размер дырки.
Рекурсией это делается красиво. Но доказано, что любой рекурсивный алгоритм можно заменить на нерекурсивный.
К тому же рекурсия в данном случае тоже линейный алгоритм.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194412
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПора делать макет.
Тут кода 20-30 строк. Пусть ТС делает. Алгоритм подробно выше расписан.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194429
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TmaytonПора делать макет.
Тут кода 20-30 строк. Пусть ТС делает. Алгоритм подробно выше расписан.
Ему не под силу. Он школьников по росту сортировал и неосилил тесты.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194976
Фотография Малыхин Сергей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
нафига волны?
простой перебор цепочки с проверкой и подсчетом при схлопывании достаточно два шага назад.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194984
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Малыхин Сергей, "волна" и "перебор цепочки" это очень красивые поэтические метафоры брат.
Они достойны литературного форума.

Но может мы спустимся на землю хотя-бы до алгоритмического языка (АЯ) или псевдокода
в лучших традициях википедии?
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194994
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Малыхин Сергейпростой перебор цепочки с проверкой и подсчетом при схлопывании достаточно два шага назад.
Согласен с этим алгоритмом. Никаких рекурсий, двух и более проходов и прочих волн.
Один проход + состояние в массиве.

maytonНо может мы спустимся на землю хотя-бы до алгоритмического языка (АЯ) или псевдокода
в лучших традициях википедии?
Скукота. Пусть ТС пишет ))
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195009
Фотография CEMb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПора делать макет.Да, пойду заведу проект в Стиме.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195026
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonDima Tпропущено...

Тут кода 20-30 строк. Пусть ТС делает. Алгоритм подробно выше расписан.
Ему не под силу. Он школьников по росту сортировал и неосилил тесты.
Задача про школьников работала нормально,проблема была в размере массива ,я просто недочитал условие
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195027
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Про волну алгоритм зачётный ,наду будет закодить
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195102
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
Глобальный счетчик

ДляВсех элемент Из массив Схлопнуть(элемент, элемент)
 Печатает счетчик
Конец

Процедура Схлопнуть(лев_край, прав_край)
  нов_лев_край = лев_край
  Пока нов_лев_край >0 и массив[--нов_лев_край] = массив[лев_край]
  //аналогично прав_край
  удалено = нов_лев_край - лев_край + нов_прав_край - прав_край
  если удалено >= 3 
     счетчик += удалено 
     Схлопнуть(нов_лев_край, нов_прав_край)
Конец
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195128
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Siemargl, яж не славянофил. Мог-бы и латиницей писать.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195404
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пока чай заваривается набросал алгоритм, сорри что не по-русски ))

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
bool match_back(std::vector<int>& state, int v)
{
    return state.size() >= 2
            && state[state.size() - 1] == v
            && state[state.size() - 2] == v;
}

int erase_back(std::vector<int>& state, int v)
{
    int erased = 0;
    while (state.size() > 0 && state[state.size() - 1] == v) {
        state.pop_back();
        erased++;
    }
    return erased;
}


int main()
{
    //std::istringstream is ("5 1 3 3 3 2");
    std::istringstream is ("10 3 3 2 1 1 1 2 2 3 3");
    int erased = 0;
    std::vector<int> state;
    int erase_v = -1;
    int v;
    while (is >> v) {
        if (erase_v == v) {
            erased++;
        }
        else if (match_back(state, v)) {
            erased += erase_back(state, v);
            erase_v = v;
            erased++;
        }
        else {
            erase_v = -1;
            state.push_back(v);
        }
    }
    cout << erased << endl;
    return 0;
}
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195583
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky, давай тыщу шариков. Посмотрим как летает твой "Запорожец".
...
Рейтинг: 0 / 0
25 сообщений из 93, страница 2 из 4
Форумы / C++ [игнор отключен] [закрыт для гостей] / Шарики(задача по программированию)
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]