0 / 0 / 0
Регистрация: 18.05.2018
Сообщений: 5
1

Включить свет в минимальном числе вагонов, так чтобы во время проезда туннеля никакой момент времени не был тёмным

05.07.2018, 10:35. Показов 547. Ответов 3
Метки нет (Все метки)

Петя решил отправиться в путешествие.Сейчас он едет в поезде.Поезд состоит из n вагонов, длина i-го вагона - ai метров.Расстоянием между вагонами можно пренебречь.
Петя заметил, что в некоторых вагонах включен свет.Поезд приближается к железнодорожному туннелю длинной h метров.Петя не хочет, чтобы в некоторый момент времени в туннеле оказались только вагоны, в которых не горит свет.Петя называет темным момент времени, если во всех вагонах,некоторый участок ненулевой длинны которых находится в туннеле,не горит свет.Чтобы исключить появление такого момента, Петя хочет включить свет в некоторых вагонах.

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

Формат входных данных:

Входные данные содержат несколько тестовых примеров. Первая строка содержит одно число t (1 ≤ t ≤ 100) –— количество тестов. Далее следуют описания тестов.

Каждый тест задается следующим образом: первая строка содержит два натуральных числа n, h (1 ≤ n ≤ 105, 1 ≤ h ≤ 109) — количество вагонов в поезде и длину туннеля в метрах. Следующая строка теста содержит n натуральных чисел ai (1 ≤ ai ≤ 109) — длины вагонов в метрах. Следующая строка содержит n чисел, i-е из который равно 1, если в i-м вагоне изначально включен свет, и 0 в противном случае. Вагоны перечислены от головы к хвосту поезда.

Сумма значений n по всем тестам не превышает 106.

Формат выходных данных:

Для каждого тестового примера выведите единственное число — наименьшее количество вагонов, в которых нужно включить свет.

Примеры:

Входные данные
2
7 10
5 3 4 5 9 9 9
1 0 0 0 1 0 0
5 2
1 2 3 1 1
1 1 0 1 1

Выходные данные
2
1
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.07.2018, 10:35
Ответы с готовыми решениями:

Какой свет горит на светофоре в момент времени
светафор горит след.образом: 3 мин зеленый,2 мин красный,по заданному вещественному t определить...

Возможно ли сделать так, чтобы скрипт проверял время и запускался в нужный момент?
Здравствуйте. Есть небольшой скрипт на VBS. Как можно сделать что бы скрипт запускался в нужное мне...

Как можно доработать код так, чтобы к каждому времени года был месяц и к нему ассоциации...
Как можно доработать этот код что бы к каждому времени года был месяц и к нему ассоциации которые...

Набить рюкзак этими предметами так, чтобы их общий вес был не менее m и при этом был минимальным
Для решения одного задания мне нужно решить следующую подзадачу. Суть такова: Есть рюкзак...

3
473 / 425 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
05.07.2018, 14:54 2
Смотри по длинам вагонов, если она превышает длину туннеля - включай свет.
Ну и естественно начало/конец вагонов надо осветить.

Т.е.:
7 10
5 3 4 5 9 9 9
1 0 0 0 1 0 0
Здесь:
1. Начало есть.
2. Пошло отсутствие света, но длина вагона 3, а туннеля 10, нормас.
3. Пошло отсутствие света, но длина вагонов уже 3+4 = 7, а туннеля 10, пойдет.
4. Пошло отсутствие света, но длина вагонов уже 3+4+5 = 12, а туннеля 10, не пойдет, включаем в крайнем свет. Включений = 1.
5. Свет есть.
6. Пошло отсутствие света, но длина вагона 9, туннеля 10, можно.
7. Пошло отсутствие света, но длина вагона 9+9 = 18, туннеля 10, не прокатит + еще и крайний. Включений = 2.

5 2
1 2 3 1 1
1 1 0 1 1
Тут по аналогии, в 3 света нет, длина туннеля меньше вагона, значит включение = 1.
0
3652 / 2989 / 828
Регистрация: 25.03.2012
Сообщений: 11,023
Записей в блоге: 1
05.07.2018, 15:06 3
где делают такие вагоны, чтобы все разной длины?
0
473 / 425 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
05.07.2018, 15:12 4
Kuzia domovenok, в задачках
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.07.2018, 15:12
Помогаю со студенческими работами здесь

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


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru