Шарики (одномерный массив)

[isst]

И снова здравствуйте! Попалась вот такая задачка:

В одной компьютерной игре игрок выставляет в линию шарики разных цветов. Когда образуется непрерывная цепочка из трех и более шариков одного цвета, она удаляется из линии. Все шарики при этом сдвигаются друг к другу, и ситуация может повториться.

Напишите программу, которая по данной ситуации определяет, сколько шариков будет сейчас "уничтожено". Естественно, непрерывных цепочек из трех и более одноцветных шаров в начальный момент может быть не более одной.

Входные данные
Сначала вводится количество шариков в цепочке (не более 1000) и цвета шариков (от 0 до 9, каждому цвету соответствует свое целое число).

Выходные данные
Требуется вывести количество шариков, которое будет "уничтожено".

Пример:
Вход: 5 1 3 3 3 2
Выход: 3

Попробовал решить, но она далеко не всегда выдает правильные ответы. Прошу помочь мне разобраться, где ошибка. Мой код:

var MAS:aRRay of LongInt;
    N, i:IntegeR;
    cur, c1, c2:Byte;

begin
  readln(N);
  SetLength(MAS, N);
  for i:= loW(MAS) to HigH(MAS) do read(MAS[i]);
  cur:= MAS[loW(MAS)];
  c1:= 1;
  c2:= 0;
  for i:= loW(MAS) + 1 to HigH(MAS) do
  begin
    if (MAS[i] = cur) then inc(c1)
    else
    begin
      cur:= MAS[i];
      if (c1 > c2) then begin c2:= c1; c1:= 1; end;
    end;
  end;
  if (c1 > c2) then writeln(c1)
  else writeln(c2);
end.

[FPaul]

Наверное, нужно просматривать не в цикле for, а в while, и при очистке цепочки отступить на 2 элемента назад. На 2 элемента - потому, что удаляется по 3, но ранее они не были удалены.

[8Observer8]

В одной компьютерной игре игрок выставляет в линию шарики разных цветов

А он может выбирать цвет и положение шарика? У меня в голове не укладывается, как выглядит эта игра... Пожалуйста, объясните подробнее, что это такое?

[Serge_Bliznykov]

8Observer8,
ничего игрок не может выбирать.
Это же не игра, а олимпиадная задача - на входе количество и расположение шариков, программа должна определить, сколько шариков "схлопнется".

[8Observer8]

Сообщение от Serge_Bliznykov

8Observer8,
ничего игрок не может выбирать.
Это же не игра, а олимпиадная задача - на входе количество и расположение шариков, программа должна определить, сколько шариков "схлопнется".

Это я понимаю. Хочу создать игру, где было бы применимо решение этой задачи. Я создал тему: ссылка

[Utkin]

Я бы писал отдельную функцию по поиску последовательности шариков и гнал бы ее по массиву. Функция должна понимать - количество элементов в массиве, стартовая позиция. А дальше дело техники.

[Poma][a]

А я бы делал так :
бахнул список(хотя и массив зайдет).. но a[i] != цвету шарика.. a[i] есть кол-во шариков одного цвета, расположенных i-ыми в последовательности
тоесть

5 1 3 3 3 2
Массив будет такой
1 3 1
Причем будем еще запоминать цвет. Поэтому будет структурка
Дальше бы я тупо бегал по списку, пока мы можешь что-нить удалить
Искал бы первый элемент > 3 и удалял его(это сделать нужно аккуратно, чтобы сложить в случае "одинаковости" цветов его соседей)..
вот

[Smitt&Wesson]

5 1 3 3 3 2
Массив будет такой
1 3 1

Не такой, а такой 5 1 2. Шарики одного цвета убираются все.

[Poma][a]

Стоп.
5 - это вообще кол-во шариков
Изначально получаем :
1 3 1
А уже потом удаляем
и получаем
1 1

Решил написать

#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

struct st
{
	int n, cnt;
};

bool f(st& a)
{
	return a.cnt >= 3;
}

int main()
{
	int n;
	cin >> n;
	
	list<st> ball;
	st t;
	t.n = -1;
	t.cnt = 1;
	ball.push_back(t);	


	for (int i = 0; i < n; i++)
	{
		cin >> t.n;
		if (ball.back().n == t.n)
			ball.back().cnt++;
		else
			ball.push_back(t);
	}

	t.n = n+1;
	t.cnt = 1;
	ball.push_back(t);
	
	int cnt = 0;
	while (true)
	{
		list<st>::iterator b = find_if(ball.begin(), ball.end(), f);
		if (b == ball.end())
			break;

		cnt += b->cnt;		
		list<st>::iterator a = --b;
		b++;
		
		list<st>::iterator c = ++b;
		--b;
		
		if (a->n == c->n)
		{
			a->cnt += c->cnt;
			ball.erase(c);
		}
		ball.erase(b);
	}

	cout << cnt;

	return 0;
}

[Serge_Bliznykov]

Сообщение от Poma][a

Стоп.
5 - это вообще кол-во шариков
Изначально получаем :
1 3 1
А уже потом удаляем
и получаем
1 1

я бы предостерёг заменять цвета количеством!
дело в том, что "засада" в данной задаче, имхо, в том,
что схлопывания могут возникать циклически.
например,
дан ряд шариков (количество 9):
1 2 3 3 3 2 2 1 1

так вот, "схлопнутся" все 9 шариков (ответ 9)

а если дан ряд:
1 4 2 2 2 2 3 3 1 1
то схлопнутся всего 4 шара.

Если, как Вы предлагаете, переводить цвета в количество, то повторные схлопывания невозможно будет провести.
А вот идея со списком мне нравится - в отличие от массива удаление из начала/середины списка не приводит к необходимости перемещать весь "хвост" на место удалённых элементов.

p.s. на мой взгляд в коде автора темы нужно заменить цикл FOR на while(repeat) и повторять цикл, пока с новой строке есть серии подряд идущих элементов.