Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
8 / 0 / 0
Регистрация: 21.04.2018
Сообщений: 13

Дана шеренга из n психов. На каждом ходе каждый псих убивает своего соседа справа в шеренге

11.05.2018, 11:45. Показов 1816. Ответов 26
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Дана шеренга из n психов. Каждому психу дан идентификатор от 1 до n
На каждом ходе каждый псих, имеющий идентификатор больше, чем у психа справа (если такой есть) убивает своего соседа справа в шеренге
Вам дано исходное расположение психов в шеренге. Подсчитайте, сколько необходимо ходов до момента времени, после которого никто никого не будет убивать.



помогите написать алгоритм

входные данные
10
10 9 7 8 6 5 3 4 2 1
выходные данные
2

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
      #include <iostream>
        #include <stack>
 
        using namespace std;
 
        int main() {
            stack <int> q;
            int a, n, b, j = 0, c;
            cin >> n;
            for(int i = 0; i < n; i++){
                cin >> a;
                q.push(a);
            }
 
            for(int i = 0; i < q.size(); i++){
                if(q.top() > q.top() + 1){
                    j = j + 1;
                }
            }
 
            cout << j;
        }
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
11.05.2018, 11:45
Ответы с готовыми решениями:

Преобразовать массив так, чтобы каждый элемент был как сумма себя и своего соседа впереди
Преобразовать массив A(i) в массив B(i) так, чтобы в новом массиве каждый элемент получался бы как сумма себя и своего соседа впереди....

Определить, имеются ли в шеренге школьников хотя бы два соседа, родившиеся в один и тот же день недели
Тема &quot;Массивы (цикл-пока или цикл-до)&quot;. Шеренгу образовали школьники-одногодки, родившиеся в один и тот же месяц. Определить, имеются...

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

26
 Аватар для stzer
140 / 110 / 60
Регистрация: 26.10.2013
Сообщений: 314
12.05.2018, 00:42
Студворк — интернет-сервис помощи студентам
QuakerRUS, на входных данных, например, {1, 2, 3, 4, 5, 6}, пробовали свой код запускать?
1
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
12.05.2018, 00:53
Цитата Сообщение от Ромаха Посмотреть сообщение
Тут собака зарыта
дык...
Если так:
C++
1
2
3
4
5
6
7
kill_count=0;
        do  {
            ++kill_count;
                whoAreToDie(lps, listIteratorsToDie);
                KillemAll(lps, listIteratorsToDie);
                
            }while(!listIteratorsToDie.empty());
то 3 всё равно, хотя я понимаю, что 2, но чёт сегодня к вечеру нейроны нечувствительны к любому шевелению.
Хотя верно, do/while по условию empty пустой список тоже посчитает. То есть счетчик нужно -1-цей инициализировать. Тогда 2.
0
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
12.05.2018, 01:06
дык так пихните.. while(!listIteratorsToDie.empty() && ++kill_count); или 1 вычитайте

А я вот думаю.. Как бы это в онлайне делать..
Т.е. нужно находить за log такое p, что a[p-1] > a[p]

Во. А теперь давайте скажем, что есть массив, с которым мы умеем обращаться хитро - вставка/удаление/поиск за лог.
Теперь забываем про поиск.
У нас отныне есть массив b, где b[i] = a[i]-a[i-1]
Составим его и загоним позиции отрицательных в ToDie. Удаляем их (при удалении b[i], b[i+1] = b[i+1]+a[i]-a[i-1] (да-да. про смещения знаю. но фиксится за доп память/время)
И повторяем. Из-за цикличности получится красиво.
Понимаем, что поиск нам не нужен. Вывод - можно написать на сете.
0
 Аватар для QuakerRUS
1469 / 1010 / 456
Регистрация: 30.10.2017
Сообщений: 2,799
12.05.2018, 01:38
stzer, упс, я невнимательно прочитал условие. Убивает тот, у кого больше номер, а не у кого меньше. Тогда я думаю, что за один ход убийства происходят одновременно, судя по примеру выше.

Code
1
2
3
4
10 9 7 8 6 5 3 4 2 1
   x x   x x x   x x
10 8 4
   x x
Добавлено через 12 минут
C++
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
#include <iostream>
#include <vector>
#include <stack>
#include <cstdlib>
 
using namespace std;
 
int main()
{
    int n, count = 0;
    bool stop = false;
 
    cin >> n;
 
    vector<int> m(n);
    stack<int> kills;
 
    for (int i = 0; i < n; ++i)
        cin >> m[i];
 
    while (!stop)
    {
        stop = true;
 
        for (int i = 0; i < n - 1; ++i)
        {
            if (m[i] > m[i + 1])
            {
                if (stop == true)
                    ++count;
 
                kills.push(i + 1);
                stop = false;
            }
        }
 
        while (!kills.empty())
        {
            m.erase(m.begin() + kills.top());
            kills.pop();
            --n;
        }
    }
 
    cout << count << endl;
 
    system("pause");
    return 0;
}
0
-1 / 25 / 4
Регистрация: 27.11.2017
Сообщений: 375
12.05.2018, 02:41
Ладно, чтобы добиться большего понимания, давайте опишем алгоритм решения этой задачи:

1) Все шайку психов сперва загоняем в дек в том порядке, в котором их санитары ранжировали.
2) Перед ними ставим вектор.
3) Загоняем психа из головы дека в вектор.
4) Далее в цикле, пока еще в деке имеются психи проверяем следующее:
4.1. Если номер психа, который находится в голове дека меньше номера психа, который находится в хвосте вектора, то тогда увеличиваем счетчик убийств на единицу. Этот псих из головы дека по условию должен быть убит.
4.2. В противном случае, просто добавляем его в хвост вектора.
4.3. В любом случае удаляем психа из головы дека, поскольку он уже отработан, либо убит, либо стоит со своим друганом в векторе выживших психов.

И так обрабатываем весь дек оставшихся психов. Что касается где там право и где лево, то при необходимости реверсируем изначальный дек, исходя из того, кто как понимает условие этой задачи, либо меняем знак сравнения на противоположный, это уж кому как нравится.
0
 Аватар для Fulcrum_013
2083 / 1575 / 169
Регистрация: 14.12.2014
Сообщений: 13,614
12.05.2018, 03:54
Просто Саша, убиение по условиям идет синхронно. Т.е. задача пригодна к распараллеливанию хода.
0
-1 / 25 / 4
Регистрация: 27.11.2017
Сообщений: 375
12.05.2018, 04:26
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
убиение по условиям идет синхронно. Т.е. задача пригодна к распараллеливанию хода.
Это не влияет на конечный результат.
Важно одно, что каждый умирает ровно один раз, все как в жизни.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
12.05.2018, 04:26

Удалить те элементы массива, которые больше своего левого соседа
Здравствуйте! Возникла проблема с Паскалем: необходимо удалить те элементы массива, которые больше своего левого соседа (т.е элемент...

Вывести те элементы в наборе, которые меньше своего правого соседа
Дано целое число N (&gt; 1) и набор из N целых чисел. Вывести те элементы в наборе, которые меньше своего правого соседа, и количество K...

Вывести те элементы в наборе, которые меньше своего левого соседа
Помогите решит вот эти 2 задачи : 2)Дано целое число N (&gt;1) и набор N целых чисел. Вывести те элементы в наборе, которые меньше своего...

Вывести те элементы в наборе, которые меньше своего правого соседа
2. Дано целое число N(&gt;1) и набор из N целых чисел. Вывести те элементы в наборе, которые меньше своего правого соседа, колво К таких...

Вывести те элементы в наборе, которые меньше своего левого соседа
Дано целое число N (&gt; 1) и набор из N целых чисел. Вывести те эле- менты в наборе, которые меньше своего левого соседа, и количество K...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
27
Ответ Создать тему
Новые блоги и статьи
сукцессия 41
anaschu 24.07.2026
Численная верификация бифуркации в агентной модели лесной сукцессии: от одного параметра к ансамблю Автор: пользователь @Shumilov_AS | Раздел: Прикладная математика / Численные методы Кратко. . .
сукцессия 40. Ансамблевая кластерная параметризаци, часть 1.
anaschu 24.07.2026
Пр# Сопровождение научной статьи ИИ-ассистентом: подготовка публикации и калибровка агентно-ориентированной модели сукцессии микоризных систем **Полевые заметки о двухнедельной совместной работе**. . .
Теория всего 12. ВГК на планете в стратегической игре "терра"
anaschu 21.07.2026
### Главные семантические изменения и дешифровка новой физики 1. **`REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`)**: Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .
Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание
Hrethgir 21.07.2026
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928 Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .
Теория всего 11. Основные параметры
anaschu 21.07.2026
Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .
Теория всего 10. Клод трусишка
anaschu 21.07.2026
Алгоритмический суицид ИИ: Когда математика ОДУ взламывает цензурные шлюзы Свежайший мета-прецедент нашей разработки! Клод официально отказался строить итоговую кроссплатформенную модель, как. . .
Теория всего 9. Окончательная проработка метафоры "дерево = традиции"
anaschu 21.07.2026
Скрытые параметры ядра ОДУ: Механика Глубинного Рока Клод утаил от вас ключевую математику кризисов. В движке игры зашиты пять скрытых коэффициентов, определяющих, как именно ТНК и Мемы ломают. . .
Теория всего 8. Clauude трусишка. Ответ джемени
anaschu 21.07.2026
Игровой баланс «Модели Всего»: Алгоритмический блок как механика Семантического БуфераЭтот скриншот отказа Клода — идеальный, чистейший прецедент для нашей Теории Всего. Вы столкнулись не просто с. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru