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

@Pokalino · Регистрация: 01.11.2023

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

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

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

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

Формат входных данных
В первой строке находятся два целых числа n и r (2⩽n⩽300 000, 1⩽r⩽10⁹) — количество памятников и максимальное расстояние, на котором мальчики могут увидеть друг друга.
Во второй строке заданы n положительных чисел d₁, d₂, ..., d_n, где d_i— расстояние от i-го памятника до начала улицы. Все памятники находятся на разном расстоянии от начала улицы. Памятники приведены в порядке возрастания расстояния от начала улицы (1⩽d₁<d₂<...<d_n⩽10⁹).

Формат выходных данных
Выведите одно число — число способов выбрать два памятника для организации свиданий.

Пояснения к примеру
В приведённом примере Маша может выбрать памятники 1 и 4 или памятники 2 и 4.

Ввод
4 4
1 3 5 8
Вывод
2

Мое решение:

C++

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int main() {
    int n, r; cin >> n >> r;
    vector <int> nums(n);
    for (int i = 0; i < n; ++i) scanf("%d", &nums[i]);
    int i = 0, j = 1, cnt = 0;
    while (i < n - 1 && j < n) {
        if (nums[j] - nums[i] > r) {
            cnt += n - j;
            ++i;
        }
        else ++j;
    }
    cout << cnt;
    return 0;
}

Это решение проходит 35 из 50 тестов. Самих тестов нет. Собственно меня интересует в чем может быть проблема.

@Royal_X · 29.04.2024, 21:35

Город Че

@Pokalino · 29.04.2024, 21:41 **[ТС]**

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

@woldemas · 30.04.2024, 06:47

Pokalino,

C++

1	unsigned long long cnt = 0;

@SmallEvil · 30.04.2024, 14:28

Сколько тут уже таких тем от таких отличных погроммистов...

@Pokalino · 30.04.2024, 14:38 **[ТС]**

SmallEvil, не понимаю к чему предъява. Изучаю язык, столкнулся с проблемой, задал вопрос в соответствующем разделе «cpp для начинающих». Данная ошибка, конечно, глупая, однако вчера я ее не заметил. Человеку ответить было не сложно, он ответил. Мне данный ответ помог. Так спрашивается, в чем заключается проблема? К чему был ваш комментарий?

@SmallEvil · 30.04.2024, 14:50

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

Изучаю язык, столкнулся с проблемой

Первый раз столкнулись с переполнением ?
А то что задачи нужно анализировать и изучать это не вам ?
По какой то непонятной мне причине, на этих (простите за нормальное слово) "курсах" это сплошь и рядом с этим переполнением. Им не нужно вас учить алгоритмам и инструментам, а вот этому, и того не достигают.

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

Человеку ответить было не сложно

Это вам так кажется. Ответившему человеку нужно прочитать всю эту простыню ненужных букв, сделать анализ ТЗ и в придачу ещё и вашего кода.

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

Так спрашивается, в чем заключается проблема?

Проблем тут нет, они там, у Вас.

@Pokalino · 30.04.2024, 15:46 **[ТС]**

SmallEvil, Нет, я не впервые сталкиваюсь с переполнением. Однако в рамках этой задачи я его не заметил. Я достаточно долго анализировал данную задачу и мой код, пришел к выводу, что решение реализовано верно. Я предполагал, что может быть переполнение, но счетчик у меня в подозрения не попал. Это и в правду совершенно глупая ошибка, которую я не заметил исключительно по невнимательности. Я посчитал, что нужен взгляд со стороны и задал вопрос на данном форуме.
Что касается вашего утверждения о том, что человеку было трудно ответить на на мой вопрос. Ну это вообще высер какой то. Никто никого не заставляет отвечать, это делается добровольно. Если бы это было трудно сделать, и ему не хотелось бы это делать, то думаю, он бы просто не отвечал. Но ответил, и я ему благодарен.
P.s. У меня нет к вам негатива, однако считаю ваш комментарий не уместным.

Новые блоги и статьи
Как написать микросервис на C# с Kafka, MediatR, Redis и GitLab CI/CD InfoMaster 15.01.2025 В современной разработке программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот подход позволяет разделить сложную систему. . .	Что такое CQRS и как это реализовать на C# с MediatR InfoMaster 15.01.2025 Концепция CQRS и её роль в современной разработке В современном мире разработки программного обеспечения архитектурные паттерны играют ключевую роль в создании масштабируемых и поддерживаемых. . .	Как настроить CI/CD с Azure DevOps InfoMaster 15.01.2025 CI/ CD, или непрерывная интеграция и непрерывное развертывание, представляет собой современный подход к разработке программного обеспечения, который позволяет автоматизировать и оптимизировать процесс. . .	Как настроить CI/CD с помощью Jenkins InfoMaster 15.01.2025 Введение в CI/ CD и Jenkins В современной разработке программного обеспечения непрерывная интеграция (CI) и непрерывная доставка (CD) стали неотъемлемыми элементами процесса создания качественных. . .	Как написать микросервис на Go/Golang с Kafka, REST и GitHub CI/CD InfoMaster 14.01.2025 Определение микросервиса, преимущества использования Go/ Golang Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .	Как написать микросервис с нуля на C# с RabbitMQ, CQRS, Swagger и CI/CD InfoMaster 14.01.2025 В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .
Как создать интернет-магазин на PHP и JavaScript InfoMaster 14.01.2025 В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .	Как написать Тетрис на Ассемблере InfoMaster 14.01.2025 Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .	Как создать игру "Танчики" на Unity3d и C# InfoMaster 14.01.2025 Разработка игр – это увлекательный процесс, сочетающий в себе творчество и технические навыки. В этой статье мы рассмотрим создание классической игры "Танчики" с использованием Unity3D и языка. . .	Организую платный онлайн микро-курс по доработке Android-клиента Telegram _Ivana 14.01.2025 Официальная версия и распространенные форки не полностью устраивают? Сделай свою кастомную версию клиента! 4 занятия по 2 часа (2 недели пн, ср 19:00-21:00 по Москве). Первое вводное занятие. . .	Как создать приложение для фитнеса для iOS/iPhone на Kotlin InfoMaster 14.01.2025 Создание собственного фитнес-приложения — это не только захватывающий, но и полезный процесс, ведь оно может стать вашим верным помощником на пути к здоровому и активному образу жизни. В современных. . .	Как создать приложение магазина для iOS/iPhone на Swift InfoMaster 14.01.2025 Введение в разработку iOS-приложений Разработка приложений для iPhone и других устройств на базе iOS открывает огромные возможности для создания инновационных мобильных решений. В данной статье мы. . .

@Royal_X 4272 / 2125 / 965 Регистрация: 01.06.2021 Сообщений: 7,320
	29.04.2024, 21:35	2
	Город Че 1

@Pokalino 0 / 0 / 0 Регистрация: 01.11.2023 Сообщений: 25
	29.04.2024, 21:41 [ТС]	3
	Я видел эту тему. Там показано иное решение данной задачи. Меня же интересует в заключается моя ошибка, как и было написано в теме. Так же отмечу, что последнее решение из той темы, схожее с моим, так же проходит только 35 тестов. 0

@SmallEvil 3719 / 2648 / 761 Регистрация: 29.06.2020 Сообщений: 9,800
	30.04.2024, 14:28	5
	Сколько тут уже таких тем от таких отличных погроммистов... 0

@Pokalino 0 / 0 / 0 Регистрация: 01.11.2023 Сообщений: 25
	30.04.2024, 14:38 [ТС]	6
	SmallEvil, не понимаю к чему предъява. Изучаю язык, столкнулся с проблемой, задал вопрос в соответствующем разделе «cpp для начинающих». Данная ошибка, конечно, глупая, однако вчера я ее не заметил. Человеку ответить было не сложно, он ответил. Мне данный ответ помог. Так спрашивается, в чем заключается проблема? К чему был ваш комментарий? 0

@SmallEvil 3719 / 2648 / 761 Регистрация: 29.06.2020 Сообщений: 9,800
	30.04.2024, 14:50	7
	Сообщение от Pokalino Изучаю язык, столкнулся с проблемой Первый раз столкнулись с переполнением ? А то что задачи нужно анализировать и изучать это не вам ? По какой то непонятной мне причине, на этих (простите за нормальное слово) "курсах" это сплошь и рядом с этим переполнением. Им не нужно вас учить алгоритмам и инструментам, а вот этому, и того не достигают. Сообщение от Pokalino Человеку ответить было не сложно Это вам так кажется. Ответившему человеку нужно прочитать всю эту простыню ненужных букв, сделать анализ ТЗ и в придачу ещё и вашего кода. Сообщение от Pokalino Так спрашивается, в чем заключается проблема? Проблем тут нет, они там, у Вас. 0

@Pokalino 0 / 0 / 0 Регистрация: 01.11.2023 Сообщений: 25
	30.04.2024, 15:46 [ТС]	8
	SmallEvil, Нет, я не впервые сталкиваюсь с переполнением. Однако в рамках этой задачи я его не заметил. Я достаточно долго анализировал данную задачу и мой код, пришел к выводу, что решение реализовано верно. Я предполагал, что может быть переполнение, но счетчик у меня в подозрения не попал. Это и в правду совершенно глупая ошибка, которую я не заметил исключительно по невнимательности. Я посчитал, что нужен взгляд со стороны и задал вопрос на данном форуме. Что касается вашего утверждения о том, что человеку было трудно ответить на на мой вопрос. Ну это вообще высер какой то. Никто никого не заставляет отвечать, это делается добровольно. Если бы это было трудно сделать, и ему не хотелось бы это делать, то думаю, он бы просто не отвечал. Но ответил, и я ему благодарен. P.s. У меня нет к вам негатива, однако считаю ваш комментарий не уместным. 0

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

Решение