Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / C++ [игнор отключен] [закрыт для гостей] / Шарики(задача по программированию) / 25 сообщений из 93, страница 1 из 4
16.03.2016, 18:45
    #39193715
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
В одной компьютерной игре игрок выставляет в линию шарики разных цветов. Когда образуется непрерывная цепочка из трех и более шариков одного цвета, она удаляется из линии. Все шарики при этом сдвигаются друг к другу, и ситуация может повториться.

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

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

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

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

Решение данной задачи реализованнное на С++,заходит только на 70%.Остальные или неправильные, или тайм лимит(знаю что далеко от идеала,но все же):

Код: 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.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;


int main(){
       freopen("input.txt","r",stdin);
	   freopen("output.txt","w",stdout);
    
    int n=0,count=0,k=0;
    int a[1000]={0};
    cin>>n;
	   for(int i=0;i<n;i++){
           
           cin>>a[i];
       }
	   int rembFirst=0;
	   bool enterance=false;
       bool remember=true;
	   do{
           enterance=false;
           for(int i=1;i<n;i++){
               
               
               if(a[i]==a[i-1]){
                   
                   if(remember) {
                    rembFirst=i-1;
                    remember=false;
                   }
                   enterance=true;
                   count++;
                   
               }
               if(a[i]!=a[i-1] || i==(n-1)){
                   
                   if(count>=3){
                       for(int  z=rembFirst;z<n;++z){
                           a[z]=a[z+count];
                       }
                       k+=count;
                       n-=count;
                       count=1;
                       remember=true;
                       rembFirst=0;
                       break;
                   }
                   remember=true;
                   rembFirst=0;
                   count=1;
               }
               
               
           }
           
       }while(enterance);
    
    
    cout<<k;
    
    return 0;
}


З.Ы:Знаю что решений этой задачи в интернете много,но все же интересно допилить свой код до ума.Прошу строго не судить
...
Рейтинг: 0 / 0
16.03.2016, 18:46
    #39193717
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
если что картинка - это мое условие,текст нашел в интернете (на случай если картинка не загрузиться)
...
Рейтинг: 0 / 0
16.03.2016, 18:55
    #39193726
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
ванмомас намбаванвсе же интересно допилить свой код до ума
Интересно - допиливай. Хотя его, как обычно, лучше будет выкинуть целиком и написать новый.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
16.03.2016, 19:11
    #39193748
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
Dimitry Sibiryakovванмомас намбаванвсе же интересно допилить свой код до ума
Интересно - допиливай. Хотя его, как обычно, лучше будет выкинуть целиком и написать новый.

Его уже надо выкидывать. Там используется массив со всеми вытекающими.
Хотя из природы самой постановки требуется что-то вроде связного би-направленного
списка.
...
Рейтинг: 0 / 0
16.03.2016, 19:14
    #39193753
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
mayton,
а что такое би-направленный список?
...
Рейтинг: 0 / 0
16.03.2016, 19:22
    #39193756
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
Список ты должен был проходить. Это первый курс кодинга. 2-я или 3 лаба.

Дву-направленный (bi-directional (doubly-linked)) это тоже самое но в дополнение
к списку каждый элемент смотрит на обоих соседей. Справа и слева.
Это позволяет двигать итератор в обратку.

В STL возможно это его имплементация (я уж точно не помню):

http://www.cprogramming.com/tutorial/stl/stllist.html
...
Рейтинг: 0 / 0
16.03.2016, 19:26
    #39193760
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
mayton,обычный список юзал не раз,про этот слышу впервые,надо разобраться
...
Рейтинг: 0 / 0
16.03.2016, 20:20
    #39193792
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
maytonиз природы самой постановки требуется что-то вроде связного би-направленного
списка.
Не требуется ни массива, ни списка. Это задача решается поточно.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
16.03.2016, 20:47
    #39193805
Siemargl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
Dimitry Sibiryakov,

разве что рекурсивно.

Список называется не бисексуальным, а двусвязным, если что, майтон )
...
Рейтинг: 0 / 0
16.03.2016, 21:07
    #39193827
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
Siemarglразве что рекурсивно.
Назачем? В условии не сказано, что шарики схлопываются каскадно. Наоборот, сказано, что
цепочка может быть только одна.

Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
16.03.2016, 21:14
    #39193831
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
ванмомас намбаванmayton,
а что такое би-направленный список?

Двусвязный список. Список, где каждая нода связана как со следующей, так и с предыдущей нодой.
...
Рейтинг: 0 / 0
16.03.2016, 21:26
    #39193838
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
SiemarglСписок называется не бисексуальным, а двусвязным, если что, майтон )
Спасибо бро. Это ценная инфа.
...
Рейтинг: 0 / 0
16.03.2016, 21:36
    #39193850
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
Не надо тут рекурсий, списков и прочей бисексуальности. Один проход.
...
Рейтинг: 0 / 0
17.03.2016, 11:00
    #39194147
Siemargl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
Dima TНе надо тут рекурсий, списков и прочей бисексуальности. Один проход.Опиши алгоритм словами. Я сходу не вижу.
...
Рейтинг: 0 / 0
17.03.2016, 11:34
    #39194177
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
SiemarglDima TНе надо тут рекурсий, списков и прочей бисексуальности. Один проход.Опиши алгоритм словами. Я сходу не вижу.
Сверяешь текущую с предыдущей, совпало - счетчик++ ... дальше писать или догадался?
...
Рейтинг: 0 / 0
17.03.2016, 11:41
    #39194184
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
Dima TSiemarglпропущено...
Опиши алгоритм словами. Я сходу не вижу.
Сверяешь текущую с предыдущей, совпало - счетчик++ ... дальше писать или догадался?
Дима, понимаю твою идею но мне кажется что после удаления учёта трех единичек 111
их (по условию) надо удалить чтобы детектировать следующую цепочку 222.

Пример входных данных:
Код: plaintext
1.
10 3 3 2 1 1 1 2 2 3 3



Их можно и не удалять но тебе по любому нужно где-то хранить
и обновлять информацию о связности соседних шариков и сделать это через FSM
КМК очень сложно.
...
Рейтинг: 0 / 0
17.03.2016, 11:50
    #39194198
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
mayton(по условию)
Да, точно, я как-то упустил из виду "ситуация может повториться".
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
17.03.2016, 11:57
    #39194208
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
maytonДима, понимаю твою идею но мне кажется что после удаления учёта трех единичек 111
их (по условию) надо удалить чтобы детектировать следующую цепочку 222.
222 окружает найденную 111, т.е. уже известно где ее искать. Удалять не обязательно, задача только посчитать.
...
Рейтинг: 0 / 0
17.03.2016, 12:00
    #39194209
CEMb
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
Да, точно, я как-то упустил из виду "ситуация может повториться". а я что-то пока не упустил. Взять два указателя на строчку, и от них проверку делать в две стороны. Один проход. о_о
...
Рейтинг: 0 / 0
17.03.2016, 12:02
    #39194214
Leonid Kudryavtsev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
Dima T222 окружает найденную 111, т.е. уже известно где ее искать. Удалять не обязательно, задача только посчитать.
Тогда или рекурсия (и/или цикл + какая нибудь коллекция)
...
Рейтинг: 0 / 0
17.03.2016, 12:03
    #39194215
Leonid Kudryavtsev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
CEMbВзять два указателя на строчку, и от них проверку делать в две стороны. Один проход. о_о
Это как?
...
Рейтинг: 0 / 0
17.03.2016, 12:03
    #39194216
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
По сути тут две части:
1. Найти цепочку
2. Проверить окрестности на новую цепочку. Если найдено, то п.2 повторить.
...
Рейтинг: 0 / 0
17.03.2016, 12:05
    #39194219
Leonid Kudryavtsev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
Dima T, согласен, но это явно смахивает "на рекурсию". Или нечто очень на нее похожее. И в любом случае, это НЕ "один проход"

p.s. понятно, что любой рекурсивный алгоритма можно заменить на не рекурсивный + коллекция
...
Рейтинг: 0 / 0
17.03.2016, 12:06
    #39194222
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
Если дотошно всматриваться, то не один проход, а максимум дважды по каждой ячейке пройтись придется. Но рекурсий и списков не надо.
...
Рейтинг: 0 / 0
17.03.2016, 12:08
    #39194227
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Шарики(задача по программированию)
Leonid Kudryavtsevp.s. понятно, что любой рекурсивный алгоритма можно заменить на не рекурсивный + коллекция
Ну зачем тут рекурсия? Надо просто пойти от найденного центра в обе стороны. Циклов достаточно.
...
Рейтинг: 0 / 0
Форумы / C++ [игнор отключен] [закрыт для гостей] / Шарики(задача по программированию) / 25 сообщений из 93, страница 1 из 4
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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