Брой 26 на Списание Инфоман
 


Национална Олимпиада по Информатика 2004, Задача 2.3. БРОЙ

Уловието на задачата може да прочетете тук.

Решение

Дадена е редицата от числа A1, A2,..., A2n. Ai Î [0;p]. Нека Si..j е сумата на числата от Ai до Aj. От всички редици A1, A2,..., A2n, ние се интересуваме от тези, за които е изпълнено S1..n – Sn+1..2n = k. И по-точно се интересуваме от техния брой.

Първо ще решим една друга задача и ще покажем как може да я използваме за решаването на горе-описаната задача. Задачата, която ще решим е следната. Колко са различните редици от N числа A1, A2,...An, Ai Î [0;p], които имат сума на членовете на редицата X. Ще дефинираме функцията F(n,x), която ни дава търсения отговор за n числа и сума x. F(0,0) = 1 и F(0,x) = 0 за x ≠ 0. За n > 0, F(n,x) може да изчислим като присвоим на последното число в редицата всяка възможна стойност. А именно F(n,x) е равна на сумата от F(n-1,x-i), за всяко i от интервала [0;p]. Очевидно F(n,x) = 0, за x > n.p, понеже сума на n числа, всяко не по-голямо от p не може да е по-голяма от n.p. Също F(n,x) = 0, за x < 0, понеже всички числа от редицата са неотрицателни. След като дефинирахме рекурентната зависимост за функцията F(n,x), може чрез метода на динамичното оптимиране да изчислим последователно стойностите на функцията за всяко n и x Î [0;n.p].

Как може да използваме вече изчислената функция F в оригиналната задача. Ако сумата на първата половина от числа е равна на 0, то сумата на втората половина трябва да е k. И броят на различните решения за сума 0 на първата половина и сума k на втората е F(n,0).F(n,-k). Аналогично ако първата половина има сума 1, втората трябва да има сума 1-k и броят на различните решения е F(n,1).F(n,1-k). Аналогично за всички възможни сума на първата половина от 0 до n.p. Сумирайки броят на различните решения за всяка възможна сума на първата половина ни дава броят на всички решения и така решаваме задачата.

Не трябва да забравяме при реализацията на задачата да използваме и подходящите типове данни. За тази задача е достатъчно използването на 64 битови целочислени числа.

Примерна реализация

#include <iostream>

using namespace std;


typedef long long i64;


const int maxn = 10;
const int maxs = 100;


int n, p, k;
i64 ans;
i64 f[maxn][maxs];


void solve();

int main()
{
	solve();

	return 0;
}

void solve()
{
	int i, j, r;

	void readf();
	void writef();

	readf();

	f[0][0] = 1;
	for (i = 1; i <= n; i++)
		for (j = 0; j <= n * p; j++)
			for (r = 0; r <= min(p, j); r++)
				f[i][j] += f[i-1][j-r];

	for (i = k; i <= n * p; i++)
		ans += f[n][i] * f[n][i-k];

	writef();
}

void readf()
{
	cin >> n >> p >> k;
}

void writef()
{
	cout << ans << '\n';
}
			

Автор: Иван Анев


обратно към брой 26