Problema Numar
0Presupunem 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; }