671 Joc7

[•DITzoneC]

Aici puteţi discuta despre problema Joc7.

[•Dastas]

E corect exemplul 2? Se cere nivelul minim 100 iar el termina jocul cu nivelul 19?

[•Tabara]

E corect exemplul 2? Se cere nivelul minim 100 iar el termina jocul cu nivelul 19?

In caz ca nu mai poate merge pe alta misiune pentru ca are N-ul la un moment dat prea mic, se returneaza valoarea respectiva.
Nu se precizeaza in enunt, dar si eu am dedus asta din exemplul 2.

[•Dastas]

Tocmai, ca inca se precizeaza ca exista intotdeauna solutie, ceea ce m-a dus cu gandul ca exemplul ar fi gresit. Asta era, imi intra in ciclu infinit cand nu aveam solutie.

Si cred ca trebuie n < 2 miliarde, nu 20 de miliarde, pt ca eu am luat 100 folosind int.

[•Tabara]

Asta era, imi intra in ciclu infinit cand nu aveam solutie.

La fel am patit si eu.

[•DITzoneC]

Am corectat precizarea respectiva.

[•jupanu92]

Va rog si eu ceva stiu ca nu aveti voie dar mam chinuit ata la pr asta .. chiar daca e usoara prima oara am obtinut doar 20 de p apoi mam chinuit am luat vreo 50 de ex si am vazut unde greseam si am luat dupaia 80 de p

Vreau si eu niste vreo doua exemple sa vad unde gresesc .

[•savim]

Problema a fost data la onigim 2008. Nu stiu daca testele sunt aceleasi, dar daca te uiti pe ele probabil te-ar putea ajuta. Personal iti recomand sa cauti greseala in codul tau. Pentru a le accesa intra pe http://isj.bc.edu.ro/ si da-i la "cautare combinata": Olimpiada nationala de informatica. Si vezi tu mai departe...

[•jupanu92]

Da ms oricum ptr raspuns dar am observat ca prin multe exemple iei suta deci am mai dat vreo 4 ex si deja am gasit eroarea si am luat 100 ms mult :*

[•gabor_oliviu1991]

trebuie sortate datele de intrare?

[•Mishu91]

Nu

[•gabor_oliviu1991]

si cam ce complexitate sa aiba algoritmul? ca eu am o idee de O(n²)

[•cos_min]

Este greu sa imi dau seama exact ce complexitate am. Cred ca in cel mai rau caz ar fi O(n^2), dar acest lucru nu cred ca are loc. Deci teoretic ar fi O(n^2), dar practic cred ca tinde undeva la O(n).

[•Irnuk]

trebuie sortate datele de intrare?

daca vrei le poti  sorta... eu am folosit un quick sort si am luat 100 pct 

[•f.v.anton]

Ce au asa de special testele 3 6 si 8 ? Ca vad ca iau doar 70 si iau WA pe astea 3 

Never mind....era doar un test pus unde nu trebuie  , acum iau 100 

[•rusu_radu]

Ce au asa de special testele 0 si 1:-?

[•otniel]

ce este gresit iau wa 3-10?

Cod:

#include<iostream>
using namespace std;
#include<stdio.h>
#include<algorithm>
FILE *f,*g;
long long n,m,maximpoz,maxim1,nr,aux,x;
int k,i;
struct puncte
{
    long long x,y,maxim;
};
puncte a[5001];
long long cmp(puncte a,puncte b)
{
    return a.x<b.x;
}
int main()
{
    f=fopen("joc7.in","r");
    g=fopen("joc7.out","w");
    fscanf(f,"%lld%d%lld\n",&n,&k,&m);
    for(i=0;i<k;i++)
        {fscanf(f,"%lld%lld\n",&a[i].x,&a[i].y);
        a[i].maxim=a[i].y-a[i].x;
        }
    sort(a,a+k,cmp);
    for(i=0;i<k;i++)
        if(a[i].x<=n)
        {
            if(a[i].maxim>maxim1)
                {maxim1=a[i].maxim;
             maximpoz=i;
             aux=a[i].y;
             x=1;}
        }
        else
        {maxim1=0;i--;
           x=0;
           n=a[maximpoz].y;
            nr++;
            if(n>=m)
                break;
                    if(n<a[i+1].x)
                    break;
        }
        if(x==1)
            nr++;
fprintf(g,"%lld %lld",aux,nr);

}

Editat de admin: Foloseste tagul "code" atunci cand postezi surse.