Форум Всеукраїнської інтернет-олімпіади NetOI
На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
#1 2014-12-20 22:06:35
- infoshoc
- Новий користувач
- Зареєстрований: 2012-10-07
- Повідомлень: 6
Розв'язки
Хотілося б знати розв'язки задач, які я не розв'язав, тому почну із себе: викладу свої розв'язки.
Diamonds
Код:
#include <cstdio>
int main()
{
int n;
scanf("%d", &n);
int s = 0;
for (int first_guest = 1; first_guest * 4 <= n; first_guest++)
{
for (int second_guest = first_guest; first_guest + second_guest * 3 <= n; second_guest++)
{
s += (n - first_guest - second_guest) / 2 - second_guest + 1;
}
}
printf("%d\n", s);
return 0;
}O(N^2)
Комусь вдалося знайти рішення за O(N), O(1) крім попереднього прорахунку 
Pills
Код:
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN = 100000;
int t[MAXN];
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &t[i]);
}
sort(t, t + n);
long long pills = 0;
for (int i = 0; i < n; i++)
{
pills += abs(t[n/2] - t[i]);
}
printf("%lld\n", pills);
return 0;
}O(NlogN)
У когось є строге математичне доведення, того що оптимальна температура це медіана вибірки, більш того ліва, при непарній кількості елементів?
Schools
Код:
#include <cstdio>
const int MAXN = 100;
const int MAXM = MAXN*MAXN;
const int MAXS = 100;
const int MAXA = 100;
const int INF = MAXM*MAXS*MAXA+1;
int d[MAXN][MAXN], a[MAXN];
inline int min(const int a, const int b){ return a < b ? a : b; }
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
d[i][i] = 0;
for (int j = i+1; j < n; j++)
{
d[i][j] = d[j][i] = INF;
}
}
for (int k = 0; k < m; k++)
{
int i, j, s;
scanf("%d%d%d", &i, &j, &s);
--i; --j;
d[i][j] = d[j][i] = s;
}
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
int answer = 0;
int best = INF;
for (int i = 0; i < n; i++)
{
int current = 0;
for (int j = 0; j < n; j++)
{
current += a[j] * d[j][i];
}
if (current < best){
answer = i;
best = current;
}
}
printf("%d\n", answer+1);
return 0;
}
O(N^3)
Дякую за увагу, хотілося б побачити розв'язки задач Diode і Cake (разом із контрприкладом на 2 вказівника)
Поза форумом
#2 2014-12-20 23:07:18
- FordPerfect
- Новий користувач
- Зареєстрований: 2014-11-15
- Повідомлень: 30
Re: Розв'язки
Приведу свои решения.
Diamonds
Код:
#include <iostream>
int main()
{
long long N,S;
std::cin>>N;
N-=4LL;
S=0LL;
S+=(N+1LL)*(N+2LL)*(N+3LL)*6LL;
S+=(N+1LL)*(N+2LL)*2LL*27LL;
S+=(3LL*59LL+(1LL-2LL*(N%2LL))*27LL)*(N+1LL);
S+=((1LL-2LL*(N%2LL))*108LL);
S+=(((N%3LL)!=1LL)*96LL);
S+=(1LL-(N%4LL))*(N%2LL==0LL)*108LL;
S+=17LL*12LL;
S=S/864LL;
std::cout<<S;
return 0;
}Алгоритмическая сложность: O(1) временная, O(1) памяти.
Cake
Код:
#include <cstdio>
#include <cmath>
static const int MAX=2000;
double r[MAX][2];
int N;
double area(int i,int j,int k)
{
i=i%N;
j=j%N;
k=k%N;
double
dx0=r[j][0]-r[i][0],
dx1=r[k][0]-r[i][0],
dy0=r[j][1]-r[i][1],
dy1=r[k][1]-r[i][1];
return std::abs(dx0*dy1-dx1*dy0)/2.0;
}
int main()
{
int a,b,c;
double S;
scanf("%d",&N);
for(int i=0;i<N;++i)
scanf("%lf%lf",&(r[i][0]),&(r[i][1]));
S=0.0;
a=0;
b=1;
c=2;
do
{
do
{
do;while(area(a,b,c)<=area(a,b,c+1)&&++c);
}while(area(a,b,c)<=area(a,b+1,c)&&++b);
if(S<area(a,b,c)) S=area(a,b,c);
++a;
if(a==b) ++b;
if(b==c) ++c;
}while(a<N&&true);
printf("%lf",S);
return 0;
}Алгоритмическая сложность: O(N) временная, O(N) памяти.
Pill
Код:
#include <cstdlib>
#include <iostream>
#include <algorithm>
const int MAX=100000;
int t[MAX+1];
int main()
{
int N;
long long answer;
std::cin>>N;
for(int i=0;i<N;++i)
std::cin>>t[i];
std::nth_element(t,t+N/2,t+N);
answer=0LL;
for(int i=0;i<N;++i)
answer+=std::abs(t[i]-t[N/2]);
std::cout<<answer;
return 0;
}Алгоритмическая сложность: O(N) временная, O(N) памяти.
Правка: это несколько оптимистично.
Diode
Код:
#include <cstdio>
static const int MAX=1000;
int r[MAX],c[MAX];
int main()
{
int T;
int N,M;
int x,y;
scanf("%d",&T);
for(int t=0;t<T;++t)
{
scanf("%d%d",&N,&M);
for(int i=0;i<N;++i) r[i]=0;
for(int j=0;j<M;++j) c[j]=0;
for(int i=0;i<N;++i)
for(int j=0;j<M;++j)
{
scanf("%d",&x);
r[i]^=x;
c[j]^=x;
}
y=0;
if(M%2==1)
for(int i=1;i<N;++i) y|=(r[i]!=r[0]);
if(N%2==1)
for(int j=1;j<M;++j) y|=(c[j]!=c[0]);
printf("%d",2+y);
}
return 0;
}Алгоритмическая сложность: O(NM) временная, O(N+M) памяти на тест.
Schools
Код:
#include <cstdio>
static const int MAX=100;
int a[MAX];
int d[MAX][MAX];
int main()
{
int n,m;
int x,y;
int c,b,s;
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
d[i][j]=1000000*(i!=j);
for(int i=0;i<m;++i)
{
scanf("%d%d",&x,&y);
scanf("%d",&(d[x-1][y-1]));
d[y-1][x-1]=d[x-1][y-1];
}
for(int i=0;i<n;++i)
a[i]=0;
for(int k=0;k<n;++k)
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
if(d[i][k]+d[k][j]<d[i][j])
d[i][j]=d[i][k]+d[k][j];
for(int i=0;i<n;++i)
scanf("%d",&(a[i]));
s=500000000;
b=-1;
for(int i=0;i<n;++i)
{
c=0;
for(int j=0;j<n;++j)
c+=a[j]*d[i][j];
if(c<s)
{
b=i;
s=c;
}
}
while(b==-1);
printf("%d",b+1);
return 0;
}Алгоритмическая сложность: O(n^3+m) временная, O(n^2+m) памяти.
Примечане: если вмеесто s=500000000; указать s=1000000; (как было у меня в 1-й версии), то решение набирает 38 баллов из 40.
Все 5 указанных решений - полнобалльные, по результату онлайн-проверки.
Відредаговано FordPerfect (2014-12-24 21:51:36)
Поза форумом
#3 2014-12-21 15:03:32
- seland
- Новий користувач
- Зареєстрований: 2012-12-28
- Повідомлень: 14
Re: Розв'язки
infoshoc написав:
У когось є строге математичне доведення, того що оптимальна температура це медіана вибірки, більш того ліва, при непарній кількості елементів?
Насправді, коли непарна кількість коротунів, медіана всього одна 
А коли парна - то неважливо яку з медіан обирати. Насправді можна обрати довільне число між лівою і правою медіаною (для непарної кількості таке число єдине - власне медіана)
Доведення цього таке: Оберемо за кінцеву температуру температуру найхолоднішого коротуна - позначимо Т. Нехай при цьому Т необхідна кількість пігулок К. Тоді при під'йомі температури на 1 градус маємо таку зміну кількості пігулок: всі, кого треба було підвищити, потребують на одну пігулку більше, а всі, кого треба було знизити, потребують на одну пігулку менше. Очевидно, що за нової температури потрібно менше пігулок тоді і тільки тоді, коли кільість коротунів з нижчою за Т температурою менше, ніж їх кількість з вищою за Т. Отже, так будемо підвищувати температуру, доки кількість коротунів "по різні боки" від цієї температури не зрівняється. А це і є медіана (або будь-яке число між медіанами для парної кількості коротунів.
Поза форумом
#4 2014-12-22 15:19:14
- Жюри_Непомнящий
- Журі
- Зареєстрований: 2005-11-03
- Повідомлень: 151
Re: Розв'язки
Идея решения задачи Diode
Пусть m - количество строк, n - количество столбцов матрицы. Будем обозначать (i,j) ход, инвертирующий i-ю строку и j-й столбец.
Рассмотрим три случая.
Случай 1. m и n оба четны.
В этом случае любая матрица m*n приводима. Действительно, если в такой матрице содержится единица в клетке (i,j), то можно добиться того, что содержимое этой клетки станет равным нулю, а содержимое остальных клеток не изменится. Для этого проделаем ходы над клетками, показанными на рисунке (обозначены *).
j
*
*
i * * * * * * * *
*
*
*
j
Элемент матрицы (x,y), не принадлежащий ни i-й строке, ни j-му столбцу, будет проинвертирован дважды - во время ходов (x,j) и (i,y), значит, его значение не изменится. Элемент, принадлежащий i-й строке, и j-му столбцу, будет проинветрирован m+n-1 раз, а поскольку это число нечетное, то этот элемент станет равным нулю. Наконец, элементы i-й строки и j-го столбца будут проинвертированы соответственно n и m раз, т.е. четное число раз, а потому не изменятся.
Применяя вышеописанный способ для всех единиц заданной матрицы, получим матрицу, состоящую из одних нулей.
Случай 2. m и n оба нечетны.
Пусть S - сумма элементов некоторой строки. Тогда произвольный ход (i,j) изменяет четность этой суммы на противоположную. Так, если элемент (i,j) принадлежит рассматриваемой строке, то после хода сумма станет равной n-S. В противном случае сумма увеличится либо уменьшится на 1. Таким образом, если четность сумм всех элементов некоторых двух строк одинакова, она останется одинаковой после любой последовательности ходов. Если четность сумм всех элементов некоторых двух строк различна, она после любой последовательности ходов останется различной. В нулевой матрице все строки имеют одинаковую сумму. Поэтому если в каких-либо двух строках матрицы сумма элементов имеет разную четность, то получить из нее нулевую матрицу невозможно. Аналогичные рассуждения справедливы и для столбцов.
Далее рассмотрим матрицу, у которой суммы элементов всех строк и всех столбцов имеют одну и ту же четность. Очевидно, что если строки имеют четную сумму, то столбцы также имеют четную сумму (поскольку в таком случае сумма всех элементов матрицы четна). Также если строки имеют четную сумму, то и столбцы имеют четную сумму. Произведем приведение к нулевой матрице часть исходной матрицы, показанную на рисунке (всей матрицы, кроме последней строки и последнего столбца) так, как описано в случае 1. Тогда в последней строке и в последнем столбце останутся одинаковые элементы. Если это нули, задача решена, а если нет - необходимо сделать еще один ход - (m,n).
n
*
*
*
*
*
*
m * * * * * * * * *
Случай 3. Одно из чисел m, n четно, а другое нечетно. Пусть количество строк нечетно. Если это не так, то при помощи операции транспонирования можно этого добиться. Заметим, что транспонирование не влияет на приводимость и неприводимость матрицы.
Как и в случае 2, произвольный ход изменяет на противоположную четность суммы любого столбца. Поэтому если эта четность в двух столбцах матрицы разная, то такая матрица неприводима. Если же в матрице все столбцы имеют одну и ту же четность, то произведем приведение к нулевой матрице часть исходной матрицы, показанную на рисунке (всей матрицы, кроме последней строки) так, как описано в случае 1. Тогда в последней строке все числа будут одинаковыми. Если это нули, задача решена. Если же это единицы, то произведем ходы над элементами, показанными на нижнем рисунке.
n
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
m
n
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
m *
Поза форумом
#6 2014-12-24 21:12:05
- FordPerfect
- Новий користувач
- Зареєстрований: 2014-11-15
- Повідомлень: 30
Re: Розв'язки
Некоторые комментарии к моим решениям, вдруг кому интересно.
Diamonds
Используется явная формула:
Беглый взгляд на Википедию выясняет, что искомая величина носит название Restricted Partitions:
http://en.wikipedia.org/wiki/Partition_(number_theory)#Restricted_part_size_or_number_of_parts
Собственно, явные формулы для k<=4 приведены на:
http://mathworld.wolfram.com/PartitionFunctionP.html
Если есть желание получить подобные формулы самостоятельно, то в Википедии по ссылке выше приведена формула для её производящей функции ( http://ru.wikipedia.org/wiki/Производящ … ательности ). Соответственно, n-й элемент может быть получен как n-й коэффициент ряда Тейлора для этой функции, который легко получить в каком-нибудь пакете символьной алгебры.
Если интересно, каким образом получены эти коэффициенты, то одним способом является, например, разложение на простые дроби (partial fraction decomposition) этой функции, после чего коэффициенты ряда Тейлора для индивидуальных слагаемых получаются тривиально (см. например: Hardy, G.H. Some Famous Problems of the Theory of Numbers. Clarendon Press, 1920. ).
http://uk.wikipedia.org/wiki/Розкладанн … ості_дроби
Приведу явные формулы для разбиений на 1..10 частей:
Код:
SeriesCoefficient[1/((1 - x)), {x, 0, n}]
1
SeriesCoefficient[1/((1 - x) (1 - x^2)), {x, 0, n}]
1/4 (3 + (-1)^n + 2 n)
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3)), {x, 0, n}]
1/72 (47 + 9 (-1)^n + 36 n + 6 n^2 + 16 Cos[(2 n \[Pi])/3])
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4)), {x, 0, n}]
1/864 (3 (5 + n) (35 + 9 (-1)^n + 2 n (10 + n)) + 108 Cos[(n \[Pi])/2] + 64 Cos[(2 n \[Pi])/3] - 64 Cos[2/3 (1 + n) \[Pi]])
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4) (1 - x^5)), {x, 0, n}]
(50651 + 38250 n + 9300 n^2 + 900 n^3 + 30 n^4 + 5400 Cos[(n \[Pi])/2] + (-1)^n (6912 Cos[(n \[Pi])/5] + 6400 Cos[(n \[Pi])/3] + 27 (375 + 50 n + 256 Cos[(3 n \[Pi])/5])) + 5400 Sin[(n \[Pi])/2])/86400
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4) (1 - x^5) (1 - x^6)), {x, 0, n}]
(1/3110400)(12800 (21 + 2 n) Cos[(2 n \[Pi])/3] - 6400 (23 + 2 n) Cos[2/3 (1 + n) \[Pi]] + 6400 (19 + 2 n) Cos[1/3 (1 + 2 n) \[Pi]] + (124416 (Cos[(2 n \[Pi])/5] + Cos[(4 n \[Pi])/5] - Cos[2/5 (1 + n) \[Pi]] - Cos[4/5 (1 + n) \[Pi]] - Cos[1/5 (1 + 4 n) \[Pi]] + Cos[1/5 (3 + 4 n) \[Pi]]))/(1 + Cos[(3 \[Pi])/5]) + 3 (598731 + 439810 n + 110250 n^2 + 12320 n^3 + 630 n^4 + 12 n^5 + 225 (-1)^n (581 + 6 n (21 + n)) + 57600 Cos[(n \[Pi])/3] + 32400 Cos[(n \[Pi])/2] + 32400 Sin[(n \[Pi])/2]))
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4) (1 - x^5) (1 - x^6) (1 - x^7)), {x, 0, n}]
19554517/76204800 + (215 (-1)^n)/2304 + (2435 (1 + n))/13824 + (25 (-1)^n (1 + n))/1536 + (16051 (1 + n) (2 + n))/345600 + ((-1)^n (1 + n) (2 + n))/1536 + (161 (1 + n) (2 + n) (3 + n))/25920 + (47 (1 + n) (2 + n) (3 + n) (4 + n))/103680 + ((1 + n) (2 + n) (3 + n) (4 + n) (5 + n))/57600 + ((1 + n) (2 + n) (3 + n) (4 + n) (5 + n) (6 + n))/3628800 + 1/32 Cos[(n \[Pi])/2] + 2/49 (Cos[(2 n \[Pi])/7] + Cos[(4 n \[Pi])/7] + Cos[(6 n \[Pi])/7]) + 1/243 (1 + n) (Cos[(2 n \[Pi])/3] - Cos[2/3 (1 + n) \[Pi]]) + (83 Cos[(2 n \[Pi])/3] - 73 Cos[2/3 (1 + n) \[Pi]] + 10 Cos[1/3 (1 + 2 n) \[Pi]])/1458 + 1/36 (Cos[(5 n \[Pi])/3] - Cos[1/3 (2 + n) \[Pi]] + Cos[1/3 (2 + 5 n) \[Pi]]) + 1/(125 (-1 + Cos[(2 \[Pi])/5])) (-3 Cos[(2 n \[Pi])/5] - 2 Cos[(4 n \[Pi])/5] + 2 Cos[2/5 (1 + n) \[Pi]] + 3 Cos[4/5 (1 + n) \[Pi]] + 2 Cos[2/5 (2 + n) \[Pi]] + 3 Cos[1/5 (1 + 2 n) \[Pi]] - 2 (Cos[2/5 (1 + 2 n) \[Pi]] + Cos[1/5 (3 + 2 n) \[Pi]] - Cos[1/5 (1 + 4 n) \[Pi]]) - 3 Cos[1/5 (3 + 4 n) \[Pi]])
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4) (1 - x^5) (1 - x^6) (1 - x^7) (1 - x^8)), {x, 0, n}]
80858443/304819200 + (833 (-1)^n)/9216 + (53368943 (1 + n))/304819200 + (181 (-1)^n (1 + n))/9216 + (859 (1 + n) (2 + n))/19200 + 1/768 (-1)^n (1 + n) (2 + n) + (49271 (1 + n) (2 + n) (3 + n))/8294400 + ((-1)^n (1 + n) (2 + n) (3 + n))/36864 + (25 (1 + n) (2 + n) (3 + n) (4 + n))/55296 + (83 (1 + n) (2 + n) (3 + n) (4 + n) (5 + n))/4147200 + ((1 + n) (2 + n) (3 + n) (4 + n) (5 + n) (6 + n))/2073600 + ((1 + n) (2 + n) (3 + n) (4 + n) (5 + n) (6 + n) (7 + n))/203212800 + 1/128 (Cos[(n \[Pi])/2] + 1/2 n Cos[(n \[Pi])/2]) + 1/32 (Cos[(n \[Pi])/4] + Cos[(3 n \[Pi])/4]) + (66 Cos[(2 n \[Pi])/3] - 37 Cos[2/3 (1 + n) \[Pi]] + 29 Cos[1/3 (1 + 2 n) \[Pi]])/1458 + 1/729 ((3 + 2 n) Cos[(2 n \[Pi])/3] - (1 + n) Cos[2/3 (1 + n) \[Pi]] + (2 + n) Cos[1/3 (1 + 2 n) \[Pi]]) + 1/108 (-Cos[1/3 (2 + n) \[Pi]] - Cos[1/3 (7 + n) \[Pi]] + Cos[1/3 (1 + 5 n) \[Pi]] + Cos[1/3 (2 + 5 n) \[Pi]]) - (1/(49 (-2 + Cos[\[Pi]/7] - 2 Sin[\[Pi]/14] + Sin[(3 \[Pi])/14])))(2 Cos[(2 n \[Pi])/7] + 2 Cos[(4 n \[Pi])/7] + 2 Cos[(6 n \[Pi])/7] - 2 Cos[2/7 (1 + n) \[Pi]] - 2 Cos[4/7 (1 + n) \[Pi]] - 2 Cos[6/7 (1 + n) \[Pi]] - Cos[2/7 (2 + n) \[Pi]] + Cos[2/7 (3 + n) \[Pi]] + Cos[1/7 (3 + 2 n) \[Pi]] + Cos[2/7 (3 + 2 n) \[Pi]] - Cos[1/7 (5 + 2 n) \[Pi]] + 2 Cos[2/7 (1 + 3 n) \[Pi]] - 2 Cos[2/7 (2 + 3 n) \[Pi]] + Cos[1/7 (5 + 4 n) \[Pi]] - 3 Cos[1/7 (1 + 6 n) \[Pi]] + 3 Cos[1/7 (5 + 6 n) \[Pi]]) + 1/128 (8 Cos[(n \[Pi])/2] + Sin[(n \[Pi])/2]) + (Cos[2/5 (-1 + n) \[Pi]] - 3 Cos[(2 n \[Pi])/5] - 2 Cos[(4 n \[Pi])/5] + 3 Cos[2/5 (1 + n) \[Pi]] + 2 Cos[4/5 (1 + n) \[Pi]] - Cos[2/5 (2 + n) \[Pi]] + Cos[1/5 (1 + 4 n) \[Pi]] + Sin[1/10 (\[Pi] + 8 n \[Pi])])/(125 (-1 + Cos[(2 \[Pi])/5]))
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4) (1 - x^5) (1 - x^6) (1 - x^7) (1 - x^8) (1 - x^9)), {x, 0, n}]
120223922309/438939648000 + (26531 (-1)^n)/294912 + (4093 (1 + n))/23328 + (2339 (-1)^n (1 + n))/147456 + (9585257 (1 + n) (2 + n))/219469824 + (41 (-1)^n (1 + n) (2 + n))/49152 + (29969 (1 + n) (2 + n) (3 + n))/5225472 + ((-1)^n (1 + n) (2 + n) (3 + n))/73728 + (929377 (1 + n) (2 + n) (3 + n) (4 + n))/2090188800 + (1843 (1 + n) (2 + n) (3 + n) (4 + n) (5 + n))/87091200 + (319 (1 + n) (2 + n) (3 + n) (4 + n) (5 + n) (6 + n))/522547200 + ((1 + n) (2 + n) (3 + n) (4 + n) (5 + n) (6 + n) (7 + n))/101606400 + ((1 + n) (2 + n) (3 + n) (4 + n) (5 + n) (6 + n) (7 + n) (8 + n))/14631321600 + 2/81 (Cos[(2 n \[Pi])/9] + Cos[(4 n \[Pi])/9] + Cos[(8 n \[Pi])/9]) + 1/108 (Cos[1/3 (4 + n) \[Pi]] + Cos[1/3 (5 + n) \[Pi]]) + (1514 Cos[(2 n \[Pi])/3] - 925 Cos[2/3 (1 + n) \[Pi]] + 589 Cos[1/3 (1 + 2 n) \[Pi]])/26244 + ((1 + n) (2 (3 + n) Cos[(2 n \[Pi])/3] - (4 + n) Cos[2/3 (1 + n) \[Pi]] + (2 + n) Cos[1/3 (1 + 2 n) \[Pi]]))/13122 + ((121 + 82 n) Cos[(2 n \[Pi])/3] - 43 (1 + n) Cos[2/3 (1 + n) \[Pi]] + 39 (2 + n) Cos[1/3 (1 + 2 n) \[Pi]])/13122 + (1/(49 (-2 + Cos[\[Pi]/7] - 2 Sin[\[Pi]/14] + Sin[(3 \[Pi])/14])))(-Cos[(2 n \[Pi])/7] - Cos[(4 n \[Pi])/7] + Cos[2/7 (1 + n) \[Pi]] + Cos[4/7 (1 + n) \[Pi]] + 2 Cos[6/7 (1 + n) \[Pi]] + Cos[2/7 (2 + n) \[Pi]] - Cos[2/7 (3 + n) \[Pi]] + Cos[2/7 (1 + 2 n) \[Pi]] + Cos[3/7 (1 + 2 n) \[Pi]] - 2 Cos[2/7 (3 + 2 n) \[Pi]] - 2 Cos[2/7 (1 + 3 n) \[Pi]] - Cos[1/7 (1 + 4 n) \[Pi]] - Cos[1/7 (3 + 4 n) \[Pi]] + Cos[1/7 (5 + 4 n) \[Pi]] + Cos[1/7 (1 + 6 n) \[Pi]] - 2 Cos[1/7 (5 + 6 n) \[Pi]]) + 1/512 (23 Cos[(n \[Pi])/2] + 19 Sin[(n \[Pi])/2]) + 1/512 ((2 + n) Cos[(n \[Pi])/2] + (1 + n) Sin[(n \[Pi])/2]) + 1/64 (Cos[(n \[Pi])/4] + Cos[(3 n \[Pi])/4] - Cos[1/4 (1 + n) \[Pi]] - Cos[3/4 (1 + n) \[Pi]] - Cos[1/4 (3 + n) \[Pi]] - Cos[1/4 (1 + 3 n) \[Pi]] + Sin[(n \[Pi])/4] - Sin[(3 n \[Pi])/4]) + (Cos[2/5 (-1 + n) \[Pi]] - 2 Cos[(2 n \[Pi])/5] - 2 Cos[(4 n \[Pi])/5] + Cos[2/5 (1 + n) \[Pi]] + Cos[2/5 (1 + 2 n) \[Pi]] + Sin[1/10 (\[Pi] + 8 n \[Pi])])/(125 (-1 + Cos[(2 \[Pi])/5]))
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4) (1 - x^5) (1 - x^6) (1 - x^7) (1 - x^8) (1 - x^9) (1 - x^10)), {x, 0, n}]
2477301615071/8778792960000 + (7622711 (-1)^n)/88473600 + 1/256 (7 Cos[(n \[Pi])/2] + 6 Sin[(n \[Pi])/2]) + 1/32 (1/2 (-Cos[1/4 (1 + n) \[Pi]] + Sin[(n \[Pi])/4] - Sin[(3 n \[Pi])/4] + Sin[1/4 (\[Pi] + 3 n \[Pi])])) + 1/216 (Cos[( n \[Pi])/3] - Cos[1/3 (2 + n) \[Pi]] - Cos[1/3 (1 + n) \[Pi]]) + 1/27 (-(1/(-45 + 42 Cos[\[Pi]/9] - 6 Cos[(2 \[Pi])/9] + 48 Sin[\[Pi]/18]))2 (5 Cos[(2 n \[Pi])/9] + 5 Cos[(4 n \[Pi])/9] + 5 Cos[(8 n \[Pi])/9] - 5 Cos[2/9 (1 + n) \[Pi]] - 5 Cos[4/9 (1 + n) \[Pi]] - 5 Cos[8/9 (1 + n) \[Pi]] - 6 Cos[2/9 (2 + n) \[Pi]] + 3 Cos[4/9 (2 + n) \[Pi]] + 2 Cos[2/9 (3 + n) \[Pi]] + 7 Cos[2/9 (4 + n) \[Pi]] + 7 Cos[1/9 (3 + 2 n) \[Pi]] + 2 Cos[1/9 (5 + 2 n) \[Pi]] - 6 Cos[1/9 (7 + 2 n) \[Pi]] - 4 Cos[1/9 (1 + 4 n) \[Pi]] + 13 Cos[2/9 (1 + 4 n) \[Pi]] + 4 Cos[1/9 (3 + 4 n) \[Pi]] - 13 Cos[2/9 (3 + 4 n) \[Pi]] + 3 Cos[1/9 (5 + 4 n) \[Pi]] - 12 Cos[1/9 (1 + 8 n) \[Pi]] - 8 Cos[1/9 (3 + 8 n) \[Pi]] + 8 Cos[1/9 (5 + 8 n) \[Pi]] + 12 Cos[1/9 (7 + 8 n) \[Pi]] + Sin[1/18 (3 + 8 n) \[Pi]] + Sin[1/18 (5 + 8 n) \[Pi]])) + (878 Cos[(2 n \[Pi])/3] - 2158/3 Cos[2/3 (1 + n) \[Pi]] + 476/3 Cos[1/3 (1 + 2 n) \[Pi]])/17496 + 1/100 (2 (Cos[(n \[Pi])/5] + Cos[(3 n \[Pi])/5])) + (1/2500)1/(-1 + Cos[(2 \[Pi])/5]) (-100 Cos[(2 n \[Pi])/5] - 100 Cos[(4 n \[Pi])/5] + 55 Cos[2/5 (1 + n) \[Pi]] + 14 Cos[4/5 (1 + n) \[Pi]] + 4 Cos[2/5 (2 + n) \[Pi]] + 4 Cos[1/5 (1 + 2 n) \[Pi]] + 41 Cos[2/5 (1 + 2 n) \[Pi]] - 45 Cos[1/5 (3 + 2 n) \[Pi]] + 14 Cos[1/5 (1 + 4 n) \[Pi]] - 59 Cos[1/5 (3 + 4 n) \[Pi]]) + 1/49 (1/(-2 + Cos[\[Pi]/7] - 2 Sin[\[Pi]/14] + Sin[(3 \[Pi])/14]) (Cos[2/7 (-1 + n) \[Pi]] - Cos[(2 n \[Pi])/7] - Cos[(4 n \[Pi])/7] + Cos[4/7 (1 + n) \[Pi]] + Cos[6/7 (1 + n) \[Pi]] + Cos[2/7 (2 + n) \[Pi]] + Cos[1/7 (1 + 2 n) \[Pi]] + Cos[3/7 (1 + 2 n) \[Pi]] - Cos[2/7 (1 + 3 n) \[Pi]] - Cos[1/7 (3 + 4 n) \[Pi]] + Sin[1/14 (5 + 8 n) \[Pi]] + Sin[3/14 (\[Pi] + 4 n \[Pi])])) + (15829067723 (1 + n))/89579520000 + (2587 (-1)^n (1 + n))/147456 + (6295714261 (1 + n) (2 + n))/146313216000 + (709 (-1)^n (1 + n) (2 + n))/589824 + (3675182783 (1 + n) (2 + n) (3 + n))/658409472000 + (5 (-1)^n (1 + n) (2 + n) (3 + n))/147456 + (1301279 (1 + n) (2 + n) (3 + n) (4 + n))/2985984000 + ((-1)^n (1 + n) (2 + n) (3 + n) (4 + n))/2949120 + (161111 (1 + n) (2 + n) (3 + n) (4 + n) (5 + n))/7464960000 + (2867 (1 + n) (2 + n) (3 + n) (4 + n) (5 + n) (6 + n))/4180377600 + (199 (1 + n) (2 + n) (3 + n) (4 + n) (5 + n) (6 + n) (7 + n))/14631321600 + ((1 + n) (2 + n) (3 + n) (4 + n) (5 + n) (6 + n) (7 + n) (8 + n))/6502809600 + ((1 + n) (2 + n) (3 + n) (4 + n) (5 + n) (6 + n) (7 + n) (8 + n) (9 + n))/1316818944000 + 1/512 (1/2 ((2 + n) Cos[(n \[Pi])/2] + (1 + n) Sin[(n \[Pi])/2])) + (2/9 ((183 + 163 n) Cos[(2 n \[Pi])/3] - 143 (1 + n) Cos[2/3 (1 + n) \[Pi]] + 20 (2 + n) Cos[1/3 (1 + 2 n) \[Pi]]))/8748 + 1/250 (1/(5 (-5 + 3 Cos[\[Pi]/5] + 8 Cos[(2 \[Pi])/5])) (-5 (5 + 2 n) Cos[(2 n \[Pi])/5] - 5 (5 + 2 n) Cos[(4 n \[Pi])/5] + 19 Cos[2/5 (1 + n) \[Pi]] + 8 n Cos[2/5 (1 + n) \[Pi]] - 14 Cos[4/5 (1 + n) \[Pi]] - 3 n Cos[4/5 (1 + n) \[Pi]] - 6 Cos[2/5 (2 + n) \[Pi]] - 3 n Cos[2/5 (2 + n) \[Pi]] + 9 Cos[1/5 (1 + 2 n) \[Pi]] + 3 n Cos[1/5 (1 + 2 n) \[Pi]] + 24 Cos[2/5 (1 + 2 n) \[Pi]] + 8 n Cos[2/5 (1 + 2 n) \[Pi]] - 21 Cos[1/5 (3 + 2 n) \[Pi]] - 8 n Cos[1/5 (3 + 2 n) \[Pi]] + Cos[1/5 (1 + 4 n) \[Pi]] + 3 n Cos[1/5 (1 + 4 n) \[Pi]] - 8 (2 + n) Cos[1/5 (3 + 4 n) \[Pi]])) + (1/9 (n (3 + n) Cos[(2 n \[Pi])/3] - (1 + n) (4 + n) Cos[2/3 (1 + n) \[Pi]] - 2 (2 + n) Cos[1/3 (1 + 2 n) \[Pi]]))/1458Или, в альтернативной форме:
Код:
SeriesCoefficient[1/((1 - x)), {x, 0, n}]
1
SeriesCoefficient[1/((1 - x) (1 - x^2)), {x, 0, n}]
1/4 (3 + 2 n + switch[{1, -1}])
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3)), {x, 0, n}]
1/72 (47 + 6 n (6 + n) + 9 switch[{1, -1}] + 8 switch[{2, -1, -1}])
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4)), {x, 0, n}]
1/288 ((5 + n) (35 + 2 n (10 + n)) + 9 (5 + n) switch[{1, -1}] + 32 switch[{1, 0, -1}] + 36 switch[{1, 0, -1, 0}])
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4) (1 - x^5)), {x, 0, n}]
(50651 + 30 n (15 + n) (85 + n (15 + n)) + 675 (15 + 2 n) switch[{1, -1}] + 3200 switch[{2, -1, -1}] + 5400 switch[{1, 1, -1, -1}] + 3456 switch[{4, -1, -1, -1, -1}])/86400
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4) (1 - x^5) (1 - x^6)), {x, 0, n}]
1/1036800 ((21 + 2 n) (28511 + 2 n (21 + n) (434 + 3 n (21 + n))) + 225 (581 + 6 n (21 + n)) switch[{1, -1}] + 3200 switch[{42 + 4 n, -19 - 2 n, -23 - 2 n}] + 32400 switch[{1, 1, -1, -1}] + 41472 switch[{2, 1, 0, -1, -2}] + 28800 switch[{2, 1, -1, -2, -1, 1}])
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4) (1 - x^5) (1 - x^6) (1 - x^7)), {x, 0, n}]
1/152409600 (87797891 + 21 n (28 + n) (106715 + 2 n (28 + n) (413 + n (28 + n))) + 33075 (511 + 3 n (28 + n)) switch[{1, -1}] + 156800 switch[{89 + 6 n, -10, -79 - 6 n}] + 4762800 switch[{1, 0, -1, 0}] + 6096384 switch[{1, 0, 1, -1, -1}] + 4233600 switch[{1, 2, 1, -1, -2, -1}] + 3110400 switch[{6, -1, -1, -1, -1, -1, -1}])
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4) (1 - x^5) (1 - x^6) (1 - x^7) (1 - x^8)), {x, 0, n}]
(1/1219276800)((18 + n) (39226571 + 3 n (36 + n) (232991 + 2 n (36 + n) (615 + n (36 + n)))) + 33075 (18 + n) (231 + n (36 + n)) switch[{1, -1}] + 1254400 switch[{4 (18 + n), -33 - 2 n, -39 - 2 n}] + 4762800 switch[{18 + n, 2, -18 - n, -2}] + 48771072 switch[{1, 0, 0, 0, -1}] + 33868800 switch[{0, 1, 1, 0, -1, -1}] + 24883200 switch[{3, 2, 1, 0, -1, -2, -3}] + 76204800 switch[{1, 0, 0, 0, -1, 0, 0, 0}])
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4) (1 - x^5) (1 - x^6) (1 - x^7) (1 - x^8) (1 - x^9)), {x, 0, n}]
(1/438939648000)(256697834389 + 10 n (45 + n) (389006170 + 3 n (45 + n) (655163 + n (45 + n) (1360 + n (45 + n)))) + 1488375 (45 + 2 n) (705 + 2 n (45 + n)) switch[{1, -1}] + 25088000 switch[{4 (442 + n (45 + n)), -749 - 2 n (42 + n), -1019 - 2 n (48 + n)}] + 857304000 switch[{25 + n, 20 + n, -25 - n, -20 - n}] + 3511517184 switch[{4, -1, -1, -1, -1}] + 6096384000 switch[{0, 1, 1, 0, -1, -1}] + 8957952000 switch[{1, 0, 2, 0, 1, -2, -2}] + 13716864000 switch[{1, 1, 1, 1, -1, -1, -1, -1}] + 16257024000 switch[{2, 0, 0, -1, 0, 0, -1, 0, 0}])
SeriesCoefficient[1/((1 - x) (1 - x^2) (1 - x^3) (1 - x^4) (1 - x^5) (1 - x^6) (1 - x^7) (1 - x^8) (1 - x^9) (1 - x^10)), {x, 0, n}]
(1/26336378880000)((55 + 2 n) (283505364417 + 2 n (55 + n) (1631423750 + n (55 + n) (6133842 + 5 n (55 + n) (1870 + n (55 + n))))) + 297675 (9406331 + 30 n (55 + n) (1155 + n (55 + n))) switch[{1, -1}] + 501760000 switch[{4317 + 344 n + 6 n^2, -14 (55 + 2 n), -3547 - 2 n (158 + 3 n)}] + 25719120000 switch[{30 + n, 25 + n, -30 - n, -25 - n}] +
10534551552 switch[{220 + 8 n, -39 - 2 n, -43 - 2 n, -67 - 2 n, -71 - 2 n}] + 121927680000 switch[{1, 2, 1, -1, -2, -1}] + 537477120000 switch[{1, -1, 1, 1, 0, -1, -1}] +
823011840000 switch[{0, 0, 1, 1, 0, 0, -1, -1}] + 975421440000 switch[{1, 1, 1, 0, 0, 0, -1, -1, -1}] + 263363788800 switch[{4, 1, -1, 1, -1, -4, -1, 1, -1, 1}])Дополнительная литература:
Hardy, G.H. Some Famous Problems of the Theory of Numbers. Clarendon Press, 1920.
Researches on the Partition of Numbers. Cayley, A Philosophical Transactions of the Royal Society of London (1776-1886). 1856-01-01. 146:127–140
G. E. Andrews (1976) The Theory of Partitions. Encyclopedia of Mathematics and its Applications, Vol. 2, Addison-Wesley Publishing Co., Reading, MA-London-Amsterdam.
http://mathworld.wolfram.com/PartitionFunctionP.html
http://www.genfunc.ru/
Cake
При написании решения я пытается максимально близко следовать алгоритму из классической статьи:
On a general method for maximizing and minimizing among certain geometric problems, David P. Dobkin, Lawrence Snyder, SFCS '79 Proceedings of the 20th Annual Symposium on Foundations of Computer Science, Pages 9-17
Откуда и происходит несколько своеобразный синтаксис решения.
Pill
Решение использует std::nth_element ( http://en.cppreference.com/w/cpp/algorithm/nth_element ) с целью получения линейной сложности (хотя стандарт C++ гарантирует только линейную среднюю сложность). Реализации, гарантирующие O(n) в худшем случае (Median of medians) также существуют, но использованы не были.
Diode
К разбору, который привёл Жюри_Непомнящий, могу только добавить, что:
1. Я получил идею решения, реализовав решатель систем линейных уравнений по модулю 2, после чего вглядывался (заметное время) в вырожденные (нулевые) строки матрицы и соответствующие им суммы свободных членов, в поисках определяемых ими инвариантов.
2. Строгого доказательства корректности результирующего алгоритма я вплоть до прочтения разбора Жюри_Непомнящий не знал.
Schools
Как легко видеть, используется алгоритм Флойда-Уоршелла.
Он проходит тесты на онлайн проверке (с 3-кратным запасом)
Код:
Тест Результат Время работы 00 PASSED (+0) 0.01 сек. 01 PASSED (+1) 0.01 сек. 02 PASSED (+1) 0.01 сек. 03 PASSED (+1) 0.01 сек. 04 PASSED (+1) 0.01 сек. 05 PASSED (+1) 0.01 сек. 06 PASSED (+1) 0.01 сек. 07 PASSED (+1) 0.01 сек. 08 PASSED (+1) 0.01 сек. 09 PASSED (+1) 0.01 сек. 10 PASSED (+1) 0.01 сек. 11 PASSED (+1) 0.01 сек. 12 PASSED (+1) 0.01 сек. 13 PASSED (+1) 0.01 сек. 14 PASSED (+1) 0.01 сек. 15 PASSED (+1) 0.01 сек. 16 PASSED (+1) 0.01 сек. 17 PASSED (+1) 0.01 сек. 18 PASSED (+1) 0.01 сек. 19 PASSED (+1) 0.01 сек. 20 PASSED (+1) 0.01 сек. 21 PASSED (+1) 0.02 сек. 22 PASSED (+1) 0.01 сек. 23 PASSED (+1) 0.01 сек. 24 PASSED (+1) 0.01 сек. 25 PASSED (+1) 0.02 сек. 26 PASSED (+1) 0.02 сек. 27 PASSED (+1) 0.02 сек. 28 PASSED (+1) 0.01 сек. 29 PASSED (+1) 0.01 сек. 30 PASSED (+1) 0.01 сек. 31 PASSED (+1) 0.01 сек. 32 PASSED (+1) 0.01 сек. 33 PASSED (+1) 0.02 сек. 34 PASSED (+1) 0.01 сек. 35 PASSED (+1) 0.01 сек. 36 PASSED (+1) 0.01 сек. 37 PASSED (+1) 0.01 сек. 38 PASSED (+1) 0.02 сек. 39 PASSED (+1) 0.03 сек. 40 PASSED (+1) 0.03 сек.
Код:
Тест Результат Время работы 00 FAILED (Time Out) 0.12 сек. 01 FAILED (Time Out) 0.12 сек. 02 FAILED (Time Out) 0.12 сек. 03 FAILED (Time Out) 0.12 сек. 04 FAILED (Time Out) 0.12 сек. 05 FAILED (Time Out) 0.12 сек. 06 FAILED (Time Out) 0.11 сек. 07 FAILED (Time Out) 0.12 сек. 08 FAILED (Time Out) 0.11 сек. 09 FAILED (Time Out) 0.12 сек. 10 FAILED (Time Out) 0.11 сек. 11 FAILED (Time Out) 0.11 сек. 12 FAILED (Time Out) 0.12 сек. 13 FAILED (Time Out) 0.12 сек. 14 FAILED (Time Out) 0.12 сек. 15 FAILED (Time Out) 0.12 сек. 16 FAILED (Time Out) 0.12 сек. 17 FAILED (Time Out) 0.12 сек. 18 FAILED (Time Out) 0.12 сек. 19 FAILED (Time Out) 0.12 сек. 20 FAILED (Time Out) 0.12 сек. 21 FAILED (Time Out) 0.12 сек. 22 FAILED (Time Out) 0.12 сек. 23 FAILED (Time Out) 0.11 сек. 24 FAILED (Time Out) 0.12 сек. 25 FAILED (Time Out) 0.12 сек. 26 FAILED (Time Out) 0.12 сек. 27 FAILED (Time Out) 0.12 сек. 28 FAILED (Time Out) 0.12 сек. 29 FAILED (Time Out) 0.12 сек. 30 FAILED (Time Out) 0.12 сек. 31 FAILED (Time Out) 0.12 сек. 32 FAILED (Time Out) 0.12 сек. 33 FAILED (Time Out) 0.11 сек. 34 FAILED (Time Out) 0.12 сек. 35 FAILED (Time Out) 0.12 сек. 36 FAILED (Time Out) 0.11 сек. 37 FAILED (Time Out) 0.11 сек. 38 FAILED (Time Out) 0.11 сек. 39 FAILED (Time Out) 0.11 сек. 40 FAILED (Time Out) 0.11 сек.
При том, что тесты:
01, 02, 04, 05, 09, 10, 11, 12, 28, 29, 30, 31, 32, 33
удовлетворяют условию m=n-1.
Для подобных входных данных алгоритм Джонсона
http://en.wikipedia.org/wiki/Johnson's_algorithm
https://ru.wikipedia.org/wiki/Алгоритм_Джонсона
http://uk.wikipedia.org/wiki/Алгоритм_Джонсона
имеет более низкую алгоритмическую сложность (O(n^2 log(n)) вместо O(n^3)).
Правка: орфография.
Правка^2: улучшена типография формулы.
Відредаговано FordPerfect (2014-12-25 00:14:30)
Поза форумом
#7 2014-12-25 19:00:12
Re: Розв'язки
Стосовно Diamonds
Зробивши перебір перших варіантів в «ручному режимі», або, використавши для цього примітивну програмку отримаємо наступний числовий ряд:
1 1 2 3 5 6 9 11 15
члени якого вираховуються за формулою:
a(n)= 1+(a(n-2)+a(n-3)+a(n-4)) – (a(n-5)+a(n-6)+a(n-7)) + a(n-9)
Код:
#include <iostream>
using namespace std;
int main ()
{
long a[6768]={};
int N;
cin >> N;
for(int n=10; n<=N+6; n++)
a[n]=1+(a[n-2]+a[n-3]+a[n-4])-(a[n-5]+a[n-6]+a[n-7])+a[n-9];
cout << a[N+6];
return 0;
}Код:
Тест Результат Время работы 00 PASSED (+0) 0.01 сек. 000 PASSED (+0) 0.01 сек. 01 PASSED (+4) 0.01 сек. 02 PASSED (+4) 0.01 сек. 03 PASSED (+4) 0.01 сек. 04 PASSED (+4) 0.01 сек. 05 PASSED (+4) 0.01 сек. 06 PASSED (+5) 0.01 сек. 07 PASSED (+5) 0.01 сек. 08 PASSED (+5) 0.01 сек. 09 PASSED (+5) 0.01 сек.
Відредаговано LVV (2014-12-25 19:31:37)
Вік живи - вік навчайся.
Поза форумом
#8 2014-12-27 18:15:10
Re: Розв'язки
Diamonds
var s,b,c,d,i1,i3,i,n,k,t:longint; i2:int64; a:array[0..100000]of int64;
begin
read(n); s:=3; a[1]:=1; k:=0; t:=0;
if(n mod 4=0)then begin
for i1:=2 to n div 4 do
begin
inc(k);
if((i1-1 ) mod 3=1)and(i1<>2)then inc(t); a[i1]:=a[i1-1]+s*k-t; end;
for i:=1 to n div 4 do
i2:=i2+a[i]; end;
if(n mod 4=1)then begin
for i1:=2 to (n-1) div 4 do
begin
inc(k);
if((i1-1) mod 3=0)then inc(t); a[i1]:=a[i1-1]+s*k-t+1; end;
for i:=1 to n div 4 do
i2:=i2+a[i]; end;
a[1]:=2; // второй круг(начальное количество вариантов при N=6)
if(n mod 4=2)then begin
for i1:=2 to (n-2) div 4 do
begin
inc(k);
if(i1 mod 3=0)then inc(t); a[i1]:=a[i1-1]+s*k-t+2; end;
for i:=1 to n div 4 do
i2:=i2+a[i]; end;
a[1]:=3; // третий круг(начальное количество вариантов при N=7)
if(n mod 4=3)then begin
for i1:=2 to (n-3) div 4 do
begin
inc(k);
if((i1-1) mod 3=1)then inc(t); a[i1]:=a[i1-1]+s*k-t+3; end;
for i:=1 to n div 4 do
i2:=i2+a[i]; end;
write(i2);
end.
Поза форумом