Endriu (samsungmaster)

Vezi solutiile trimise	Nume	Endriu
	Cont	samsungmaster
	Rating	445
	Statut	Utilizator normal
	Forum	trimite mesaj privat, vezi activitate

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-12-27 16:50:13.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	euclid2.in, euclid2.out	Sursă	ad-hoc
Autor	Arhiva Educationala	Adăugată de	Filip Cristian Buruiana •filipb
Timp execuţie pe test	0.125 sec	Limită de memorie	4608 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Algoritmul lui Euclid

Cel mai mare divizor comun dintre doua numere naturale a si b este cel mai mare numar natural pozitiv d care divide ambele numere.

Cerinta

Dandu-se T perechi de numere naturale (a, b), sa se calculeze cel mai mare divizor comun al numerelor din fiecare pereche in parte.

Date de intrare

Fisierul de intrare euclid2.in contine pe prima linie numarul T de perechi. Urmatoarele T linii contin cate doua numere naturale a si b.

Date de iesire

In fisierul de iesire euclid2.out se vor scrie T linii. A i-a linie din acest fisier contine cel mai mare divizor comun al numerelor din perechea de pe linia i+1 din fisierul de intrare.

Restrictii

1 ≤ T ≤ 100 000
Pentru fiecare pereche, 2 ≤ a, b ≤ 2 * 10⁹

Exemplu

euclid2.in	euclid2.out
3 12 42 21 7 9 10	6 7 1

Indicatii de rezolvare

O scurta prezentare a acestui subiect gasiti aici.
Cel mai mare divizor comun dintre doua numere a si b se poate calcula iterativ, printr-o simpla parcurgere a tuturor numerelor de la 2 la minim(a, b). Aceasta rezolvare se gaseste aici si obtine 30 de puncte. Pentru a imbunatati timpul de rulare putem folosi algoritmul lui Euclid prin scaderi, ceea ce duce la obtinerea a 60 de puncte, sau prin impartiri, solutie ce obtine punctajul maxim.

Probleme similare

cmmdc de pe infoarena

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

Fişierul intrare/ieşire:	euclid.in, euclid.out	Sursă	Summer Challenge 2007, runda 2
Autor	Igor Naverniouk	Adăugată de	Daniel Pasaila •danielp
Timp execuţie pe test	1.2 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Euclid

Euclid era un om destept care stia ca timpul masinilor de calcul avea sa vina intr-o zi. Stia ca oamenii aveau sa organizeze competitii pe aceste masini, asa ca a vrut sa contribuie cu un puzzle.
Fiind data o matrice de m linii si n coloane de intregi pozitivi, sa se gaseasca un dreptunghi de inaltime cel putin h si lungime cel putin w, astfel incat numerele din dreptunghi sa aiba cel mai mare cmmdc dintre toate dreptunghiurile de acest fel.

Date de intrare

Fisierul de intrare va incepe printr-o linie ce contine numarul de teste, T. Fiecare test va incepe printr-o linie ce contine m, n, h si w. Urmeaza m linii a cate n intregi pozitivi, descriind matricea de mai sus.

Date de iesire

Pentru fiecare fisier de iesire, scrieti cate o linie continand "Case #x: ", dupa care afisati cel mai mare cmmdc (x reprezinta numarul testului).

Restrictii

1 ≤ T ≤ 20
1 ≤ h ≤ m
1 ≤ w ≤ n
1 ≤ m,n ≤ 400
numerele din matrice sunt intre 1 si 10⁹

Exemplu

euclid.in	euclid.out
3 2 2 1 1 1 2 3 4 3 3 3 1 1 2 3 4 5 6 7 8 9 2 2 2 2 1000000000 1000000000 1000000000 1000000000	Case #1: 4 Case #2: 3 Case #3: 1000000000

Explicatie

pentru primul exemplu, este evident ca dreptunghiul cu cmmdc maxim contine doar patratelul de coordonate (1, 1) (coordonatele sunt numerotate de la 0)
pentru al 2-lea exemplu dreptunghiul cu cmmdc maxim este format din ultima coloana a matricii; nu exista alt dreptunghi de dimensiuni mai mari sau egale care sa aiba cmmdc-ul mai mare
in cazul ultimului exemplu putem alege intreaga matrice

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

Fişierul intrare/ieşire:	fact.in, fact.out	Sursă	info-arena 1.0
Autor	Cristian George Strat	Adăugată de
Timp execuţie pe test	0.075 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	1/5

Vezi solutiile trimise | Statistici

Factorial

Se da un numar intreg P. Sa se gaseasca cel mai mic numar natural strict pozitiv N pentru care N! are exact P cifre de 0 la sfarsit.

Se stie ca N! = 1 * 2 * 3 * .... * (N - 1) * N.

Date de intrare

Fisierul fact.in va contine pe prima linie numarul intreg P.

Date de iesire

Pe prima linie a fisierului fact.out se va scrie acel numar N care indeplineste conditiile impuse sau -1 daca nu exista un astfel de N.

Restrictii

0 ≤ P ≤ 10⁸

Exemple

fact.in	fact.out
0	1
2	10
10	45

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Indicii de rezolvare

Arată 2 categorii

Cum se trimit solutii?

Acest utilizator nu si-a personalizat inca pagina de profil. Click aici sa afli cum iti poti personaliza pagina de profil.

infoarena informatica de performanta

Endriu (samsungmaster)

Algoritmul lui Euclid

Cerinta

Date de intrare

Date de iesire

Restrictii

Exemplu

Indicatii de rezolvare

Probleme similare

Euclid

Date de intrare

Date de iesire

Restrictii

Exemplu

Explicatie

Factorial

Date de intrare

Date de iesire

Restrictii

Exemple

Indicii de rezolvare