Problema Numar

Presupunem ca avem n numere prime notate a1, a2, ..., an sortate crescator. Formam un sir strict crescator b ale carui elemente sunt toti multipli acestor n numere prime astfel incat, multipli comuni apar o singura data. Presupunem ca numerotarea pozitiilor elementelor din sirul b incepe tot cu 1.

• Cerinta

Scrieti un program care citeste din fisierul de intrare valoarea lui n si apoi cele n elemente ale sirului a, determina elementul de pe pozitia m din sirul b si afiseaza in fisierul de iesire valoarea acestuia.

• Date de intrare

Fisierul de intrare numar.in contine
– pe prima linie doua numere naturale separate printr-un spatiu care reprezinta primul valoarea lui n si al doilea valoarea lui m;
– pe a doua linie n numere naturale prime separate prin cate un spatiu care reprezinta valorile elementelor sirului a. Aceste valori sunt dispuse in ordine strict crescatoare iar ultima dintre ele este mai mica decat un milion.

• Date de iesire

Fisierul de iesire numar.out va contine pe prima linie o singura valoare care reprezinta termenul de pe pozitia m din sirul b.

• Restrictii

Pentru 30% din teste n≤20, m≤1000, a1≤50
Pentru celelalte 70% din teste 21≤n≤100, 1001≤m≤15000, 51≤a1≤1000
an<1000000

• Solutie

Rezolvarea mea se bazeaza pe o varianta modificata a unui ciur, de tipul Erathostenes. Nu este insa cea mai optima, o abordare backtracking aducand punctajul maxim.

#include <stdio.h> 

#define MAX 15000 

int a[MAX], b[MAX]; 
int n, m, poz = 0, i, j, k = 0, p; 

int main() 
{ 
 FILE *f = fopen ("numar.in","r"); 
 FILE *g = fopen ("numar.out","w"); 
 fscanf (f,"%d %d", &n, &m); 
 for (i=0; i<n; ++i) 
 fscanf (f,"%d", &a[i]); 
 fclose(f); 

 i = a[0]; 
 while (poz < m) 
 { 
     for (j=0; j<n; ++j) 
         if (i % a[j] == 0)  
         { 
             int ok = 1; 
             for (p=0; p<k; ++p) 
                  if (b[p] == i) ok = 0; 
             if (ok) 
             { 
                 b[k] = i; 
                 k ++; 
                 poz ++; 
             } 
          } 
      i ++; 
 } 

 fprintf (g,"%d\n", b[poz-1]); 
 fclose(g); 
 return 0; 
}