Задача про шеренгу мальчиков и девочек

@anna212 · Регистрация: 18.01.2018

Студворк — интернет-сервис помощи студентам

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

вход.:
Первая строка стандартного ввода содержит два целых числа n, k (1 <= k <= n <= 10 ^ 6), что означает количество людей в строке и число девушек, которых мы хотим, чтобы они были в строке. Следующая строка записи содержит целые числа {0 или 1}, обозначающие следующих лиц в серии: 0 - означает девушка, 1 - мальчик.

выход.:
Первая и единственная строка стандартного вывода должна содержать одно целое число, то есть минимальное количество мальчиков, которые должны быть удалены из строки, или одно слово «НЕТ», когда мальчиков нельзя удалить, чтобы девочки были в ряду.

Для входных данных:
8 3
0 1 1 0 1 0 1 0
правильный ответ:
2

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

Байт · 18.01.2018, 22:32

anna212, находите самую правую и самую левую девочку, и всех пацанов между ними гоните в шею!

Не по теме:

И будет вам Розовый Рай:)

@anna212 · 18.01.2018, 22:48 **[ТС]**

Байт, если так сделать, то ответ будет правильный только в варианте предложенным в задаче. а если по другому расставить мальчиков и девочек, то будет не правильно.

Добавлено через 4 минуты
есть решение задачи на pascale, но как сделать на с++ не понимаю.

Байт · 18.01.2018, 23:47

anna212, Условие задачи очень мутно. Я так и не понял, даже с вашими примерами, чего надо достигнуть.

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

есть решение задачи на pascale,

Любой паскалевский код без особых проблем переводится в сишный. Но я за это не возьмусь. Не потому что сложно. Потому что скушно

Добавлено через 2 минуты
А самое главное, смысл этой задачи совершенно не понятен... То есть нет задачи, как таковой. Условие можно понять по-разному. Я его понял так, как решил в посте 2. То есть буквально так, как там написано. А оно другое? Если вас интересует ответ, потрудитесь его (условие) сформулировать.

@anna212 · 19.01.2018, 00:24 **[ТС]**

Байт, да, условие задачи тупорылое, но увы оно такое есть, нужно самому продумывать все возможные варианты. я переделала код, но не работает.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
wczytaj(n, k, t[])
 poczatek := 1
 koniec := 1
 wynik := n + 1
 if t[1] == 0 then
 dziewczynki := 1
 else
 dziewczynki := 0
while koniec < n do
 while dziewczynki < k AND poczatek < n do
 poczatek := poczatek + 1
 if t[poczatek] == 0 then dziewczynki := dziewczynki + 1
 if dziewczynki == k then wynik := min(wynik, poczatek – koniec + 1)
 if t[koniec] == 0 then dziewczynki := dziewczynki - 1
 koniec := koniec + 1
if wynik == n + 1 then
 wypisz(NIE)
else
 wypisz(wynik - k)

и вот как я переделала:

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
#include<iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n, k,d;
    cin >> n >> k;
    int t[n];
    for(int i=1; i<=n; i++){
        cin >> t[i];
    }
    int poczatek=1, koniec=1, w=n+1;
    if(t[1]==0)
        d=1;
    else
        d=0;
    while(koniec < n){
        while (d<k && poczatek < n ){
            poczatek=+1;
            if(t[poczatek]==0) d=+1;
        }
            if(d==k) w=min(w,poczatek -koniec + 1);
            if(t[koniec]==0)
            d=-1;
                koniec=+1;
    }
            if(w==n+1) cout << "NIE" << endl;
            else cout << w-k;
}

Добавлено через 4 минуты
Вот как предлагают решить эту задачу:

Мы решаем задачи с использованием метода «гусеница». В двух переменных мы сохраняем голову гусеницы и ее спину соответственно. Пусть конец будет ее спиной и головой. Первоначально обе переменные задаются для первого лица в строке. Затем, в начале, мы двигаемся так долго вправо, пока между началом и концом не будет ровно k девочек. Затем конец перемещается на одно место вправо, и мы начинаем начало снова, пока не будет девочек. Так что это похоже на движение гусеницы.
Перед каждой сменой конца мы должны рассчитать количество мальчиков, которые должны покинуть линию и выбрать минимум из этих значений. Мы можем подсчитать количество мальчиков простым способом, посчитав разницу: poczatek−koniec+1−k, потому что мы знаем, что между началом и концом есть ровно k девочек, поэтому остальные должны быть мальчиками.

Байт · 19.01.2018, 00:33

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

Мы решаем задачи с использованием метода «гусеница».

Не знаю. возможно, этот метод и хорош. Возможно, есть у другие. Но я, увы! просто не вижу задачи. или она какая-то другая? Какая же? Простите меня за тупость, но я просто не вижу ее.
Я подозреваю, что вы здесь хотели сказать

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

чтобы девушка стояла в ряд, одна рядом с другой

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

Добавлено через 57 секунд
Всетки попытайтесь для начала задачу сформулировать...

@anna212 · 19.01.2018, 00:36 **[ТС]**

Байт, я ничего сказать не хотела, такое условие задачи, переделать я его не могу, нужно как-то его понять. в итоге за 2 дня попыток решений ничего не вышло. большое спасибо, что отписался)

Новичок · 19.01.2018, 08:00

Долго не понимал в чем подвох, думал условие совсем бредовое.

Сообщение от Байт

anna212, находите самую правую и самую левую девочку, и всех пацанов между ними гоните в шею!

Вот это первое в голову пришло. Показалось что задача сделать так чтоб девушки шли подряд. Но сейчас внезапно увидел вот это

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

Первая строка стандартного ввода содержит два целых числа n, k (1 <= k <= n <= 10 ^ 6), что означает количество людей в строке и число девушек, которых мы хотим, чтобы они были в строке.

Т.е нам нужно чтоб было k девушек подряд, а не все-все подряд.

Добавлено через 8 минут
Решается как-то так: с помощью префиксных сумм мы сможем быстро находить количество мальчиков на любом отрезке, потом мы еще заведем массив в котором будут индексы всех девушек. Ну а дальше будет у нас скажем очередь. Вначале закинем первых k девочек. Дальше возьмем первую и последнюю девочек, посмотрим сколько между ними мальчиков(с помощью префиксных сумм это будет быстро), если их меньше чем текущий ответ - обновим ответ. Дальше первую из очереди уберем, добавим последнюю и опять тоже самое.
P.S Пишу это совсем сонный, мог усложнить решение, но я пытался придумать эффективное решение ибо n, k довольно немаленькие...

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@anna212 0 / 0 / 0 Регистрация: 18.01.2018 Сообщений: 4

	Задача про шеренгу мальчиков и девочек 18.01.2018, 21:44. Показов 2481. Ответов 7 Метки с (Все метки) Здравствуйте, есть задача: Мальчики и девочки выстроились в линию, человек рядом с человеком. Теперь мы задаемся вопросом, сколько мальчиков, как минимум, должны выйти из строя, чтобы девушка стояла в ряд, одна рядом с другой, и между ними не стоял мальчик. вход.: Первая строка стандартного ввода содержит два целых числа n, k (1 <= k <= n <= 10 ^ 6), что означает количество людей в строке и число девушек, которых мы хотим, чтобы они были в строке. Следующая строка записи содержит целые числа {0 или 1}, обозначающие следующих лиц в серии: 0 - означает девушка, 1 - мальчик. выход.: Первая и единственная строка стандартного вывода должна содержать одно целое число, то есть минимальное количество мальчиков, которые должны быть удалены из строки, или одно слово «НЕТ», когда мальчиков нельзя удалить, чтобы девочки были в ряду. Для входных данных: 8 3 0 1 1 0 1 0 1 0 правильный ответ: 2 Не понимаю даже в какую сторону думать, чтобы решить, наверно не до конца поняла задачу. Может кто помочь, хотя бы подтолкнуть на правильный ход мыслей. Заранее благодарю) 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	18.01.2018, 22:32
	anna212, находите самую правую и самую левую девочку, и всех пацанов между ними гоните в шею! Не по теме: И будет вам Розовый Рай:) 0

@anna212 0 / 0 / 0 Регистрация: 18.01.2018 Сообщений: 4
	18.01.2018, 22:48 [ТС]
	Байт, если так сделать, то ответ будет правильный только в варианте предложенным в задаче. а если по другому расставить мальчиков и девочек, то будет не правильно. Добавлено через 4 минуты есть решение задачи на pascale, но как сделать на с++ не понимаю. 0

@anna212 0 / 0 / 0 Регистрация: 18.01.2018 Сообщений: 4
	19.01.2018, 00:36 [ТС]
	Байт, я ничего сказать не хотела, такое условие задачи, переделать я его не могу, нужно как-то его понять. в итоге за 2 дня попыток решений ничего не вышло. большое спасибо, что отписался) 0