Ошибка во время выполнения программы.

@KnockKnock · Регистрация: 04.11.2012

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

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

Условие:

Кликните здесь для просмотра всего текста

Как и у каждого мальчика, у Феди есть игрушечные машинки. Однако ему повезло больше, чем обычному мальчику — все n его машинок являются радиоуправляемыми. Целыми днями он может устраивать различные автогонки и играть с друзьями.

Из всех видов гонок Федя предпочитает гонки по прямой. В данном формате соревнования трасса имеет форму прямой и является бесконечной (соревнования идут до тех пор, пока Феде это не надоест). Изначально каждая из n машинок находится на некотором расстоянии от старта — имеет фору xi метров. По команде все машинки начинают свое движение от старта, при этом каждая машинка движется во время гонки с постоянной скоростью vi метров в секунду. Все машинки движутся в одном направлении — удаляются от старта.

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

Так как этого события можно ждать очень долго, Федя хочет настроить камеру на автоматическое включение во время обгона. Однако, Федя самостоятельно не может найти время, которое пройдет со времени начала гонки до времени первого обгона. Помогите Феде — напишите программу, находящую искомую величину.

Формат входных данных
В первой строке входного файла содержится единственное число n — количество машинок на трассе (2 <= n <= 100). Каждая из следующих n строк содержит по два целых числа xi и vi — расстояние от старта (в метрах) и скорость машинки i (в метрах в секунду) соответственно (1<= xi,vi <= 1000).

Исходно никакие две машинки не находятся в одной точке. Гарантируется, что хотя бы один обгон во время гонки произойдет.

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

Решение-то простое, перебираем машинки, ищем пары, где у одной скорость больше, а координата меньше, затем выбираем минимум из решений. Сразу оговорюсь, писал без оптимизаций

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;
 
 
int main ()
{
    long n, k;
    double x [101];
    double v [101];
 
    double res [101];
 
    cin >> n;
 
    for (long i = 0; i < n; i++)
    {
        cin >> x[i] >> v[i];
    }
 
    
    k = 0;
 
    for (long i = 0; i < n; i++)
        for (long j = 0; j < n; j++)
        {
            if (i == j) continue;
            if ( (v[i] > v[j]) && (x[i] < x[j]) ) {
                res [k] = (x[j] - x[i]) / (v[i] - v[j]);
                k++;
            }
        }
        
    
    double min = res [0];
    for (long i = 0; i < k; i ++) {
        if (res[i] < min) min = res [i];
    }
    
    
    cout << min;
 
 
    return 0;
}

Скорости гарантированно разные при делении, значит, на ноль не должно быть деления... В чём может быть проблема?

@I.M. · 04.11.2012, 21:59

Ошибка во время выполнения - завалился тест или прога вылетела?

Добавлено через 1 минуту
если второе, то проблема в этом

C++
1
double res [101];

т.е. фиксированный размер массива
и здесь:

C++
1
res [k] = (x[j] - x[i]) / (v[i] - v[j])

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

@KnockKnock · 04.11.2012, 23:03 **[ТС]**

Это именно ошибка в процессе. На сайте отправляешь cpp-файл, он компилируется и прогоняется через некоторое количество тестов. В комментариях к заваленному тесту указано только, что прога вылетает...
Делал размеры массивов с запасом (каждый по 2 тысячи, например), не спасает положение.

@I.M. · 04.11.2012, 23:08

А этот массив вообще нужен? Разве нельзя на ходу считать минимум?

Добавлено через 2 минуты
Я про double res [101];

И "с запасом" если и делать, то надо учитывать самый плохой случай, который я указал выше. Это примерно 5000 вариантов

@KnockKnock · 04.11.2012, 23:27 **[ТС]**

В этом была причина, да... Забыл нормально посчитать максимальное количество результатов =\
Переписал без массива, прошло все тесты. Спасибо за верную мысль.

Ведь хотел же сразу нормально написать, зачем-то решил с массивом делать =\

valeriikozlov · 04.11.2012, 23:29

KnockKnock, отсортируйте машинки по удаленности от старта, тогда минимум нужно будет искать между парами x[i] и x[i-1]. Максимум 99 вариантов.

@KnockKnock · 04.11.2012, 23:34 **[ТС]**

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

@Venzo · 04.11.2012, 23:35

не подскажите откуда задача?)

@KnockKnock · 04.11.2012, 23:41 **[ТС]**

Почему, подскажу

http://informatics.mccme.ru/mo... rid=3019#1

@Venzo · 05.11.2012, 00:30

KnockKnock, спасибо

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@KnockKnock 1 / 1 / 1 Регистрация: 04.11.2012 Сообщений: 11
	04.11.2012, 23:03 [ТС]
	Это именно ошибка в процессе. На сайте отправляешь cpp-файл, он компилируется и прогоняется через некоторое количество тестов. В комментариях к заваленному тесту указано только, что прога вылетает... Делал размеры массивов с запасом (каждый по 2 тысячи, например), не спасает положение. 0

@I.M. 576 / 559 / 47 Регистрация: 16.12.2011 Сообщений: 1,389
	04.11.2012, 23:08
	А этот массив вообще нужен? Разве нельзя на ходу считать минимум? Добавлено через 2 минуты Я про double res [101]; И "с запасом" если и делать, то надо учитывать самый плохой случай, который я указал выше. Это примерно 5000 вариантов 0

@KnockKnock 1 / 1 / 1 Регистрация: 04.11.2012 Сообщений: 11
	04.11.2012, 23:27 [ТС]
	В этом была причина, да... Забыл нормально посчитать максимальное количество результатов =\ Переписал без массива, прошло все тесты. Спасибо за верную мысль. Ведь хотел же сразу нормально написать, зачем-то решил с массивом делать =\ 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	04.11.2012, 23:29
	KnockKnock, отсортируйте машинки по удаленности от старта, тогда минимум нужно будет искать между парами x[i] и x[i-1]. Максимум 99 вариантов. 0

@KnockKnock 1 / 1 / 1 Регистрация: 04.11.2012 Сообщений: 11
	04.11.2012, 23:34 [ТС]
	Да я перед написанием подумал, что сортировать по затратам времени не сильно выгоднее, чем просто сравнить каждую с каждой в обеих сочетаниях, а потом вот сильно залип над этой ошибкой. Собственно, из-за мыслей о максимум 99 вариантах при сортировке и забыл напрочь про размер массива res... 0

@Venzo 127 / 125 / 16 Регистрация: 03.07.2011 Сообщений: 354
	04.11.2012, 23:35
	не подскажите откуда задача?) 0

@KnockKnock 1 / 1 / 1 Регистрация: 04.11.2012 Сообщений: 11
	04.11.2012, 23:41 [ТС]
	Почему, подскажу http://informatics.mccme.ru/mo... rid=3019#1 0

@Venzo 127 / 125 / 16 Регистрация: 03.07.2011 Сообщений: 354
	05.11.2012, 00:30
	KnockKnock, спасибо 0