Dijagonale

Za administratora,

Da li bih mogao da dobijem neki test primer za zadatak dijagonale sa YOUI takmicenja.

Za sve test primere sto sam napravio radi, ali mi stalno daje pogresna resenja kad posaljem.

P.S.
Tekst zadatka nije potpun pise:

Ulaz: Ulazni podaci se citaju sa tastature. U prvom redu se ukucaju celi brojevi n i m (3<10000, 0

trebalo bi popuniti zagradu (verovatno je 3<n<10000, 0<m<9997)

Isto ja sam se mucio sa ovim zadatkom, pa ako moze prati i meni neki test, da
vidim o cemu je problem.

Ja resio i bez test primera od strana admina.

a evo ti 2 test primera:
primer1:
12 7
1 3
3 5
5 7
7 9
1 5
1 11
9 11

resenje 5

primer2:
12 7
1 3
3 5
5 7
7 9
1 7
1 11
9 11

resenje 4

@ Dmitar
Objasni mi malo tvoju ideju za resavanje jer nisam bas nesto mnogo razumeo.
I ja sam imao ideju sa pokazivacima, ali sam odustao od nje jer sam imao prekoracen memorijski limit, ali ideja nije ista kao tvoja.
Moja ideja je bila sledeca:

1 Od svih temena napravim mnogougao,

2 pri ucitavanju dijagonala (p, k) odredjujem koji mnogougao ta dijagonala deli na dva dela

3 podelim taj mnogougao na sledeci nacin:
3.1 nov.teme := p;
nov.next:=mnog.next;
repeat
nov:=nov.next;
until nov.teme=k;
new(mnog.next);
mnog:=mnog.next;
mnog.teme := k;
mnog.next:=nov.next;
nov.next:=nil;
3.2 odredim velicine ta dva nova mnogougla i ako je neka velicina 3 taj mnogougao izbacim da ga vise ne gleda.

4 nakon ucitavanja svih dijagonala odredim koji je mnogougao najveci i stampam njegovu velicinu.

Nisam siguran sta mi nije proslo kod ovoga, ali znam da nije.


Resenje koje mi radi (a i TIJANAKG ima veom slicno resenje) koristi samo 3(2) niza duzine n.

Pa ja sam radio kao graf, ali sve sam ispomesao...

Moje resenje je sledece:
Sortiram dijagonale tako da je razlik izmedju temena rastuca.
Krenem od prve dijagonale i idem ka poslednjoj (sortirane)
1) nov=d[i][2]-d[i][1];
if nov>max then max:=nov;
2) izbacim sva temena od d[i][1]+1 do d[i][2] ukljucujuci i njih pa u dijagonalama reimenujem temena koja su ostala (ukoliko su veca od d[i][1]

probaj

ja ne razumem, sta mislis sa to izbacujes temena od d[i][1]+1 do d[i][2], kako gi izbacujes? kako preimenujes ostali temena (ustvari koji su ti ostali temena)?

Jel mozes da pojasnis bolje to pod 2?

2) izbacim sva temena od d[i][1]+1 do d[i][2]
npr d[i][1] = 4 i d[i][2] =7
dijagonalu 4-7 proglasavam za stranicu mnogougla, a radi lakseg gledanja koja temena su u mnogouglu uradim sledece:
teme 8 proglasim za teme 5
teme 9 proglasim za teme 6
teme 10 proglasim za teme 7
teme 11 proglasim za teme 8 ...
teme N proglasim za teme N-3

to isto to uradim i u dijagonalama.

Proslo je za najvise 0.04 :)

Nije jasan input zadatka. Kolko sam shvatio, drugi broj u prvom redu (m) je kolko ima linija ispod.
E sad sta znace ta 2 broja?

Parovi koji slede (a,b) govore da su cvorovi a i b povezani

Ok thx.