pbinfo 3738 NewYork
Cerința
Doru s-a mutat în New York și își caută o nouă locuință specială în perimetrul străzilor numerotate cu numerele distincte de la 1 la n. Fiind pasionat de matematică, el vrea să se mute pe strada în care cel mai mare divizor comun (cmmdc) al înălțimilor clădirilor este maxim.
În plus, alegerea clădirii nu este una ușoară, el dorind să se mute doar într-o clădire perfectă. Numim o clădire perfectă o clădire care are cea mai mare înălțime număr prim de pe strada pe care se află.
Fiind ocupat cu împachetatul, Doru vă roagă pe voi să găsiți clădirea perfectă.
Date de intrare
Fișierul de intrare nyk.in conține pe prima linie numărul de străzi n pe care Doru își caută noua locuință.
Pe fiecare dintre următoarele n linii (câte una pentru fiecare stradă din cele n, în ordinea crescătoare a numerelor străzilor) se află numărul m, reprezentând numărul de clădiri de pe strada curentă, urmat de m numere ce reprezintă înălțimile clădirilor de pe strada curentă (în ordinea poziționării lor pe stradă, de la stânga la dreapta). Pe fiecare linie numerele sunt separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire nyk.out va conține două linii.
Prima linie va conține două numere naturale separate printr-un spațiu, reprezentând numărul străzii cerute și poziția pe stradă a clădirii în care se va muta Doru.
A doua linie va conține un număr natural reprezentând înălțimea clădirii alese.
Dacă pe strada cu cmmdc-ul maxim nu se găsește nicio clădire cu înălțimea un număr prim, atunci prima linie a fișierului va conține mesajul Nu am gasit casa!
Restricții și precizări
1 ≤ n ≤ 1000
1 ≤ m ≤ 1000
Numerele de pe a doua linie a fișierului de intrare sunt mai mici decât 1 000 000 000
Înălțimile clădirilor sunt numere naturale nenule mai mici ca 2 000 000 000.
Pe fiecare stradă există cel puțin o clădire.
Dacă pe strada cu cmmdc-ul maxim sunt mai multe clădiri perfecte, se va afișa cea mai din dreapta.
Dacă sunt mai multe străzi cu aceeași clădire perfectă, se va afișa cea care are numărul străzii cel mai mare.
Exemplu
nyk.in
5
2 1 2
3 18 6 48
2 5 7
4 3 6 9 12
4 34 17 68 17
nyk.out
5 4
17
Explicație
Valoarea maximă a celui mai mare divizor comun al înălțimilor clădirilor de pe o stradă dintre cele cinci este 17 (cmmdc(1,2)=1, cmmdc(18, 6, 48)=6, cmmdc(5, 7)=1, cmmdc(3, 6, 9, 12)=3, cmmdc(34, 17, 68, 17)=17). Astfel Doru va alege clădirea a 4-a de pe strada cu numărul 5.
Răspunsuri la întrebare
Program C++ :
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("nyk.in");
ofstream g("nyk.out");
int fct_cmmdc(int a, int b){
//Functie care returneaza cel mai mare divizor comun al numerelor a si b (Euclid)
int r;
while(b != 0){
r = a % b;
a = b;
b = r;
}
return a;
}
bool prim(int n){
//Functie care returneaza 1 daca n este prim sau 0 altfel.
if(n<2)return 0;
for(int i=2;i<=n/2;i++)
if(n%i==0)return 0;
return 1;
}
int main(){
int i,j,n,m,cmmdc,curent,maxcmmdc=0,nractualcladire=0,maxprimcladire=0;
int strada=0, cladire=0, inaltimecladire=0;
//Citire strazi
f >> n;
for(i=1;i<=n;i++){
//Initializare maxim cladire
maxprimcladire=0;
//Citire cladiri
f >> m;
for(j=1;j<=m;j++){
f >> curent;
//Daca aceasta e prima cladire de pe strada, atribuie valoarea ei cmmdc. Altfel calculeaza cmmdc
if(j==1) cmmdc=curent;
else cmmdc=fct_cmmdc(curent,cmmdc);
//Determina maximul prim de pe strada respectiva, salveaza inaltimea
if(curent>=maxprimcladire && prim(curent)){
maxprimcladire = curent;
nractualcladire = j;
}
}
//Daca cmmdc actual e mai mare decat maximul inlocuieste maxcmmdc, salveaza numarul strazii si al cladirii; si inaltimea cladirii;
if(cmmdc>=maxcmmdc){
maxcmmdc = cmmdc;
strada=i;
cladire = nractualcladire;
inaltimecladire = maxprimcladire;
}
}
//Afisare rezultat
if(inaltimecladire)g << strada << " " << cladire << endl << inaltimecladire;
else cout << "Nu am gasit casa!";
}
Nota :
Pbinfo da doar 80 de puncte pentru aceasta solutie. Cum site-ul nu ofera suficiente detalii despre testele la care programele sunt supuse nu imi pot da seama exact de problema.