|
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
0
|
||||||
| 11.05.2018, 11:45 | |
|
Ответы с готовыми решениями:
26
Преобразовать массив так, чтобы каждый элемент был как сумма себя и своего соседа впереди Определить, имеются ли в шеренге школьников хотя бы два соседа, родившиеся в один и тот же день недели
|
|
140 / 110 / 60
Регистрация: 26.10.2013
Сообщений: 314
|
|
| 12.05.2018, 00:42 | |
|
1
|
|
|
Комп_Оратор)
|
|||||||
| 12.05.2018, 00:53 | |||||||
|
Если так:
Хотя верно, do/while по условию empty пустой список тоже посчитает. То есть счетчик нужно -1-цей инициализировать. Тогда 2.
0
|
|||||||
| 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
|
|
|
1469 / 1010 / 456
Регистрация: 30.10.2017
Сообщений: 2,799
|
|||||||||||
| 12.05.2018, 01:38 | |||||||||||
|
stzer, упс, я невнимательно прочитал условие. Убивает тот, у кого больше номер, а не у кого меньше. Тогда я думаю, что за один ход убийства происходят одновременно, судя по примеру выше.
![]()
0
|
|||||||||||
|
-1 / 25 / 4
Регистрация: 27.11.2017
Сообщений: 375
|
|
| 12.05.2018, 02:41 | |
|
Ладно, чтобы добиться большего понимания, давайте опишем алгоритм решения этой задачи:
1) Все шайку психов сперва загоняем в дек в том порядке, в котором их санитары ранжировали. 2) Перед ними ставим вектор. 3) Загоняем психа из головы дека в вектор. 4) Далее в цикле, пока еще в деке имеются психи проверяем следующее: 4.1. Если номер психа, который находится в голове дека меньше номера психа, который находится в хвосте вектора, то тогда увеличиваем счетчик убийств на единицу. Этот псих из головы дека по условию должен быть убит. 4.2. В противном случае, просто добавляем его в хвост вектора. 4.3. В любом случае удаляем психа из головы дека, поскольку он уже отработан, либо убит, либо стоит со своим друганом в векторе выживших психов. И так обрабатываем весь дек оставшихся психов. Что касается где там право и где лево, то при необходимости реверсируем изначальный дек, исходя из того, кто как понимает условие этой задачи, либо меняем знак сравнения на противоположный, это уж кому как нравится.
0
|
|
|
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 | ||
|
Важно одно, что каждый умирает ровно один раз, все как в жизни.
0
|
||
| 12.05.2018, 04:26 | |
|
Удалить те элементы массива, которые больше своего левого соседа Вывести те элементы в наборе, которые меньше своего правого соседа
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
сукцессия 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
Игровой баланс «Модели Всего»: Алгоритмический блок как механика Семантического БуфераЭтот скриншот отказа Клода — идеальный, чистейший прецедент для нашей Теории Всего. Вы столкнулись не просто с. . .
|