Задачка - крепкий орешек про линейку - C++ - Ответ 3680208

#include <ctime>
#include <vector>
#include <cstdlib>
#include <iostream>
using namespace std;
 
//Ôóíêöèÿ âîçâðàùàåò îñòàòîê îò ðàçíîñòè Ì è ñóììû îòåðêçîâ
//íàëè÷èå ýòîé ôóíêöòò ïîçâîëèò ïðîèçâåñòè ââîä ðàçíûõ îòðåçêîâ
//ñóììà êîòîðûõ äàñò M
int calcRestLength(int M, vector <int> parts, int restNum);
 
int main()
{
    int i, j;//Ñ÷¸ò÷èêè
    int part;//Äëèííà îòäåëüíîé ÷àñòè
    int count = 0;//Ñ÷¸ò÷èê ïóåé
    int length;//äëèííà ñóììû îòðåçêîâ
    int N = 0;//Áóäåò ñîäåðæàòü â ñåáå ÷èñëî âàðèàíòîâ êîòîðûìè ìîæíî äîáðàòüñÿ äî Ì
    srand(time(0));//óñòàíîâèëè íà÷ çíà÷åíèå â ãåíåðàòîðå ñëó÷ ÷èñåë
    //Èìåòèðóåì ââîä ïîëüçîâàòåëÿ
    int S = 5; //ìîæíî áûëî áû ðåàëèçîâàòü êàê S = 1 + rand()%5
    int M = 30;//30 ïîóñëîâèþ íó è áîã ñ íèì, õîòÿ ìîæíî äëèíó ëèíåéêè è ðàíäîìíî ñäåëàòü
    vector <int> parts;//Âåêòîð ñ äëèíàìè îòðåçêîâ
    for(i = 0; i < S; i++)
    {
        //Çàïîëíÿåì âåêòîð ÷àñòÿìè áîëüøå íóëèÿ è <= M
        part = calcRestLength(M, parts, S - (i + 1));
        cout<<"Length of "<<i + 1<<" part : "<<part<<endl;
        parts.push_back(part);
    }
    //Òàêñ à òåïåðü ïîåõàëè èñêàòü ñïîñîáû äîñòèæåíèÿ êîíöà ëèíåéêè
    cout<<"Roots searching start..."<<endl;
    for(i = 0; i < S; i++)
    {
        cout<<"Current Root : "<<parts[i];
        length = parts[i];
        for(j = 0; j < S && length < M; j++)
        {
            if(i != j)
            {
                length += parts[j];
                cout<<" - "<<parts[j];
            }
        }
        cout<<"\nM acceded Root lenth : "<<length<<endl;
        if(M != length)
        {
            cout<<"Root length = "<<length<<endl;
            cout<<"M != length - root not acepted"<<endl;
        }
        else
        {
            cout<<"M == length - root acepted"<<endl;
            count++;
        }
    }
    cout<<"Roots searching end"<<endl;
    cout<<"Total number of roots : "<<count<<endl;
    cin.get();//Ñòîï òî÷êà
    return 0;
}
 
int calcRestLength(int M, vector <int> parts, int restNum)
{
    int i;
    int length = 0;
    int count  = 0;
    for(i = 0; i < (int)parts.size(); i++)
        length += parts[i];
    for(i = 0; i < restNum; i++)
        count += (i + 1);
    return 1 + rand()%(M - length - count + 1);
}