Salut am nevoie de ajutor la niste probleme

[•pekaciu]

Le atasez

[•SpiderMan]

La a doua problema prima data ar fi sa observi ca pentru o diag. suma dintre numitor si numarator este constanta. Astfel, se incepe de la suma 2, suma 3 si tot asa. Se observa ca exista 1 element cu suma 1, 2 cu suma 2, 3 cu suma 3 etc. Astfel, pentru un N fixat, cauti primul x a.i. 1 + 2 + .... + x sa fie strict mai mic decat N. (daca este egal cu N, atunci N poate fi chiar ultimul termen, cum este al doilea exemplu). Avand acest x (putina matematica), inseamna ca esti la cazul in care cauti o fractie de forma a/b, cu a + b = x + 1. Asadar, trebuie sa vezi de unde se incepe, adica de la fractia 1/x, sau de la x/1. Asta ti-o da paritatea lui x, daca x este par, incepi de la 1/x, daca este impar de la x/1. Acum, cu acest x, este simplu. Rezultatul evident o sa fie : notand cu ct = N - x, pentru x par, o sa ai fractia (1 + ct) / (x - ct), iar daca x este impar, o sa ai invers, adica (x - ct) / (1 + ct).
Pentru prima problema, ai posibilitatea in N^2 (care cred ca ajunge) cu un vector, in care la pasul curent iei elementul minim din el nevizitat (folosesti si-un vector boolean de vizitati), si adaugi in vector element * 2, element * 3 si element * 5, pana cand ai N elemente in acel vector, si apoi cu o ultima parcurgere afli elementul maxim, afisandu-l. Poti face si cu un heap in NlogN, dar nu-i cazul.

[•pekaciu]

ceva am inteles dar poti sa ma ajuti cu codul in c++

[•klamathix]

Hai sa nu rezolvam temele acasa chiar asa direct .

[•flaviumanica]

La prima,zic ca ar fi mai simplu sa iei in variabila x toate numerele naturale,incepand de la 1,iar in y pozitia lor in vectorul solutie. Cand y ajunge egal cu n,afisezi x-ul respectiv.
Ca un numar x sa fie pus in vectorul solutie,trebuie ca dupa ce il imparti la 2(cat timp permite divizibilitatea),la 3 si la 5, x-ul sa ramana 1.

[•visanr]

La prima,zic ca ar fi mai simplu sa iei in variabila x toate numerele naturale,incepand de la 1,iar in y pozitia lor in vectorul solutie. Cand y ajunge egal cu n,afisezi x-ul respectiv.
Ca un numar x sa fie pus in vectorul solutie,trebuie ca dupa ce il imparti la 2(cat timp permite divizibilitatea),la 3 si la 5, x-ul sa ramana 1.

Al 900-lea termen e 26244000, nu prea poti face cum zici tu.

[•flaviumanica]

La prima,zic ca ar fi mai simplu sa iei in variabila x toate numerele naturale,incepand de la 1,iar in y pozitia lor in vectorul solutie. Cand y ajunge egal cu n,afisezi x-ul respectiv.
Ca un numar x sa fie pus in vectorul solutie,trebuie ca dupa ce il imparti la 2(cat timp permite divizibilitatea),la 3 si la 5, x-ul sa ramana 1.

Al 900-lea termen e 26244000, nu prea poti face cum zici tu.

Te referi ca se ajunge la numere prea mari? Da,asa e,insa ca rationament e ok. Acum nu stiu,se depuncteaza la concursuri astfel de lucruri?

[•visanr]

La prima,zic ca ar fi mai simplu sa iei in variabila x toate numerele naturale,incepand de la 1,iar in y pozitia lor in vectorul solutie. Cand y ajunge egal cu n,afisezi x-ul respectiv.
Ca un numar x sa fie pus in vectorul solutie,trebuie ca dupa ce il imparti la 2(cat timp permite divizibilitatea),la 3 si la 5, x-ul sa ramana 1.

Al 900-lea termen e 26244000, nu prea poti face cum zici tu.

Te referi ca se ajunge la numere prea mari? Da,asa e,insa ca rationament e ok. Acum nu stiu,se depuncteaza la concursuri astfel de lucruri?

Da, se ajunge la numere prea mari si nu poti itera cu X pana ajungi la al 5000-lea termen. Se depuncteaza, deoarece nu va intra in timp pe teste mai mari. Pe teste cu N mic (vreo 300-400 maxim) merge bine.

[•flaviumanica]

Pentru prima problema, ai posibilitatea in N^2 (care cred ca ajunge) cu un vector, in care la pasul curent iei elementul minim din el nevizitat (folosesti si-un vector boolean de vizitati), si adaugi in vector element * 2, element * 3 si element * 5, pana cand ai N elemente in acel vector, si apoi cu o ultima parcurgere afli elementul maxim, afisandu-l. Poti face si cu un heap in NlogN, dar nu-i cazul.

Dar in cazul asta,pentru n=4 nu afiseaza 5,cand trebuie 4? Adica la inceput pleci cu 1,pui in vectori 2,3,5.Ai ajuns la 4,te-ai oprit. Maximul acum e 5,si totusi...

[•Steve]

E mai greu de implementat solutia N^2 decat NlogN din cauza ca trebuie sa tii un hash/vector de booli de tipul used[ i ][j][k], unde i iti indica puterea la care e ridicat 2, j = puterea la care e ridicat 3, etc. Dupaia trebuie sa mergi cu operatia ta pana la elementul N unde te opresti (O sa ai pana la 3N elemente in vector), si e destul de stupid de bagat imo.
Mai simplu, bagi intr-un heap numarul 1. Iei o variabila k = 1, si o variabila last = 0. Cat timp k < N faci asa:
Iei elementul minim din heap. Il numim "a". Daca a = last atunci il scoti pur si simplu. Altfel, scoti a si bagi la loc in heap 2a, 3a, 5a, incrementezi k-ul si last ia valoarea a. Altfel spus:

Cod:

priority_queue <int> Hp;
int k = 1, last;

void Aflare ()
{
Hp.push (1);
while (k < N)
{
while (Hp.top () == last) Hp.pop ();
int a = Hp.top ();
Hp.pop ();
Hp.push (2*a);
Hp.push (3*a);
Hp.push (5*a);
k++;
last = a;
}
}

Raspunsul e in Hp.top () acum.

[•vlad_D]

si memoria iti ajunge? Sau ajungi sa bagi prea multe numere inutile?

Incearca sa o rezolvi mai eficient. Si gandeste-te ca e o problema de clasa 9-a de la o locala.. in care multi nu prea stiu ce e heap oricum..

[•Steve]

Scuze, nu realizasem ca e a 9a...ce-i drept nu m-as mira ca la o locala sa dea subiecte aiurea.
Mi se pare mult mai simplu

Cod:

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define ll long long
using namespace std;

int N;
priority_queue <ll, vector <ll>, greater <ll> > Hp;
int k = 1;
ll last;

ll Aflare ()
{
Hp.push (1);
while (k < N)
{
while (Hp.top () == last) Hp.pop ();
ll a = Hp.top ();
Hp.pop ();
Hp.push (2*a);
Hp.push (3*a);
Hp.push (5*a);
k++;
last = a;
}
return Hp.top ();
}

int main ()
{
    cin >> N;
    cout << Aflare ();
    return 0;
}

decat o solutie care tine un vector de marime 3N de struct-uri de tipul {numar, exponent la care e ridicat 2, exp la care e ridicat 3, exp la care e ridicat 5} si un indice de tipul used[50][50][50] care iti zice daca ai mai luat numarul ala pana in momentul respectiv. In plus, solutia cu heap tine un element K de maxim 3 ori (exista 3 numere din care se poate ajunge la K, mai precis K/2, K/3, K/5. Nu vei analiza unul din aceste numere decat o singura data, deci e pretty obvious). Dimensiunea heapului e maxim 3N. Daca vrei mai putin de 3N memorie (chiar nu vad sensul) bagi arbore de cautare in loc de heap si e exact la fel, daca bagi stl. Scuze pentru posturi daca le considerati inutile.

[•vlad_D]

"decat o solutie care tine un vector de marime 3N de struct-uri de tipul {numar, exponent la care e ridicat 2, exp la care e ridicat 3, exp la care e ridicat 5} si un indice de tipul used[50][50][50] care iti zice daca ai mai luat numarul ala pana in momentul respectiv. "

Cine a zis ca nu se poate mai usor? Incearca liniar.