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

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

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

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

вход.:
Первая строка стандартного ввода содержит два целых числа 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

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++

#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 довольно немаленькие...

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

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

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

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	18.01.2018, 23:47	4
	anna212, Условие задачи очень мутно. Я так и не понял, даже с вашими примерами, чего надо достигнуть. Сообщение от anna212 есть решение задачи на pascale, Любой паскалевский код без особых проблем переводится в сишный. Но я за это не возьмусь. Не потому что сложно. Потому что скушно Добавлено через 2 минуты А самое главное, смысл этой задачи совершенно не понятен... То есть нет задачи, как таковой. Условие можно понять по-разному. Я его понял так, как решил в посте 2. То есть буквально так, как там написано. А оно другое? Если вас интересует ответ, потрудитесь его (условие) сформулировать. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	19.01.2018, 00:33	6
	Сообщение от anna212 Мы решаем задачи с использованием метода «гусеница». Не знаю. возможно, этот метод и хорош. Возможно, есть у другие. Но я, увы! просто не вижу задачи. или она какая-то другая? Какая же? Простите меня за тупость, но я просто не вижу ее. Я подозреваю, что вы здесь хотели сказать Сообщение от anna212 чтобы девушка стояла в ряд, одна рядом с другой , но не решаюсь высказать свои соображения, чтобы опять не попасть ногой в лужу, а пальцем в небо. Добавлено через 57 секунд Всетки попытайтесь для начала задачу сформулировать... 0

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

Новичок 1642 / 1091 / 487 Регистрация: 17.07.2012 Сообщений: 5,345
	19.01.2018, 08:00	8
	Долго не понимал в чем подвох, думал условие совсем бредовое. Сообщение от Байт anna212, находите самую правую и самую левую девочку, и всех пацанов между ними гоните в шею! Вот это первое в голову пришло. Показалось что задача сделать так чтоб девушки шли подряд. Но сейчас внезапно увидел вот это Сообщение от anna212 Первая строка стандартного ввода содержит два целых числа n, k (1 <= k <= n <= 10 ^ 6), что означает количество людей в строке и число девушек, которых мы хотим, чтобы они были в строке. Т.е нам нужно чтоб было k девушек подряд, а не все-все подряд. Добавлено через 8 минут Решается как-то так: с помощью префиксных сумм мы сможем быстро находить количество мальчиков на любом отрезке, потом мы еще заведем массив в котором будут индексы всех девушек. Ну а дальше будет у нас скажем очередь. Вначале закинем первых k девочек. Дальше возьмем первую и последнюю девочек, посмотрим сколько между ними мальчиков(с помощью префиксных сумм это будет быстро), если их меньше чем текущий ответ - обновим ответ. Дальше первую из очереди уберем, добавим последнюю и опять тоже самое. P.S Пишу это совсем сонный, мог усложнить решение, но я пытался придумать эффективное решение ибо n, k довольно немаленькие... 0

Опции темы