Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/18: Рейтинг темы: голосов - 18, средняя оценка - 4.89
2 / 2 / 0
Регистрация: 14.03.2018
Сообщений: 45
1

Ошибка при решении задачи "Сумма максимума и минимума" - Time limit exceeded

14.03.2018, 15:44. Показов 3704. Ответов 8
Метки нет (Все метки)

Вот http://********/asp/do/index.asp?main=task&id_course=1&id_section=3&id_topic=34&id_ problem=611

Задана последовательность целых чисел. Числа нумеруются по порядку следования, начиная с единицы. Требуется написать программу, которая найдет сумму максимума из чисел с четными номерами и минимума из чисел с нечетными номерами – max{a2, a4, …}+min{a1, a3, …}

Но проблема не в решении, а во времени выполнении кода

Сначала я попробовал этот вариант:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
 
int main() {
  int v;
  int min=30000, max=-30000;
  for (int i=1; std::cout << v; i++)
    if (i%2) // если номер числа в последовательности нечетен
      if (v<min) min=v;
      else;
    else
      if (v>max) max=v;
  std::cout << min+max;
}
Но он не прошел один из тестов - превышен указанный в задаче лимит времени (1 сек.).

Тогда я попробовал заменить iostream, как советовали люди в обсуждении, на stdio.h/cstdio. И у меня получилось это:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
 
int main() {
  int v;
  int min=30000, max=-30000;
  for (int i=1; scanf("%d", &v); i++)
    if (i%2)
      if (v<min) min=v;
      else;
    else
      if (v>max) max=v;
  printf("%d", min+max);
}
Но такое решение провалилось на самом простеньком первом тесте - программа выполнялась 2 секунды! Хотя этот код у меня выполнился намного быстрее

Как мне решить эту задачу?

Добавлено через 7 минут
Вот исправленная ссылка на задачу:

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


Добавлено через 12 секунд
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.03.2018, 15:44
Ответы с готовыми решениями:

Time limit exceeded
Добрый день. Программа - бинарный поиск правой границы в упорядоченном множестве фраз. Возникает...

Time limit exceeded
Решаю задачки на одном сайте, там есть онлайн компилятор. Моя VS справляется, но компилятор с сайта...

Time limit exceeded
http://acm.timus.ru/problem.aspx?space=1&amp;num=1196 Уже все перепробовал, и всегда возникает...

Матрица инцидентности = Time-limit exceeded
Как переделать программу, чтобы время ее выполнения было &lt;0.250 sec? #include &lt;iostream&gt; using...

8
7062 / 6073 / 2764
Регистрация: 14.04.2014
Сообщений: 26,077
14.03.2018, 15:51 2
А сколько чисел-то? И кто их вводит?
0
2 / 2 / 0
Регистрация: 14.03.2018
Сообщений: 45
14.03.2018, 16:41  [ТС] 3
Кол-во целых чисел варьируется от 2 до 2×105, которые по модулю не превышают 10000. Все числа вводятся в единственной строке.
0
1715 / 564 / 187
Регистрация: 12.03.2016
Сообщений: 2,164
14.03.2018, 16:56 4
Цитата Сообщение от ELchemist Посмотреть сообщение
if (i%2)
для чего? Цикл с шагом 2. И что означает
Цитата Сообщение от ELchemist Посмотреть сообщение
сумму максимума
номер задачи какой? ссылка не работает.
0
471 / 423 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
14.03.2018, 17:03 5
Цитата Сообщение от ELchemist Посмотреть сообщение
for (int i=1; std::cout << v; i++)
Как Вы его вообще хотели пройти с таким подходом?

Цитата Сообщение от ELchemist Посмотреть сообщение
for (int i=1; scanf("%d", &v); i++)
Теперь здесь ввод, а был вывод. (Ну хотя бы ввод появился )

Цитата Сообщение от ELchemist Посмотреть сообщение
Кол-во целых чисел варьируется от 2 до 2×105, которые по модулю не превышают 10000. Все числа вводятся в единственной строке.
Где и кто их вводит? На каком этапе? + Ссылка битая, не перейти.
Откуда появляется лимит в 1с? От чего он зависит? (кол-во итераций, или вообще на всё про всё всего 1с?)

Добавлено через 2 минуты
Цитата Сообщение от мановар Посмотреть сообщение
для чего? Цикл с шагом 2. И что означает
Для проверки четности индекса. Сумма - есть сложение найденного Макс. значения из всех четных элементов, с Мин.значением из всех нечетных.
0
1715 / 564 / 187
Регистрация: 12.03.2016
Сообщений: 2,164
14.03.2018, 17:07 6
Да нашел я ее на том сайте, разобрался. Там
"Входные данные
Входной текстовый файл INPUT.TXT содержит в единственной строке последовательность от 2 до 2×10^5 целых чисел, которые по модулю не превышают 10000.

Выходные данные
Выходной текстовый файл OUTPUT.TXT должен содержать одно целое число - сумму максимума из чисел с четными номерами и минимума из чисел с нечетными номерами."

Работу с файлами надо организовать, это может быть одно из условий принятия решения.
0
2 / 2 / 0
Регистрация: 14.03.2018
Сообщений: 45
14.03.2018, 17:15  [ТС] 7
Номер задачи 272

Извините, если что-то вы не поняли. Я просто пишу с телефона, да к тому же я очень торопился

for (int i=1; std::cout << v; i++)
Вместо std::cout должен был быть std::cin. Опечаточка вышла.

Где и кто их вводит? На каком этапе?
Пользователь, наверное, вводит. Может вопрос в зацикливании цикла? Так об этом не нужно беспокоиться - в конце ввода всегда будет стоять eof

Добавлено через 12 секунд
Номер задачи 272

Извините, если что-то вы не поняли. Я просто пишу с телефона, да к тому же я очень торопился

for (int i=1; std::cout << v; i++)
Вместо std::cout должен был быть std::cin. Опечаточка вышла.

Где и кто их вводит? На каком этапе?
Пользователь, наверное, вводит. Может вопрос в зацикливании цикла? Так об этом не нужно беспокоиться - в конце ввода всегда будет стоять eof

Добавлено через 4 минуты
Работу с файлами надо организовать, это может быть одно из условий принятия решения.
Сомневаюсь. На сайте можно решить задачи и через работу с файлами, и через консольный ввод/вывод.
0
471 / 423 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
14.03.2018, 17:42 8
Цитата Сообщение от ELchemist Посмотреть сообщение
Может вопрос в зацикливании цикла? Так об этом не нужно беспокоиться - в конце ввода всегда будет стоять eof
В конце какого ввода? Судя по вашему коду, у вас нет конца цикла. А точнее - есть, выход за пределы допустимого значения int. И прога упадет с exception. Отсюда и все проблемы.

Если задача требует файлы - значит стоит сделать с файлами, т.к. проверку осуществляет компьютер, и если он не видит нужных файлов - тест фейл) (Кто вам будет интересно 2*10^5 значений руками там сидеть вводить? ) //Если не оговорено, что ввод с консоли допустим

Посему у них имеется набор подготовленных файлов, ожидающих результат в виде Output.txt
0
2 / 2 / 0
Регистрация: 14.03.2018
Сообщений: 45
15.03.2018, 08:28  [ТС] 9
Ввод и вывод с консоли ДОПУСТИМ.

Наверное, вы путаете Time limit exceeded с Runtime error. Runtime error появляется, когда программа НИКОГДА НЕ ЗАВЕРШАЕТСЯ. А у меня появилось Time limit exceeded, то есть программа ЗАВЕРШИЛАСЬ БЕЗ ОШИБКИ, просто времени на выполнение определенного теста к задаче ушло больше, то есть более 1 секунды выполнялась задача, то есть не соответствует всем условиям задачи.

Добавлено через 10 секунд
Ввод и вывод с консоли ДОПУСТИМ.

Наверное, вы путаете Time limit exceeded с Runtime error. Runtime error появляется, когда программа НИКОГДА НЕ ЗАВЕРШАЕТСЯ. А у меня появилось Time limit exceeded, то есть программа ЗАВЕРШИЛАСЬ БЕЗ ОШИБКИ, просто времени на выполнение определенного теста к задаче ушло больше, то есть более 1 секунды выполнялась задача, то есть не соответствует всем условиям задачи.

Добавлено через 14 часов 31 минуту
Все, я нашел решение задачи:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <cstdio>
 
int main() {
  std::ios_base::sync_with_stdio(0);
  int v;
  int min=30000, max=-30000;
  for (int i=1; std::cin >> v; i++)
    if (i%2)
      if (v<min) min=v;
      else;
    else
      if (v>max) max=v;
  std::cout << min+max;
}
При добавлении std::ios_base::sync_with_stdio(0) решение проходит по времени без использования printf() и scanf().

Тему можно закрывать
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.03.2018, 08:28

Timus Time limit exceeded (Bingo!)
Здравствуйте. Второй день уже пытаюсь решить проблемы &quot;Timus, C#, Time limit exceeded&quot;, у меня не...

Acm.timus.ru Time limit exceeded
Добрый день. Сама задача http://acm.timus.ru/problem.aspx?space=1&amp;num=1021 и мое решение: ...

Простой парсер выдает ошибку "Maximum execution time of 30 seconds exceeded"
Доброго времени суток, форумчане. Нуждаюсь в вашем совете. В общем написал простенький парсер для...

Количество делителей - Time-limit exceeded >1.000
Нужно определить, сколько делителей имеет данное натуральное число? Входные данные: В одной...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.