Uždavinys „Slidės“

Turit kokių idėjų kaip išspręsti šį uždavinį? Jei taip, tai būčiau dėkingas, jei trumpai nupasakotomėt algoritmą, o geriausia būtų jei dar funkciją sprendimui parašytumėt. Pats sprendžiu C++ kalba, bet suprasiu, jei parašysit ir Pascal ;) Iš anksto dėkoju.

Uždavinio sąlyga čia.

Man meta "Jums čia draudžiama."

Man meta "Jums čia draudžiama."

Pataisyta

Issirikiuoji dydziu masyva ir tada priskiri kas du kiekvienam, t.y. 1 ir 2 pirmam, 2 ir 3 antram ir t.t.. Kazka tik sugalvot su numeriais, neblogai manau butu numeriu masyva gretimais dydziu masyvo rikiuotis.

Issirikiuoji dydziu masyva ir tada priskiri kas du kiekvienam, t.y. 1 ir 2 pirmam, 2 ir 3 antram ir t.t.. Kazka tik sugalvot su numeriais, neblogai manau butu numeriu masyva gretimais dydziu masyvo rikiuotis.

Is esmes taip, bet dar yra atveju kai slidziu/2 daugiau negu zmoniu, tad kazkurias reikia atmest. :D bet siaip atrodo nesunkus, kai sugalvoji algoritma

Is esmes taip, bet dar yra atveju kai slidziu/2 daugiau negu zmoniu, tad kazkurias reikia atmest. :D bet siaip atrodo nesunkus, kai sugalvoji algoritma

Nematau jokios problemos, atmesta bus tas, ko neisdalinsi, pvz turim 5 slides ir 2 vaikus, 1 ir 2 pirmam, 3 ir 4 antram, o penkta lieka. Dalint gi reikia ne viska ka turi, o tiek poru, kiek yra vaiku :)

EDIT: visgi pergalvojau, kad negeras mano pateiktas sprendimas bus. Sakykim duomenys bus 500 600 1000 2000 2001 ir gausim snipsta :)

Padariau Perl

slides.pl

http://www.nerij.us/drive

Issirikiuoji dydziu masyva ir tada priskiri kas du kiekvienam, t.y. 1 ir 2 pirmam, 2 ir 3 antram ir t.t.. Kazka tik sugalvot su numeriais, neblogai manau butu numeriu masyva gretimais dydziu masyvo rikiuotis.

Ne visai tiesa... Tarkime, kad išrykiuotas masyvas atrodo taip:

5

6

10

15

16

17

19

36

Tikrai gausi ne geriausius rezultatus, nes imdamas iš eilės suporuosi 10 su 15, kai tuo tarpu 15 yra išskirtis, kurią reikia atmesti. Tačiau pats sortinimas gera idėja, kadangi konkretus skaičius atsiduria tarp dviejų jam panašiausiųjų. Tada galima formuoti naują masyvą, kuriame nurodoma skaičių pora ir skirtumas tarp jos narių. 6-5=1 ([6][5][1]), 10-6=4 ([10][6][4]), 15-10=5, 16-15=1 ir taip toliau. Tada naują masyvą susortinti pagal mažiausią skirtumą ir paimti tiek masyvo narių, kiek yra vaikų, ir įrašyti duomenis į failą.

Čia šiaip idėja, aš nei programeris, nei matematikas :), buitiškai mąstau šiuo atveju.

3 8

5

6

10

15

16

17

19

36

manoji

6

5 6

1 2

4 7

manoji

6

5 6

1 2

4 7

Pagal tave skirtumų suma tokiai sekai bus |5-6| + |1-2| + |4-7| = 4; bet mažiausia įmanoma skirtumų suma yra |6-7| + |4-5| + |1-2| = 3. Jei aš teisingai supratau, kad tu pateiki tris poras, kurias reiktų paskirstyti trims vaikams...

Pagal tave skirtumų suma tokiai sekai bus |5-6| + |1-2| + |4-7| = 4; bet mažiausia įmanoma skirtumų suma yra |6-7| + |4-5| + |1-2| = 3. Jei aš teisingai supratau, kad tu pateiki tris poras, kurias reiktų paskirstyti trims vaikams...

Isvedami ne ilgiai o numeriai

|nr(5)-nr(6)|+|nr(1)- nr(2)|+|nr(4)- nr(7)|=|16-17|+|5-6|+|15-19|=6

|nr(6)-nr(7)| + |nr(4)-nr(5)| + |nr(1)-nr(2)| = |17-16| + |15-10| + |6-5| = 7

madafakas stipriai baravykauji, masai tai ilgius tai numerius

Pagal tave skirtumų suma tokiai sekai bus |5-6| + |1-2| + |4-7| = 4; bet mažiausia įmanoma skirtumų suma yra |6-7| + |4-5| + |1-2| = 3. Jei aš teisingai supratau, kad tu pateiki tris poras, kurias reiktų paskirstyti trims vaikams...

Taip taciau mano programa klaidinga

2 6

850

950

1001

1002

1050

1150

manoji paskaiciuoja s=101

o yra variantas ir s=99

Isvedami ne ilgiai o numeriai

|nr(5)-nr(6)|+|nr(1)- nr(2)|+|nr(4)- nr(7)|=|16-17|+|5-6|+|15-19|=6

|nr(6)-nr(7)| + |nr(4)-nr(5)| + |nr(1)-nr(2)| = |17-16| + |15-10| + |6-5| = 7

 

madafakas stipriai baravykauji, masai tai ilgius tai numerius

Jei nori būti suprastas teisingai, reikia kalbėti teisingai. Jei aš pateikiu ilgius ir kalbu apie ilgius, tai tavo komentaras su numestais skaičiais ir yra interpretuojamas kaip iligai, o ne kaip numeriai. Nesugebėjimas išsireikšti tinkamai nėra pretekstas kitus kaltinti nesupratingumu, taip kad nesistebėk grybus sodindamas, kad kažkas juos vėliau renka.

P.S. Tikrai neblogas uždavinukas kaip mokiniams ir dar su Pascal (spėju)...

Ne visai tiesa... Tarkime, kad išrykiuotas masyvas atrodo taip:

 

5

6

10

15

16

17

19

36

 

Tikrai gausi ne geriausius rezultatus, nes imdamas iš eilės suporuosi 10 su 15, kai tuo tarpu 15 yra išskirtis, kurią reikia atmesti. Tačiau pats sortinimas gera idėja, kadangi konkretus skaičius atsiduria tarp dviejų jam panašiausiųjų. Tada galima formuoti naują masyvą, kuriame nurodoma skaičių pora ir skirtumas tarp jos narių. 6-5=1 ([6][5][1]), 10-6=4 ([10][6][4]), 15-10=5, 16-15=1 ir taip toliau. Tada naują masyvą susortinti pagal mažiausią skirtumą ir paimti tiek masyvo narių, kiek yra vaikų, ir įrašyti duomenis į failą.

 

Čia šiaip idėja, aš nei programeris, nei matematikas :), buitiškai mąstau šiuo atveju.

Taip, paeditinau greitai ta savo sprendimo buda, kad negeras ir jau nakti miego norejau tai patingejau aprasyt tai, kad reikia ne is eiles visus priskirt, bet tikrint is abieju pusiu ir ziuret, kuris arciau :)

Taip, paeditinau greitai ta savo sprendimo buda, kad negeras ir jau nakti miego norejau tai patingejau aprasyt tai, kad reikia ne is eiles visus priskirt, bet tikrint is abieju pusiu ir ziuret, kuris arciau :)

patikslink zodius

>tikrint is abieju pusiu

patikslink zodius

>tikrint is abieju pusiu

Sakykim yra penkios slides, issirikiuojam ir nepriskiriam kaip is pradziu sakiau, kad 1 ir 2 vienam, toliau dvi kitam, o reikia paziuret ar skirtumas tarp 1 ir 2 mazesnis negu skirtumas tarp 2 ir 3, taip gaunasi, kad paiimi antra slide ir patikrini is abieju pusiu skaicius, t.y. du artimiausius jam.

Sakykim yra penkios slides, issirikiuojam ir nepriskiriam kaip is pradziu sakiau, kad 1 ir 2 vienam, toliau dvi kitam, o reikia paziuret ar skirtumas tarp 1 ir 2 mazesnis negu skirtumas tarp 2 ir 3, taip gaunasi, kad paiimi antra slide ir patikrini is abieju pusiu skaicius, t.y. du artimiausius jam.

Taip ir padariau, taciau spendimas blogas, bendra minimali suma blogai pasiskaiciuoja. del benros maziausios sumos naudinga imti kartais nevisai maziausia skirtuma.

Taip ir padariau, taciau spendimas blogas, bendra minimali suma blogai pasiskaiciuoja. del benros maziausios sumos naudinga imti kartais nevisai maziausia skirtuma.

Parodyk prasau tokius duomenis, nes cia pries logika kazkaip man atrodo, maziausia suma skirtumu paskaiciuot tai ir skaiciuoji pacius maziausius skirtumus. EDIT: pazejau dabar auksciau duotus duomenis, sutinku.

viena minimalioji pora, gali pagadinti dvi kitas

esme panasiai tokia

bandau daryti bruteforce taciau nesiseka

Mano sprendimas:

struct slide { vector<int> numeris; int ilgis; slide(): numeris(0){ numeris.empty(); } }

1) Pasidaryt histogramą: slide L[2501]

L.numeris.size() - kiek slidžių yra ilgio L.

2) Minimalūs slidžių ilgių skirtumai bus tarp L[a] ir L, kur a < b, L[a] < L, L[a] > 0, L > 0 ir b iškarto eina po a (kur yra L > 0)

Tada išrenki N mažiausių ilgių skirtumų.

Šitas uždavinys nelengvas dinaminio programavimo uždavinys. Sprendimą pridedu 2 lengvensė jo versija, 3 tavo duota versija.

3e2_spr.pdf

Mano sprendimas būdas. Taikiau dinaminį programavimą ;) Testai 100/100

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;

const char Dfailas[] = "slides.in";
const char Rfailas[] = "slides.out";
const int  nMax      = 1002;                // man poru
const int  mMax      = 2002;                // max slidziu
int minSumos[mMax][nMax];
bool Poros[mMax][nMax];

struct Slide {
   int ilgis;
   int nr;
};

void Skaitymas(Slide A[], int& n, int& m);
void Rikiavimas(Slide A[], int m);
int MinSuma(Slide A[], int n, int m, int P[]);
void Rasymas(int P[], int n, int minS);

int main(void) {
   Slide Slides[mMax];
   int n;              // vaikų / porų kiekis
   int m;              // slidžių kiekis
   int minSuma;
   int SlidziuPoros[mMax];

   Skaitymas(Slides, n, m);
   Rikiavimas(Slides, m);
   minSuma = MinSuma(Slides, n, m, SlidziuPoros);

   Rasymas(SlidziuPoros, n, minSuma);
   return 0;
}

void Skaitymas(Slide A[], int& n, int& m) {
   ifstream fd(Dfailas);
       fd >> n >> m;
       for (int i = 0; i < m; i++) {
           fd >> A[i].ilgis;
           A[i].nr = i + 1;
       }
   fd.close();
}

void Rikiavimas(Slide A[], int m) {
   int tempIlgis, tempNr;
   for (int i = 0; i < m-1; i++)
       for (int j = i+1; j < m; j++)
           if (A[j].ilgis > A[i].ilgis) {
               // Apkeicia ilgius
               tempIlgis = A[j].ilgis;
               A[j].ilgis = A[i].ilgis;
               A[i].ilgis = tempIlgis;
               // Apkeicia numerius
               tempNr = A[j].nr;
               A[j].nr = A[i].nr;
               A[i].nr = tempNr;
           }
}

int MinSuma(Slide A[], int n, int m, int P[]) {
   int kiek = 0;
   for (int i = 0; i <= n; i++)
       for (int j = 0; j <= m; j++) {
           if (j < 2*i)
               minSumos[j][i] = 99999;
           else if (j == 2*i) {
               minSumos[j][i] = 0;
               for (int k = 0; k < j; k = k + 2)
                   minSumos[j][i] += A[k].ilgis - A[k+1].ilgis;
           }
           else if (i == 0)
             minSumos[j][i] = 0;
           else {
               if (minSumos[j-1][i] < minSumos[j-2][i-1] + A[j-2].ilgis - A[j-1].ilgis) {
                   minSumos[j][i] = minSumos[j-1][i];
                   Poros[j][i] = false;
               }
               else {
                   minSumos[j][i] = minSumos[j-2][i-1] + A[j-2].ilgis - A[j-1].ilgis;
                   Poros[j][i] = true;
               }
           }
       }
   int i = n;
   int j = m;
   while ((i > 0) && (j >= 2*i)) {
       if (Poros[j][i]) {
           P[kiek++] = A[j-1].nr;
           P[kiek++] = A[j-2].nr;
           j -= 2;
           i--;
       }
       else
           j--;
   }
   i--;
   while (i >= 0) {
       P[kiek++] = A[2*i].nr;
       P[kiek++] = A[2*i+1].nr;
       i--;
   }
   return minSumos[m][n];
}

void Rasymas(int P[], int n, int minS) {
   ofstream fr(Rfailas);
       fr << minS << endl;
       for (int i = 0; i < n*2; i = i + 2)
           fr << P[i] << " " << P[i+1] << endl;
   fr.close();
}

Kur galima pratestuoti programa?

Kur galima pratestuoti programa?

olimp.mif.vu.lt aplinkoje