Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2015-11-12 17:25:13

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Розбір рішень Задача Profit

Рішення «в лоб» передбачає простий перебір варіантів вкладеними циклами:

Код:

#include <iostream>
using namespace std;
int main()
{
int a,s=0;
    cin >> a;
    
    for(int b=a-1; b>=2; b--)
        for(int c=b; c>=2; c--)
            for(int d=c-1; d>0; d--)
                s++;
        
    cout << s;
    return 0;
}

Але при великих значеннях a,b,c,d перебір триває декілька секунд, тому створимо формулу для розрахунку варіантів перебору.

Код:

#include <iostream>
using namespace std;
int main()
{
int a;
    cin >> a;
long int s=0;    
    for(int i=2; i<a; i++)
            s+=i*(i-1)/2;
                
    cout << s;
    return 0;
}

Вік живи - вік навчайся.

Поза форумом

 

#2 2015-11-12 17:33:08

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Розбір рішень Задача Profit

Можна знайти залежність, що для 5 відповідь буде дорівнювати сумі 3*1+2*2+1*3, для 6 відповідно 4*1+2*3+3*2+1*4 і т.д. для n
(n-2)*1+(n-3)*2+(n-4)*3+...+2*(n-3)+1*(n-2)

Відредаговано LeonID (2015-11-12 17:36:33)

Поза форумом

 

#3 2015-11-12 18:14:43

andervish
Новий користувач
Зареєстрований: 2011-01-16
Повідомлень: 25

Re: Розбір рішень Задача Profit

https://oeis.org/A000292
Ответ: n(n-1)(n-2)/6

Відредаговано andervish (2015-11-12 18:15:00)

Поза форумом

 

#4 2015-11-12 19:04:03

ttt
Новий користувач
Зареєстрований: 2015-11-12
Повідомлень: 1

Re: Розбір рішень Задача Profit

Чим не правильний цей розв'зок? Підкажіть будь-ласка (Pascal)


Program Profit;
var i:real;
a:integer;
begin
read(a);
if a/2 = round(a/2) then
begin
i:sada-2)/2;
write(2*i*(i+1)*(2*i+1)/3);
end
else
begin
i:sada-3)/2;
write(2*i*(i+1)*(2*i+1)/3+(a-1)*(a-2)/2);
end;
end.

Поза форумом

 

#5 2015-11-12 19:18:25

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Розбір рішень Задача Profit

ttt написав:

Чим не правильний цей розв'зок? Підкажіть будь-ласка (Pascal)


Program Profit;
var i:real;
a:integer;
begin
read(a);
if a/2 = round(a/2) then
begin
i:sada-2)/2;
write(2*i*(i+1)*(2*i+1)/3);
end
else
begin
i:sada-3)/2;
write(2*i*(i+1)*(2*i+1)/3+(a-1)*(a-2)/2);
end;
end.

Результатом повинно бути ціле число, а ви виводите дробове.

Поза форумом

 

#6 2015-11-12 23:58:19

FordPerfect
Новий користувач
Зареєстрований: 2014-11-15
Повідомлень: 30

Re: Розбір рішень Задача Profit

На всякий случай, упомяну формулы Фаульхабера, может кто-то их не видел:
http://mathworld.wolfram.com/FaulhabersFormula.html

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt