Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 24.07.2012, 10:15   #1
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию Оптимизация (сокращение) кода решения задачи #2 c acmp.ru - нахождение суммы целых чисел от 1 до N

Добрый день.

Кто специалист в решении олимпиадных задач и/или обладает нестандартным решением.

Есть задачка #2 на acmp.ru.
Очень простая. учебная.

условие задачи:

Сумма
(Время: 1 сек. Память: 16 Мб Сложность: 19%)

Требуется посчитать сумму целых чисел от 1 до N.

Входные данные
В единственной строке входного файла INPUT.TXT записано единственное целое число N, не превышающее по абсолютной величине 10^4.

Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — сумму чисел от 1 до N.

"фишка" в том, что исходное N может быть как равно нулю, так и быть отрицательным.

у меня получилось решение на 131 байт:
Код:
var z,n:longint;
begin
  reset(input, 'input.txt');
  rewrite(output, 'output.txt');
  read(n); z:=n*(abs(n)+1) div 2;
  if n<=0 then inc(z);
  write(z)
end.


однако в топе решений светятся решения размером 110 байт (беру только решения на языке Паскаль).

честно говоря, все мои попытки улучшить результат провалились..
вопрос. Как можно решить данную задачу кодом на 110 байт?!!
Serge_Bliznykov вне форума Ответить с цитированием
Старый 24.07.2012, 10:46   #2
DiemonStar
Старожил
 
Регистрация: 08.02.2012
Сообщений: 2,173
По умолчанию

Цитата:
однако в топе решений светятся решения размером 110 байт (беру только решения на языке Паскаль).
может они ассемблерные вставки использовали? я бы в функции так и сделал. и деление заменил бы на сдвиг.
Правильно поставленная задача - три четверти решения.
DiemonStar вне форума Ответить с цитированием
Старый 24.07.2012, 10:57   #3
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

На 7 уменьшает
Код:
z:=n*(abs(n)+1) div 2 + ord(n<=0);
Добавил
тогда z не нужно:
write(n*(abs(n)+1) div 2 + ord(n<=0)) еще -6
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 24.07.2012 в 11:09.
Аватар вне форума Ответить с цитированием
Старый 24.07.2012, 11:38   #4
volvo877
Форумчанин
 
Аватар для volvo877
 
Регистрация: 01.06.2009
Сообщений: 108
По умолчанию

Код:
var n:comp;
begin
  reset(input, 'input.txt');
  rewrite(output, 'output.txt');
  read(n); write(n*(1+abs(n))/2+ord(n<=0):0:0)
end.
116 байт. Как можно убрать еще 6 - не понимаю...
volvo877 вне форума Ответить с цитированием
Старый 24.07.2012, 12:57   #5
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Аватар
ord(n<=0)
Спасибо. Отличный ход. я искал что-то подобное, но написать такое тямы не хватило.

Спасибо всем высказавшимся в теме!
Полезные посты!

Если у кого-то ещё идея хорошая в голову прийдёт — милости прошу!
Serge_Bliznykov вне форума Ответить с цитированием
Старый 24.07.2012, 13:30   #6
astecenko
Homo Interneticus
Форумчанин
 
Аватар для astecenko
 
Регистрация: 04.03.2011
Сообщений: 611
По умолчанию

Так тоже 116
Код:
var n:int64;
begin
  reset(input,'input.txt');
  rewrite(output,'output.txt');
  read(n);
  write(n*succ(abs(n))div 2+ord(n<1))
end.
astecenko вне форума Ответить с цитированием
Старый 24.07.2012, 15:24   #7
astecenko
Homo Interneticus
Форумчанин
 
Аватар для astecenko
 
Регистрация: 04.03.2011
Сообщений: 611
По умолчанию

Код:
var n:int64;
begin
  reset(input,'input.txt');
  rewrite(output,'output.txt');
  read(n);
  write(n*(1+abs(n))div 2+ord(n<1))
end.
Размер кода: 114
astecenko вне форума Ответить с цитированием
Старый 25.07.2012, 06:38   #8
Plague
Забанен
Форумчанин Подтвердите свой е-майл
 
Аватар для Plague
 
Регистрация: 01.11.2006
Сообщений: 420
По умолчанию

история одного байта
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
Plague вне форума Ответить с цитированием
Старый 25.07.2012, 08:25   #9
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Код:
var n:longint;
begin
  reset(input,'input.txt');
  rewrite(output,'output.txt');
  read(n);
  write((sqr(n)+n) div 2)
end.
не?
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 25.07.2012, 08:34   #10
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Цитата:
Сообщение от Stilet Посмотреть сообщение
не?
для отрицательного n не прокатит
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
программа для решения задачи из теории чисел Santogold Фриланс 10 30.04.2012 17:00
Сокращение кода. Eldrich JavaScript, Ajax 0 07.09.2011 20:01
Оптимизация и сокращение кода (if + сдвиг) Alex Cones Общие вопросы Delphi 2 06.04.2010 21:37
Оптимизация решения транспортной задачи методом "ступенек" EvKont Помощь студентам 0 26.04.2009 14:51
нахождение суммы четных чисел в массиве Ci_novice Общие вопросы C/C++ 1 23.12.2007 12:11