Определить когда необходимо заехать в отель а когда выехать

@Dmitry0-01 · Регистрация: 17.09.2021

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

Условие
Вы не поверите, но Петр на отлично сдал экзамен по математическому анализу. Порядок вокруг наводит порядок в голове.

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

«Гранд-отель Гильберта», который выбрал Петр, пользуется большой популярностью, и места в нем распродаются очень быстро. Ходят слухи, что в нем бесконечное количество номеров, да и принять он может бесконечное количество автобусов с бесконечным количеством посетителей.

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

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

В предстоящем месяце 28 дней, ровно 4 недели, первый день месяца начинается в понедельник, соответственно месяц заканчивается в воскресенье. Расписание представлено в удобном формате, где указаны дни недели, в которые интересующий Петра номер занят. В расписании указаны полные дни, которые заняты. Все остальные дни свободны.

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

Помогите Петру определить, когда ему необходимо заехать в отель, а когда выехать.

Формат входных данных
Входные данные состоят из четырех строк, каждая из которых описывает одну неделю месяца. В каждой строке через пробел перечислены дни недели (MON, TUE, WED, THU, FRI, SAT, SUN), которые заняты, где «MON» --- понедельник, «TUE» --- вторник и так далее.

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

Формат выходных данных
Ваша программа должна вывести два числа через пробел: начало и конец максимального отрезка свободных дней, который можно забронировать. Если существует несколько таких отрезков одинаковой продолжительности, требуется выбрать самый ранний из них. Если весь месяц занят, выведите "0 0".

Замечание
В первом примере заняты даты 1 (MON), 8 (MON), 15 (MON), 22 (MON), 27 (SAT). Самым большим отрезком является дата с 2 по 7.

Примеры данных
Пример 1
MON
MON
MON
MON SAT

2 7
Пример 2
TUE MON

10 28
Пример 3

1 28
Пример 4
MON THU SAT SUN FRI TUE WED
SUN TUE MON FRI THU SAT WED
FRI THU WED SAT MON SUN TUE
WED MON THU SAT TUE FRI SUN

0 0

@andreyfreelans · 23.07.2024, 09:42

C++

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
 
int main() {
    // Массив для обозначения занятости дней
    std::vector<bool> occupied(28, false);
    
    // Дни недели
    std::string daysOfWeek[] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
 
    // Заполнение массива занятых дней
    for (int week = 0; week < 4; ++week) {
        std::string line;
        std::getline(std::cin, line);
        std::istringstream iss(line);
        std::string day;
 
        // Считываем занятые дни и помечаем их в occupied
        while (iss >> day) {
            auto it = std::find(std::begin(daysOfWeek), std::end(daysOfWeek), day);
            if (it != std::end(daysOfWeek)) {
                int dayIndex = (week * 7) + (it - daysOfWeek);
                occupied[dayIndex] = true;
            }
        }
    }
 
    // Ищем максимальный отрезок свободных дней
    int maxStart = -1, maxEnd = -1;
    int bestStart = -1, bestLength = 0;
 
    for (int i = 0; i < 28; ++i) {
        if (!occupied[i]) { // Если день свободен
            if (maxStart == -1) {
                // Начало нового свободного отрезка
                maxStart = i;
            }
            maxEnd = i; // Обновляем конец текущего свободного отрезка
        } else {
            // Если мы попали на занятый день, проверяем длину текущего отрезка
            if (maxStart != -1) {
                int currentLength = maxEnd - maxStart + 1;
                if (currentLength > bestLength) {
                    bestLength = currentLength;
                    bestStart = maxStart;
                }
                maxStart = -1; // Сбрасываем на случай следующего свободного отрезка
            }
        }
    }
 
    // Проверяем последний отрезок, если он был свободным
    if (maxStart != -1) {
        int currentLength = maxEnd - maxStart + 1;
        if (currentLength > bestLength) {
            bestLength = currentLength;
            bestStart = maxStart;
        }
    }
 
    // Проверяем, если вообще не нашли свободные дни
    if (bestStart == -1) {
        std::cout << "0 0" << std::endl;
    } else {
        std::cout << bestStart + 1 << " " << bestStart + bestLength << std::endl;
    }
 
    return 0;
}

@Dmitry0-01 4 / 5 / 2 Регистрация: 17.09.2021 Сообщений: 296
		1
	Определить когда необходимо заехать в отель а когда выехать 17.07.2024, 22:55. Показов 1157. Ответов 1 Метки нет (Все метки) Условие Вы не поверите, но Петр на отлично сдал экзамен по математическому анализу. Порядок вокруг наводит порядок в голове. Что нужно сделать после тяжелого экзамена - конечно же хорошенько отдохнуть. Каникулы уже не за горами, и Петр решил провести их с пользой, отдохнув от учебы и насладившись спокойствием в уединенном отеле где-нибудь на морском побережье. «Гранд-отель Гильберта», который выбрал Петр, пользуется большой популярностью, и места в нем распродаются очень быстро. Ходят слухи, что в нем бесконечное количество номеров, да и принять он может бесконечное количество автобусов с бесконечным количеством посетителей. Но Петра заинтересовал только один номер, поэтому он сразу же запросил расписание доступности этого номера на следующий месяц, чтобы выбрать для себя подходящий отрезок времени. Он хочет выбрать непрерывный максимально возможный отрезок дней, когда сможет отдохнуть. Если таких отрезков несколько --- самый ранний из них. В предстоящем месяце 28 дней, ровно 4 недели, первый день месяца начинается в понедельник, соответственно месяц заканчивается в воскресенье. Расписание представлено в удобном формате, где указаны дни недели, в которые интересующий Петра номер занят. В расписании указаны полные дни, которые заняты. Все остальные дни свободны. Теперь перед Петром стоит задача определить максимальный отрезок времени с первого по двадцать восьмое число месяца, на который он сможет забронировать номер, чтобы максимально продолжительно насладиться отдыхом. Естественно, Петр хочет найти самый ранний из возможных отрезков, чтобы отдохнуть как можно скорее. Помогите Петру определить, когда ему необходимо заехать в отель, а когда выехать. Формат входных данных Входные данные состоят из четырех строк, каждая из которых описывает одну неделю месяца. В каждой строке через пробел перечислены дни недели (MON, TUE, WED, THU, FRI, SAT, SUN), которые заняты, где «MON» --- понедельник, «TUE» --- вторник и так далее. Гарантируется, что в одной строке указаны различные дни недели. Если ни один день на неделе не занят --- дана пустая строка. Каждая строка, в том числе пустая и последняя, заканчивается символом перевода строки. Формат выходных данных Ваша программа должна вывести два числа через пробел: начало и конец максимального отрезка свободных дней, который можно забронировать. Если существует несколько таких отрезков одинаковой продолжительности, требуется выбрать самый ранний из них. Если весь месяц занят, выведите "0 0". Замечание В первом примере заняты даты 1 (MON), 8 (MON), 15 (MON), 22 (MON), 27 (SAT). Самым большим отрезком является дата с 2 по 7. Примеры данных Пример 1 MON MON MON MON SAT 2 7 Пример 2 TUE MON 10 28 Пример 3 1 28 Пример 4 MON THU SAT SUN FRI TUE WED SUN TUE MON FRI THU SAT WED FRI THU WED SAT MON SUN TUE WED MON THU SAT TUE FRI SUN 0 0 0

	23.07.2024, 09:42