Cod sursa(job #2577922)

Utilizator ionut.birisBiris Ionut ionut.biris Data 10 martie 2020 09:51:19
Problema Floyd-Warshall/Roy-Floyd Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
using namespace std;

const int NMAX = 1005;

ifstream f("A.in");
ofstream g("A.out");

bool NrPrime[NMAX];

int A[NMAX];
int N,M,Grad;
int Solutie;
int St[NMAX];

void ConstruireSirNrPrime()
{
    NrPrime[1] = 1;

    for(int i = 3; i <= 1005; i++)
        if(NrPrime[i] == 0)
            for(int  j = i * i; j<= 1005; j+=i)
                NrPrime[j] = 1;

    for(int i = 4; i<= 1005; i+=2)
        NrPrime[i] = 1;

}

void ConstruireSir(int n,int m)
{
    for(int i = n; i<=m; i++)
        A[i] = i;
}

int ok(int k)
{
    int sum;

    for(int j = 1; j <= k; j++)
    {
        sum = 0;
        for(int i = j; i <= Grad; i++)
            sum+=St[i];
        if(NrPrime[sum] == 0)
            return 0;
    }
    return 1;

}

void Afis(){
    for(int i = 1;i <= M-N+1;i++)
        cout << St[i] << " ";
}

void Backt(int k)
{
    for(int i = 1; i <= M - N + 1; i++)
    {
        St[k] = i;
        if(ok(k))
            if(k == M - N + 1)
            {
                Afis();
                break;
            }
            else Backt(k+1);
    }
}

int main()
{
    ConstruireSirNrPrime();

    int nr;

    while(f >> nr){
        if(nr==0)
            break;
        else{
            N = nr;
            f >> M >> Grad;
            ConstruireSir(N,M);
        }

        Backt(1);
    }

    return 0;
}