/* Задача B2. СУМА Напишете програма SUM.EXE, която пресмята броя на различните редици от N неотрицателни цели числа такива, че сумата от квадратите на тези числа да е по-малка от дадена стойност S. Входните данни се въвеждат на един ред от стандартния вход като две цели числа N и S, разделени с един интервал (0 < N < 30, S < 100). Резултатът трябва да бъде изведен на стандартния изход като едно цяло число. ПРИМЕР Вход: 1 4 Изход: 2 Решение на Задача В2 - Сума от Иван Анев Ще решим задачата използвайки метода на динамичното оптимиране. Ще дефинираме функцията F(x,y) за 0 <= x < S и 0 <= y <= N. Където F(x,y) е броят на различните суми от y неотрицателни числа, чиято сума е x. Отговорът на нашата задача е сумата на F(x,N) за всяко x. Сега трябва да опишем метод за изчисляване на функцията F. Ще започнем от базовите случаи. За нашата задача това ще бъдат тези F, за който y е нула, тоест нямаме събираеми. А именно F(0,0) = 1 и F(x,0) = 0 за x < 0. После как изчисляваме останалите стойности. Последователно ще образуваме от редици с дължина j (за 0 <= j < N), редици с дължина j+1. Как става това за конкретно j. За всеки F(x,j) >= 0 и всяко k, такова че x + k2 < S, към стойността на F(x+k*k,j+1) се прибавя стойността на F(x,j). Изчисляването на F(x,y) ще става в ред на нарастване на y. y = 0 е базовият случай. После ще изчислим за y = 1, 2 ... N. Накрая сумираме стойностите на F(x,N) и получаваме отговора на задачата. */ /* NAME: Ivan Anev PROG: sum LANG: C++ */ #include <iostream> #include <cstring> using namespace std; typedef long long lint; const int maxn = 31; const int maxs = 100; class Sum { private: lint f[maxs][maxn]; public: void solve() { int n, s; int i, j, k; lint r; cin >> n >> s; memset(f, 0, sizeof(f)); f[0][0] = 1; for (i = 0; i < n; i++) for (j = 0; j < s; j++) if (f[j][i]) for (k = 0; k * k + j < s; k++) f[j+k*k][i+1] += f[j][i]; r = 0; for (i = 0; i < s; i++) r += f[i][n]; cout << r << '\n'; } }; Sum sum; int main() { sum.solve(); return 0; }