С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
LVV
94 / 91 / 21
Регистрация: 15.02.2010
Сообщений: 369
#1

Лимит памяти для решений задач - C++

07.02.2013, 04:47. Просмотров 1015. Ответов 17
Метки нет (Все метки)

Чем руководствуются авторы задач, устанавливая лимт памяти для программ-решений?
Например, простая задча.
Её решение, сохранённое в текстовом режиме (блокнот) занимает на диске 4 килобайта.
C++
1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
cout << n/10 << " " << n%10 << endl;
return 0;
}
Откомпилированный файл (exe-шник) занимает меньше одного мегабайта (VisualStudio).
Вопрос: Если это не обьём кода и не объём ехе-шника,то что это?
Если это обьём памяти, используемый программой во время работы, то как грамотно установить его для конкретной задачи? И почему он в предложенной задаче аж 16 мегабайт?
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.02.2013, 04:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Лимит памяти для решений задач (C++):

резервирование памяти/освобождение памяти для трехмерного массива - C++
Необходимо создать трехмерный массив (A), в котором элементы вдоль направления Z выли бы выровнены по 16 байт. Есть две проблемы: ...

Составить программу для вычисления решений системы неравенств - C++
Для произвольных значений a,b вычислить решение системы неравенств. a/x&gt;=b b*x&lt;=0

Система для решений уравнений методом простых итераций. - C++
День добрый. Образовалась проблема. Я пропустил почти весь 2 семестр по болезни и теперь висит задача в виде курсового проекта на тему...

Лимит - C++
Составить прог-у которая найдет лимит 1 + 1/2^2 + 1/3^2 + ... +1/n^2

Лимит по времени - C++
Как можно сделать еще быстрее? Время работы 1.046 сек. Хотелось бы меньше 1.00 секунды:) #include &quot;stdafx.h&quot; #include &lt;iostream&gt; ...

Просрочен лимит времени - C++
Я решал задачу, вот она: Проблема в том, что я когда заносил в массив данные через scanf, то она выполнялась 2,5 секунды, а когда я...

17
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,200
Завершенные тесты: 1
07.02.2013, 11:09 #2
Цитата Сообщение от LVV Посмотреть сообщение
Если это обьём памяти, используемый программой во время работы, то как грамотно установить его для конкретной задачи?
Так же, как и время работы - исходя из предполагаемого метода решения. Так, чтобы слишком простые и неэффективные решения не прошли тест.
Цитата Сообщение от LVV Посмотреть сообщение
И почему он в предложенной задаче аж 16 мегабайт?
Думаю, просто так, потому что тут всё равно. Хотя надо учитывать, что в памяти будет exe'шник, несколько dll'ок, ещё стек какой-то размер уже изначально имеет.
1
LVV
94 / 91 / 21
Регистрация: 15.02.2010
Сообщений: 369
07.02.2013, 11:20  [ТС] #3
Цитата Сообщение от Somebody Посмотреть сообщение
Так же, как и время работы - исходя из предполагаемого метода решения...
... надо учитывать, что в памяти будет exe'шник, несколько dll'ок, ещё стек какой-то размер уже изначально имеет.
Но время вычислений можно измерить, скажем, средствами <time.h> внутри самой программы. А как измерить требуемый размер памяти. Ведь не наугад же он устанавливается авторами задач. К тому же тестирующей системе нужно как-то проверять, укладывается ли решение в лимит памяти...
0
alex_x_x
бжни
2450 / 1655 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
07.02.2013, 11:58 #4
LVV, ulimit + timeout - вот и все решение по ограничение
Авторами ограничения берутся видимо из существующих решений
0
LVV
94 / 91 / 21
Регистрация: 15.02.2010
Сообщений: 369
07.02.2013, 13:19  [ТС] #5
Цитата Сообщение от alex_x_x Посмотреть сообщение
LVV, ulimit + timeout - вот и все решение по ограничение
Авторами ограничения берутся видимо из существующих решений
Не забывайте, чт это страничка для начинающих...
Простой вопрос: участник олимпиады решает конкретную задачу. Как ему конкретно узнать, какой обьём памяти использует его конкретное решение? Например, такое:
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int main()
{
long long s=0;
for(int i=1; i<10000; i++)
for(int j=i; j<10000; j++)
s+=(i*j);
cout << s << endl;
return 0;
}
Может я по своей малограмотности что-то не так формулирую, тогда извините.
Но для большинства олимпиадых задач кроме тайм-лимита устанавливается ещё и лимит памяти.
Вот меня и интересует, как его вычислить (определить).
Что касается лимитов времени, то здесь нет проблем, потому что его можно определить, скажем, так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <ctime>
using namespace std;
int main()
{
long long s=0;
clock_t start,finish;
start = clock();
for(int i=1; i<10000; i++)
for(int j=i; j<10000; j++)
s+=(i*j);
finish = clock();
cout << s << endl
<< finish-start;
return 0;
}
А каким образом я могу определить обьём памяти, используемый данным решением?
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,200
Завершенные тесты: 1
07.02.2013, 14:34 #6
Так, на глаз... Отдельная переменная - почти ничего, сам код - тоже немного. Так что достаточно посчитать размеры массивов, связных списков, деревьев и прочих крупных вещей.
1
LVV
94 / 91 / 21
Регистрация: 15.02.2010
Сообщений: 369
07.02.2013, 14:52  [ТС] #7
Цитата Сообщение от Somebody Посмотреть сообщение
Так, на глаз... Отдельная переменная - почти ничего, сам код - тоже немного. Так что достаточно посчитать размеры массивов, связных списков, деревьев и прочих крупных вещей.
Жаль. Я думал, существуют определённые методы...
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,200
Завершенные тесты: 1
07.02.2013, 16:14 #8
Цитата Сообщение от LVV Посмотреть сообщение
Жаль. Я думал, существуют определённые методы...
Методы, конечно, существуют. Только смысла особого не имеет точно измерять всё в таком случае.
0
LVV
94 / 91 / 21
Регистрация: 15.02.2010
Сообщений: 369
07.02.2013, 17:58  [ТС] #9
Цитата Сообщение от Somebody Посмотреть сообщение
Методы, конечно, существуют. Только смысла особого не имеет точно измерять всё в таком случае.
Я и не имел в виду только это случай.
Прото хотелось знать, если задаётся лимит времени, то как он определяется для каждой конкретной задачи и каждого конкреиного решения.
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
07.02.2013, 19:07 #10
Цитата Сообщение от LVV Посмотреть сообщение
Прото хотелось знать, если задаётся лимит времени, то как он определяется для каждой конкретной задачи и каждого конкреиного решения.
Ну это же от авторов задачи и тестирующей системы зависит. Обычно есть какой-то повседневный лимит, который устанавливается на многие задачи, для некоторых задач он понижается, для некоторых повышается. Ваша задача к некоторым не относится.
0
Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
07.02.2013, 20:11 #11
лимиты задаются, чтобы задачу не решали "в лоб", а применяли какие-то алгоритмы, которые авторы задачи "заложили".
Авторы задач решают свои задания, и исходя от своих решений указывают лимиты.
0
LVV
94 / 91 / 21
Регистрация: 15.02.2010
Сообщений: 369
07.02.2013, 20:49  [ТС] #12
Цитата Сообщение от ZoRT Посмотреть сообщение
лимиты задаются, чтобы задачу не решали "в лоб", а применяли какие-то алгоритмы, которые авторы задачи "заложили".
Авторы задач решают свои задания, и исходя от своих решений указывают лимиты.
В том то и дело: хотелось бы знать как они определяют лимиты для своих решений? Это делается особым программным обеспечением? Или средствами С++ в самом решении можно определить?
0
Croessmah
Ушел
Эксперт CЭксперт С++
13558 / 7708 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 1
07.02.2013, 20:56 #13
Цитата Сообщение от LVV Посмотреть сообщение
Это делается особым программным обеспечением?
Если Вы пишите программу, вы же знаете сколько памяти она кушает =) плюс всякие библиотеки и т.д.
0
LVV
94 / 91 / 21
Регистрация: 15.02.2010
Сообщений: 369
08.02.2013, 08:48  [ТС] #14
Цитата Сообщение от Croessmah Посмотреть сообщение
Если Вы пишите программу, вы же знаете сколько памяти она кушает =) плюс всякие библиотеки и т.д.
То есть: мне нужно сидеть с калькулятором и подсчитывать, какой обьём занимает код, какой библиотеки, сколько потребуется на переменные, сколько уйдёт на массивчик... и т.д. и т.п. ???
Это тоже самое, что с секундомером определять, укладывается ли прорамма в лимит времени, или нет.
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.02.2013, 11:51 #15
Цитата Сообщение от LVV Посмотреть сообщение
То есть: мне нужно сидеть с калькулятором и подсчитывать, какой обьём занимает код, какой библиотеки, сколько потребуется на переменные, сколько уйдёт на массивчик... и т.д. и т.п. ???
В подавляющем большинстве случаев нужно посчитать лишь размер самого большого контейнера(массива/списка/дерева/etc), это занимает несколько секунд.
Причем считается это только в том случае, если вы не уверены, что ваша программа пройдет ограничения на память. А это не так уж часто случается.
1
08.02.2013, 11:51
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.02.2013, 11:51
Привет! Вот еще темы с ответами:

Лимит char в msvc - C++
В настройках не ставил /J. Однако почему то компилятор не выдаёт ошибку если пишу: char ftp = -100; char ftp = 250; По дефолту char...

Как задать свои иконки для панели задач и для программы в папке? - C++
Хочу, чтобы эти иконки отличались от той, что стоит в заголовке окна приложения.

Счастливый билет (Лимит Времени) - C++
Всем привет! Контестер пишет Time Limit. Подскажите что можно сделать чтоб моя программа работала быстрее. Что можно изменить или добавить?...

Как увеличить лимит на количество символов в консоли - C++
Использую консоль для вывода информации В определенный момент старая информация затираеться Можно как то увеличить лимит на количество...


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

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

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