ALGORITMI - PRIMERI
1. Fibonačijevi podnizovi
Dat je niz prirodnih brojeva dužine N manjih od M.
Naći maksimalnu dužinu podniza fibonačijevog niza tako da on može biti formiran od zadatih brojeva i ispisati indekse elemenata zadatog niza koji formiraju ovaj fibonacijev podniz.
Ulaz
U prvom redu standardnog ulaza nalaze se prirodni brojevi N i M koji predstavljaju broj elemenata i maksimalnu moguću vrednost elemenata zadatog niza.
U drugom redu nalazi se N prirodnih brojeva koji predstavljaju zadati niz.
Izlaz
Na standardni izlaz u prvom redu ispisati broj elemenata najdužeg fibonačijevog podniza koji se može formirati i ispisati indekse elemenata zadatog niza koji formiraju ovaj fibonacijev podniz. Ukoliko postoje dva ista broja sa razlicitim indeksom u nizu uzeti manji indeks. Indekse ispisati u redu takvom da elementi niza, koje oni indeksiraju, formiraju fibonacijev podniz.
Ograničenja
M <= 10 000;
N <= 10 000 000;
Primer
Ulaz
12
20
Izlaz
2 4 6 8 10 11 13 4 3 2 1 1
4
10 11 0
Naći maksimalnu dužinu podniza fibonačijevog niza tako da on može biti formiran od zadatih brojeva i ispisati indekse elemenata zadatog niza koji formiraju ovaj fibonacijev podniz.
Ulaz
U prvom redu standardnog ulaza nalaze se prirodni brojevi N i M koji predstavljaju broj elemenata i maksimalnu moguću vrednost elemenata zadatog niza.
U drugom redu nalazi se N prirodnih brojeva koji predstavljaju zadati niz.
Izlaz
Na standardni izlaz u prvom redu ispisati broj elemenata najdužeg fibonačijevog podniza koji se može formirati i ispisati indekse elemenata zadatog niza koji formiraju ovaj fibonacijev podniz. Ukoliko postoje dva ista broja sa razlicitim indeksom u nizu uzeti manji indeks. Indekse ispisati u redu takvom da elementi niza, koje oni indeksiraju, formiraju fibonacijev podniz.
Ograničenja
M <= 10 000;
N <= 10 000 000;
Primer
Ulaz
12
20
Izlaz
2 4 6 8 10 11 13 4 3 2 1 1
4
10 11 0
2. Faktorizacija
Dato je n brojeva. Potrebno je faktorisati svaki broj, tj. napisati ga kao proizvod prostih činilaca. Svaki broj faktorisati u formatu p1^a1 * p2^a2 * ... * pk^ak , gde su p1 ≤ p2 ≤ ... ≤ pk svi prosti činioci datog broja (u rastućem redosledu), a a1, a2, ..., ak - njihovi odgovarajući izložioci. Izmedju brojeva i simbola '*' i '^' ne sme biti razmaka. Takođe, ukoliko je izložilac nekog broja jednak 1, treba ga svejedno ispisati.
Ulaz
U prvom redu standradnog ulaza nalazi se prirodan broj n . U sledećih n redova se nalazi po jedan ceo broj bi koga treba faktorisati.
Izlaz
Na standardni izlaz za svaki broj ispisati, u posebnom redu, njegovu faktorizaciju u gore opisanom formatu, u redosledu datim na ulazu.
Ograničenja
1 ≤ n ≤ 200.000,
2 ≤ bi ≤ 200.000.
U prvom redu standradnog ulaza nalazi se prirodan broj n . U sledećih n redova se nalazi po jedan ceo broj bi koga treba faktorisati.
Izlaz
Na standardni izlaz za svaki broj ispisati, u posebnom redu, njegovu faktorizaciju u gore opisanom formatu, u redosledu datim na ulazu.
Ograničenja
1 ≤ n ≤ 200.000,
2 ≤ bi ≤ 200.000.
3. Parovi prostih brojeva
Dat je prirodan broj N. Odrediti koliko ima parova prostih brojeva p i q, tako da je p ≤ q i da je p+q takođe prost broj koji je manji ili jednak od N.
Ulaz
U prvom i jedinom redu standardnog ulaza nalazi se prirodan broj N.
Izlaz
U prvom i jedinom redu standardnog izlaza ispisati traženi broj parova prostih brojeva.
Ograničenja
1 ≤ N ≤ 1.000.000
U prvom i jedinom redu standardnog ulaza nalazi se prirodan broj N.
Izlaz
U prvom i jedinom redu standardnog izlaza ispisati traženi broj parova prostih brojeva.
Ograničenja
1 ≤ N ≤ 1.000.000
Primer
Ulaz
6
Izlaz
1
Objašnjenje primera
Postoji samo jedan par koji zadovoljava uslove a to je (2, 3). Zaista, 2 i 3 su prosti brojevi i 2+3 je prost broj koji je manji ili jednak od 6.
Ulaz
6
Izlaz
1
Objašnjenje primera
Postoji samo jedan par koji zadovoljava uslove a to je (2, 3). Zaista, 2 i 3 su prosti brojevi i 2+3 je prost broj koji je manji ili jednak od 6.
4. Faktorizacija 2
Za brojeve p i q kažemo da su k-prosto udaljeni ukoliko su oni prosti i između njih postoji tačno k prostih brojeva. Vama su dati brojevi N i k. Poznato je da je broj N ili prost ili se može zapisati u obliku proizvoda p1·p2·p3·...·pm, gde za svako 1 ≤ i ≤ m - 1 važi pi < p_{i+1} i pi i p_{i+1} su k-prosto udaljeni brojevi. Nažalost, mi ne znamo broj m niti brojeve pi - vaš zadatak je da faktorisete broj N, tj. da ga napišete u obliku proizvoda prostih brojeva.
Ulaz
U jednom test primeru je potrebno faktorisati više brojeva N.
U prvom redu standardnog ulaza se nalazi prirodan broj T - broj parova (N, k) iz opisa problema. U svakom od narednih T redova se nalaze, redom, brojevi N i k, razdvojeni razmakom.
Izlaz
Na standarni izlaz je potrebno ispisati T redova pri čemu je u i-tom redu potrebno ispisati faktorizaciju i-tog broja N sa ulaza. Činioce broja N ispisati u rastućem poretku i između svaka dva činioca ispisati znak '*' (zvezdica) bez razmaka i navodnika (videti dati primer).
Ograničenja
1 ≤ T ≤ 5.000
2 ≤ N ≤ 1.000.000.000.000
0 ≤ k ≤ 100
U jednom test primeru je potrebno faktorisati više brojeva N.
U prvom redu standardnog ulaza se nalazi prirodan broj T - broj parova (N, k) iz opisa problema. U svakom od narednih T redova se nalaze, redom, brojevi N i k, razdvojeni razmakom.
Izlaz
Na standarni izlaz je potrebno ispisati T redova pri čemu je u i-tom redu potrebno ispisati faktorizaciju i-tog broja N sa ulaza. Činioce broja N ispisati u rastućem poretku i između svaka dva činioca ispisati znak '*' (zvezdica) bez razmaka i navodnika (videti dati primer).
Ograničenja
1 ≤ T ≤ 5.000
2 ≤ N ≤ 1.000.000.000.000
0 ≤ k ≤ 100
Primer
Ulaz4
238 2
11 0
2431 0
10 1
Izlaz
2*7*17
11
11*13*17
2*5
Objašnjenje primera
Npr. u prvom paru (N = 238, k = 2), brojevi 2 i 7 su k-prosto udaljeni jer su oni prosti i između njih se nalaze tačno dva prosta broja: 3 i 5. Slično i za brojeve 7 i 17. Faktorizacija broja N pod navedenim uslovima je, naravno, jedinstvena.
Ulaz4
238 2
11 0
2431 0
10 1
Izlaz
2*7*17
11
11*13*17
2*5
Objašnjenje primera
Npr. u prvom paru (N = 238, k = 2), brojevi 2 i 7 su k-prosto udaljeni jer su oni prosti i između njih se nalaze tačno dva prosta broja: 3 i 5. Slično i za brojeve 7 i 17. Faktorizacija broja N pod navedenim uslovima je, naravno, jedinstvena.
5. NZD i NZS
Učitati dva broja i odrediti njihov NZD i NZS
6. Najveći NZD
Dat je niz prirodnih brojeva a od n elemenata. U jednom potezu dozvoljeno je odabrati proizvoljna dva susedna broja u nizu i zameniti ih njihovim zbirom. Na primer, ukoliko smo odabrali brojeve ai i ai + 1, niz (a1, a2, ..., ai, ai + 1, ... an) postaje (a1, a2, ..., ai + ai + 1, ... an). Ovo zatim možemo ponavljati na novodobijenim nizovima (primetimo da se broj elemenata niza svaki put smanjuje za 1).
Primeniti određeni broj poteza nad početnim nizom, tako da na kraju dobijemo tačno k brojeva čiji je najveći zajednički delilac najveći moguć.
Primeniti određeni broj poteza nad početnim nizom, tako da na kraju dobijemo tačno k brojeva čiji je najveći zajednički delilac najveći moguć.
Ulaz
U prvom redu standardnog ulaza nalaze se 2 prirodna broja n i k koji predstavljaju, redom, broj elemenata u početnom nizu i broj elemenata koji treba ostati na kraju. Sledeći red sadrži n prirodnih brojeva ai (razdvojenih razmakom) koji predstavljaju početni niz.
Izlaz
U prvom redu standardnog ispisati maksimalni moguć najveći zajednički delilac preostalih brojeva. U drugom redu ispisati kprirodnih brojeva razdvojenih razmakom - izgled niza nakon svih poteza, čiji je najveći zajednički delilac maksimalan. Ukoliko ima više rešenja, štampati bilo koje.
Ograničenja
1 ≤ k < n ≤ 100.000
1 ≤ ai ≤ 1.000.000
Suma svih elemenata niza a nije veća od 1.000.000.
U prvom redu standardnog ulaza nalaze se 2 prirodna broja n i k koji predstavljaju, redom, broj elemenata u početnom nizu i broj elemenata koji treba ostati na kraju. Sledeći red sadrži n prirodnih brojeva ai (razdvojenih razmakom) koji predstavljaju početni niz.
Izlaz
U prvom redu standardnog ispisati maksimalni moguć najveći zajednički delilac preostalih brojeva. U drugom redu ispisati kprirodnih brojeva razdvojenih razmakom - izgled niza nakon svih poteza, čiji je najveći zajednički delilac maksimalan. Ukoliko ima više rešenja, štampati bilo koje.
Ograničenja
1 ≤ k < n ≤ 100.000
1 ≤ ai ≤ 1.000.000
Suma svih elemenata niza a nije veća od 1.000.000.
Primer
Ulaz
6 3
12 7 3 2 15 15
Izlaz
6
12 12 30
Objašnjenje primera
Ukoliko izvršimo poteze (12, 7, 3, 2, 15, 15) → (12, 10, 2, 15, 15) → (12, 10, 2, 30) → (12, 12, 30) dobijamo brojeve 12, 12 i 30 čiji je najveći zajednički delilac jednak 6. Nije moguće dobiti 3 broja sa većim najvećim zajedničkim deliocem.
Ulaz
6 3
12 7 3 2 15 15
Izlaz
6
12 12 30
Objašnjenje primera
Ukoliko izvršimo poteze (12, 7, 3, 2, 15, 15) → (12, 10, 2, 15, 15) → (12, 10, 2, 30) → (12, 12, 30) dobijamo brojeve 12, 12 i 30 čiji je najveći zajednički delilac jednak 6. Nije moguće dobiti 3 broja sa većim najvećim zajedničkim deliocem.
7. NZD dva proizvoda
Dato je n prirodnih brojeva A1, A2, ..., An i m prirodnih brojeva B1, B2, ..., Bm. Potreno je izračunati NZD( A1 · A2 ··· An, B1 · B2 ··· Bm). Međutim, kako ovaj broj može biti jako veliki, izračunajte samo njegov ostatak pri deljenju sa 1.000.000.000.
Ulaz
U prvom redu standardnog ulaza nalazi se jedan prirodan broj n. U drugom redu se nalaze n prirodnih brojeva - A1, A2, ..., An, razdvojeni razmakom. U trećem redu se nalazi prirodan broj m. U četvrtom redu se nalaze m prirodnih brojeva - B1, B2, ..., Bm, razdvojeni razmakom.
Izlaz
U prvi i jedini red standardnog izlaza ispisati ostatak pri deljenju traženog NZD-a brojem 1.000.000.000.
Ograničenja
1 ≤ n, m ≤ 1.000
1 ≤ Ai, Bi < 1.000.000.000
Primer
Ulaz3
358572 83391967 82
3
50229961 1091444 8863
Izlaz
12028
Objašnjenje primera
Važi NZD(358572 · 83391967 · 82, 50229961 · 1091444 · 8863) = NZD(2451966000072168, 485897929014301292) = 408661000012028. Kako je 408661000012028 MOD 1.000.000.000 = 12028, taj broj je rešenje.
U prvom redu standardnog ulaza nalazi se jedan prirodan broj n. U drugom redu se nalaze n prirodnih brojeva - A1, A2, ..., An, razdvojeni razmakom. U trećem redu se nalazi prirodan broj m. U četvrtom redu se nalaze m prirodnih brojeva - B1, B2, ..., Bm, razdvojeni razmakom.
Izlaz
U prvi i jedini red standardnog izlaza ispisati ostatak pri deljenju traženog NZD-a brojem 1.000.000.000.
Ograničenja
1 ≤ n, m ≤ 1.000
1 ≤ Ai, Bi < 1.000.000.000
Primer
Ulaz3
358572 83391967 82
3
50229961 1091444 8863
Izlaz
12028
Objašnjenje primera
Važi NZD(358572 · 83391967 · 82, 50229961 · 1091444 · 8863) = NZD(2451966000072168, 485897929014301292) = 408661000012028. Kako je 408661000012028 MOD 1.000.000.000 = 12028, taj broj je rešenje.
8. ARITMETIČKI TROUGAO
Napisati program koji izračunava zbir brojeva predstavljenih aritmetičkim trouglom
1
2 3 4
5 6 7 8 9
10 11 12 13 14 15 16
2 3 4
5 6 7 8 9
10 11 12 13 14 15 16