BitCell

Your IT power source

Skip to content


[9] Concurs - Cursa

Topic locked

[9] Concurs - Cursa

Postby Mihai » 14 Jun 2011, 00:21

Cursa

Undeva, într-o galaxie foarte foarte îndepărtată, există o planetă numită Jup. Jup este o planetă plată în formă de dreptunghi, împărțită în N*M pătrate de arie egală (N fiind numărul de linii iar M numărul de coloane, ambele fiind numere naturale nenule mai mici sau egale cu 1000). Fiecare astfel de pătrat reprezintă o țară care poate fi unic identificată prin intermediul coordonatelor sale, X și Y.

În câteva zile, pe Jup va începe o cursă foarte interesantă, în care scopul este să ajungi în cel mai scurt timp posibil din țara din stânga-jos (cea de pe linia N și coloana 1) în cea din dreapta-sus (linia 1 și coloana M) folosind Jupmobilul. Prietenul tău, Iahim, vrea neapărat să câștige anul acesta. Pentru asta, însă, va avea nevoie de ajutorul tău!

Ajută-l pe Iahim să găsească drumul care-i va asigura victoria știind că:

  • fiecare țară poate fi traversată în orice direcție, timpul necesar traversării țării de pe linia X și coloana Y fiind T[X][Y]. Timpul necesar traversării unei țări este un număr natural nenul, mai mic sau egal cu 1000.
  • din țara de pe linia X și coloana Y se poate ajunge în maximum două țări:
    • țara de pe linia X-1 și coloana Y
    • țara de pe linia X și coloana Y+1
  • pentru orice viraj, se pierde un timp TOprire pentru oprirea efectivă a Jupmobilului din cauza inerției foarte mari de pe planeta Jup. Acest TOprire este același pentru toată planeta (deci este același indiferent de țară), fiind un număr natural nenul mai mic sau egal cu 1000.
    • prin viraj se înțelege orice întoarcere la 90⁰ - spre exemplu, dacă din țara de coordonate X și Y se trece în cea de coordonate X-1 și Y iar apoi în cea de coordonate X-1,Y+1, s-a efectuat un viraj la stânga.

Date de intrare – fișierul bitcell9.in:
Pe prima linie se vor afla N, M și TOprire cu semnificația din enunț. Pe următoarele linii, se va afla matricea T reprezentând timpul necesar fiecărei traversări.

Date de ieșire – fișierul bitcell9.out:
Pe prima linie a fișierului se va afișa timpul minim în care Iahim poate finaliza cursa. Pe următoarele linii se vor afișa, câte una pe linie, coordonatele țărilor prin care acesta va trece, în ordinea în care le vizitează.

Exemplu fișier de intrare:
Line number On/Off | Expand/Contract | Select all
  1. 5 3 10
  2. 7 3 3
  3. 1 3 2
  4. 3 1 1
  5. 8 2 2
  6. 1 3 6 


Exemplu fișier de ieșire:
Line number On/Off | Expand/Contract | Select all
  1. 28
  2. 5 1
  3. 5 2
  4. 5 3
  5. 4 3
  6. 3 3
  7. 2 3
  8. 1 3


Explicație:

Drumul minim:

733
132
311
822
136


Timpul necesar parcurgerii sale este 28:
1+3+6+2+1+2+3=18, la care se adaugă TOprire=10, timpul necesar întoarcerii Jupmobilului după vizitarea țării de pe linia 5 și coloana 3.

Perioada de desfășurare:
14-25 Iunie - înscrierea în concurs
26 Iunie - desemnarea câștigătorului
0,0p / 0 votes
User avatar
Mihai
Byte
 
Joined: 29 Dec 2009
Status: 25

Re: [9] Concurs - Cursa

Postby cata45 » 14 Jun 2011, 19:22

Facut sa citeasca din fisier (bitcell9.in).
Sper ca l-am gandit bine si ca nu am busit nimic :)

Executabilul: in atasament.
1p / 1 votes
Attachments
bitcell9-cata45.rar
(114.06 KiB) Downloaded 28 times
The EARTH without ART is just EH.
User avatar
cata45
Byte
 
Joined: 02 Sep 2010
Status: 9

Re: [9] Concurs - Cursa

Postby Mihai » 15 Jun 2011, 22:42

În locul tău l-aș mai testa puțin :).
Vezi ce-ți afișează pe exemplul ăsta:

Line number On/Off | Expand/Contract | Select all
  1. 5 3 10
  2. 7 3 3
  3. 1 3 2
  4. 3 1 20
  5. 8 2 2
  6. 1 3 6
0,0p / 0 votes
User avatar
Mihai
Byte
 
Joined: 29 Dec 2009
Status: 25

Re: [9] Concurs - Cursa

Postby cata45 » 16 Jun 2011, 11:36

Uneori afiseaza drumul bun si minimul gresit. Asta pentru ca nu am verificat schimbarile de directie... Ma uit in seara asta peste cod... daca nu imi vine nicio idee despre directie probabil o sa fac back in plan. Exista limita de memorie? Ma gandeam sa mai tin o matrice in care pun de cate ori am schimbat directia pana la elementul (i,j). Nu cred ca mai am timp sa fac vreo modificare. Maine plec in vacanta pentru cateva saptamani. O lucrez in vacanta dar nu cred ca ajung pana se termina concursul.
0,0p / 0 votes
The EARTH without ART is just EH.
User avatar
cata45
Byte
 
Joined: 02 Sep 2010
Status: 9

Re: [9] Concurs - Cursa

Postby Mihai » 16 Jun 2011, 15:54

Nu există limită de memorie așa că poți încerca un backtracking; sunt curios cam la ce performanțe reușești să-l duci.
Distracție plăcută în vacanță!
0,0p / 0 votes
User avatar
Mihai
Byte
 
Joined: 29 Dec 2009
Status: 25

Re: [9] Concurs - Cursa

Postby eni4ever » 17 Jun 2011, 20:16

Aplicația mea : aici.

Dacă îmi este permis (atât de regulament, dar mai ales de timp) voi reveni cu o variațiune, zic eu, interesantă.

Spor
0,0p / 0 votes
Last edited by eni4ever on 18 Jun 2011, 00:41, edited 1 time in total.
Image

"Rațiunea vine în umbre scurte numite suferințe." Victor Adăscăliței
"Bender: Anything less than immortality is a complete waste of time.
Zoidberg: Then suicide it is! Step into my office ..." Futurama S06E06
User avatar
eni4ever
DWord
 
Joined: 03 Jan 2010
Location: Timișoara
Status: 57.83

Re: [9] Concurs - Cursa

Postby Mihai » 17 Jun 2011, 23:46

Din păcate, nici programul tău nu se comportă cum ar trebui. Încearcă să vezi despre ce vorbesc pe testul ăsta:
Line number On/Off | Expand/Contract | Select all
  1. 3 3 100
  2. 4  4 1
  3. 4  4 100
  4. 1  4 400

Atât tu cât și Cătălin aveți, în ciuda implementării foarte diferite, aceeași greșeală de logică. Aveți mai mult de o săptămână să vă dați seama despre ce vorbesc așa că spor la treabă băieți!
0,0p / 0 votes
User avatar
Mihai
Byte
 
Joined: 29 Dec 2009
Status: 25

Re: [9] Concurs - Cursa

Postby eni4ever » 18 Jun 2011, 01:34

Bun Test! =D>

One more try ...
0,0p / 0 votes
Image

"Rațiunea vine în umbre scurte numite suferințe." Victor Adăscăliței
"Bender: Anything less than immortality is a complete waste of time.
Zoidberg: Then suicide it is! Step into my office ..." Futurama S06E06
User avatar
eni4ever
DWord
 
Joined: 03 Jan 2010
Location: Timișoara
Status: 57.83

Re: [9] Concurs - Cursa

Postby Mihai » 18 Jun 2011, 13:10

Încă un test:
Line number On/Off | Expand/Contract | Select all
  1. 5 3 15
  2. 7 3 3
  3. 1 3 2
  4. 3 1 20
  5. 8 2 2
  6. 1 3 6
0,0p / 0 votes
User avatar
Mihai
Byte
 
Joined: 29 Dec 2009
Status: 25

Re: [9] Concurs - Cursa

Postby eni4ever » 18 Jun 2011, 23:08

Oh well ... back to the drawing board! :)
0,0p / 0 votes
Image

"Rațiunea vine în umbre scurte numite suferințe." Victor Adăscăliței
"Bender: Anything less than immortality is a complete waste of time.
Zoidberg: Then suicide it is! Step into my office ..." Futurama S06E06
User avatar
eni4ever
DWord
 
Joined: 03 Jan 2010
Location: Timișoara
Status: 57.83

Re: [9] Concurs - Cursa

Postby eni4ever » 23 Jun 2011, 18:44

Vreau să văd o variantă dinamică ... până atunci, recursivitatea e soluția tuturor problemelor! :-W

Tape 3
3p / 1 votes
Image

"Rațiunea vine în umbre scurte numite suferințe." Victor Adăscăliței
"Bender: Anything less than immortality is a complete waste of time.
Zoidberg: Then suicide it is! Step into my office ..." Futurama S06E06
User avatar
eni4ever
DWord
 
Joined: 03 Jan 2010
Location: Timișoara
Status: 57.83

Re: [9] Concurs - Cursa

Postby Mihai » 26 Jun 2011, 10:39

Felicitări, Victor! Ultima variantă a ta, cea recursivă, este singura care merge - ce-i drept, la matrici de 20x20 am oprit execuția programului după un minut și ceva, dar pe testele mici e singurul care dă rezultatul corect. Drept urmare, ai câștigat și acest concurs.

Soluția lui eni4ever:
Line number On/Off | Expand/Contract | Select all
  1.  
  2. #include <QtCore/QCoreApplication>
  3. #include <QDebug>
  4. #include <QFile>
  5. #include <QTextStream>
  6. #include <limits>
  7. #include <QStringList>
  8.  
  9. const QString fisierPlanetaIntrare = "bitcell9.in";
  10. const QString fisierPlanetaIesire = "bitcell9.out";
  11.  
  12. class BCConcursPlaneta
  13. {
  14.     enum DirectieDeplasare{DirNedefinita, DirOrizontala, DirVerticala};
  15.  
  16. public:
  17.     BCConcursPlaneta() : costara(NULL){}
  18.     ~BCConcursPlaneta(){
  19.         int cnt;
  20.  
  21.         if(costara != NULL){
  22.             for(cnt = 0; cnt < latimep; ++cnt){
  23.              delete[] costara[cnt];
  24.             }
  25.             delete[] costara;
  26.         }
  27.     }
  28.  
  29.     unsigned int getLungimePlaneta(void){return lungimep;}
  30.     unsigned int getLatimePlaneta(void){return latimep;}
  31.  
  32.     bool IncarcaPlaneta()
  33.     {
  34.         int cntr;
  35.         int cntc;
  36.         QFile fplaneta(fisierPlanetaIntrare);
  37.  
  38.         if(fplaneta.open(QIODevice::ReadOnly) == false)
  39.         {
  40.             qWarning() << "Fisierul de intrare nu s-a putut deschide!";
  41.             return false;
  42.         }
  43.  
  44.         QTextStream cplaneta(&fplaneta);
  45.  
  46.         cplaneta >> latimep >> lungimep >> costcotire;
  47.         costara = new unsigned int*[latimep];
  48.  
  49.         for(cntr = 0; cntr < latimep; ++cntr)
  50.         {
  51.             costara[cntr] = new unsigned int[lungimep];
  52.             for(cntc = 0; cntc < lungimep; ++cntc)
  53.             {
  54.                 cplaneta >> costara[cntr][cntc];
  55.             }
  56.         }
  57.  
  58.         fplaneta.close();
  59.  
  60.         return true;
  61.     }
  62.  
  63.     bool proceseazaDrumMihai(void)
  64.     {
  65.         return proceseazaDrumMinim(0, getLatimePlaneta() - 1,
  66.                                    getLungimePlaneta() - 1, 0);
  67.     }
  68.     bool proceseazaDrumMinim(unsigned int stx, unsigned int sty,
  69.                              unsigned int endx, unsigned int endy)
  70.     {
  71.         unsigned int costMinLoc = std::numeric_limits<unsigned int>::max();
  72.         QStringList trasLocal;
  73.  
  74.         drumMinimLocal.clear();
  75.         procDrumMinimRecursiv(DirNedefinita,
  76.                               0, costMinLoc,
  77.                               trasLocal,
  78.                               stx, sty, endx, endy);
  79.  
  80.         return (drumMinimLocal.isEmpty() == false);
  81.     }
  82.  
  83.     void scrieRezultat()
  84.     {
  85.         QFile fiesire(fisierPlanetaIesire);
  86.  
  87.         if(fiesire.open(QIODevice::WriteOnly | QIODevice::Text) == false){
  88.             qWarning() << "Nu am putut deschide fisierul pentru scriere!";
  89.             return;
  90.         }
  91.  
  92.         QTextStream ores(&fiesire);
  93.  
  94.         foreach(QString res, drumMinimLocal)
  95.         {
  96.             ores << res << "\n";
  97.         }
  98.         fiesire.close();
  99.     }
  100.  
  101. protected:
  102.     virtual void procDrumMinimRecursiv(DirectieDeplasare dirCur,
  103.                                        unsigned int costCurent, unsigned int &costMinim,
  104.                                        QStringList &trasLocCur,
  105.                                        int curx, int cury,
  106.                                        int endx, int endy)
  107.     {
  108.         if(curx < lungimep && cury >= 0)
  109.         {
  110.             costCurent += costara[cury][curx];
  111.             trasLocCur.push_back(QString("%1 %2").arg(cury + 1).arg(curx + 1));
  112.  
  113.             if(dirCur == DirVerticala)
  114.             {
  115.                 procDrumMinimRecursiv(DirOrizontala,
  116.                                       costCurent + costcotire, costMinim,
  117.                                       trasLocCur,
  118.                                       curx + 1, cury, endx, endy);
  119.             }
  120.             else
  121.             {
  122.                 procDrumMinimRecursiv(DirOrizontala,
  123.                                       costCurent, costMinim,
  124.                                       trasLocCur,
  125.                                       curx + 1, cury, endx, endy);
  126.             }
  127.  
  128.             if(dirCur == DirOrizontala)
  129.             {
  130.  
  131.                 procDrumMinimRecursiv(DirVerticala,
  132.                                       costCurent + costcotire, costMinim,
  133.                                       trasLocCur,
  134.                                       curx, cury - 1, endx, endy);
  135.             }
  136.             else
  137.             {
  138.                 procDrumMinimRecursiv(DirVerticala,
  139.                                       costCurent, costMinim,
  140.                                       trasLocCur,
  141.                                       curx, cury - 1, endx, endy);
  142.             }
  143.  
  144.  
  145.             if(curx == endx && cury == endy &&
  146.                costCurent < costMinim)
  147.             {
  148.                 costMinim = costCurent;
  149.                 drumMinimLocal = trasLocCur;
  150.                 drumMinimLocal.push_front(QString("%1").arg(costMinim));
  151.             }
  152.  
  153.             trasLocCur.pop_back();
  154.             costCurent -= costara[cury][curx];
  155.         }
  156.     }
  157.  
  158. private:
  159.     unsigned int costcotire;
  160.     int latimep;
  161.     int lungimep;
  162.     unsigned int **costara;
  163.     QStringList drumMinimLocal;
  164. };
  165.  
  166. int main(int argc, char *argv[])
  167. {
  168.     //QCoreApplication a(argc, argv);
  169.  
  170.     BCConcursPlaneta aventurabc;
  171.  
  172.     if(aventurabc.IncarcaPlaneta())
  173.     {
  174.         if(aventurabc.proceseazaDrumMihai())
  175.         {
  176.             aventurabc.scrieRezultat();
  177.         }
  178.     }
  179.  
  180.     return 0;//a.exec();
  181. }


Soluția lui cata45:
Line number On/Off | Expand/Contract | Select all
  1. #include <fstream>
  2. using namespace std;
  3. #define IN "bitcell9.in"
  4. #define OUT "bitcell9.out"
  5. #define MaxN 10010
  6. fstream f(IN, ios::in), g(OUT, ios::out);
  7. long a[MaxN][MaxN], b[MaxN][MaxN], i, j, n, m, T, cate, val;
  8. bool ok;
  9.  
  10. struct A{
  11.     int i;
  12.     int j;
  13. }drum[3011];
  14.  
  15. int minim(int a, int b)
  16. {
  17.     if(a<b)
  18.         return a;
  19.     return b;
  20. }
  21. int main()
  22. {
  23.     f>>n>>m>>T;//citire date
  24.     for(i=1; i<=n; ++i)
  25.     {
  26.         for(j=1; j<=m; ++j)
  27.             f>>a[i][j];
  28.     }
  29.     f.close();
  30.    
  31.     for(i=n; i>=1; --i)//formare ultima linie si prima coloana in b
  32.     {
  33.         for(j=1; j<=m; ++j)
  34.         {
  35.             if(i==n)
  36.                 b[i][j]=b[i][j-1]+a[i][j];
  37.             if(j==1 && i!=n)
  38.                 b[i][j]=b[i+1][j]+a[i][j];
  39.         }
  40.     }
  41.    
  42.     for(j=2; j<=m; ++j)//formare penultima linie in b
  43.         b[n-1][j]=minim(b[n][j]+T+a[n-1][j] , b[n-1][j-1]+T+a[n-1][j]);
  44.    
  45.     for(i=n-2; i>=1; --i)//formare b
  46.     {
  47.         for(j=2; j<=n; ++j)
  48.             b[i][j]=minim(b[i][j-1]+T+a[i][j] , b[i+1][j]+a[i][j]);
  49.     }
  50.    
  51.     g<<b[1][m]<<endl;//afisare minim
  52.    
  53.     cate=1;//reconstituie drum
  54.     drum[cate].i=1;
  55.     drum[cate].j=m;
  56.     val=b[1][m]-a[1][m];
  57.     ok=false;
  58.    
  59.     while(ok==false)
  60.     {
  61.         if(b[drum[cate].i][drum[cate].j-1]==val)
  62.         {
  63.             cate++;
  64.             drum[cate].i=drum[cate-1].i;
  65.             drum[cate].j=drum[cate-1].j-1;
  66.             val=val-a[drum[cate].i][drum[cate].j];
  67.         }
  68.         else  
  69.             if(b[drum[cate].i+1][drum[cate].j]==val)
  70.             {
  71.                 cate++;
  72.                 drum[cate].i=drum[cate-1].i+1;
  73.                 drum[cate].j=drum[cate-1].j;
  74.                 val=val-a[drum[cate].i][drum[cate].j];
  75.             }
  76.             else
  77.                 val=val-T;
  78.            
  79.         if(val==a[n][1])
  80.             ok=true;
  81.     }
  82.    
  83.     g<<n<<" "<<1<<endl;
  84.     for(i=cate; i>=1; --i)
  85.         g<<drum[i].i<<" "<<drum[i].j<<endl;
  86.     g.close();
  87.     return 0;
  88.    
  89. }


Șmecheria problemei constă în faptul că trebuie să reții pentru fiecare țară drumul minim atât venind din partea stângă cât și de jos. Asta permitea o rezolvare în O(M*N).
0,0p / 0 votes
User avatar
Mihai
Byte
 
Joined: 29 Dec 2009
Status: 25
Topic locked

Return to Concursuri de programare desktop

Who is online

Users browsing this forum: No registered users and 0 guests


Powered by phpBB © phpBB Group
cron