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

LVV · 2015-11-12 17:25:13

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

Код:

#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;
}

LeonID · 2015-11-12 17:33:08

Можна знайти залежність, що для 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)

andervish · 2015-11-12 18:14:43

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

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

ttt · 2015-11-12 19:04:03

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

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

LeonID · 2015-11-12 19:18:25

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

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

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

FordPerfect · 2015-11-12 23:58:19

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

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

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

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

Код:

Код:

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

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

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

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

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

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

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

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

ttt написав:

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

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

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