Detalii evaluare: ~49936199

Detalii evaluare #49936199

Rezumat problema
Detalii
Evaluare
Ajutor

Rezumat problemă

`#1788` Rege1

Regele Leonidas trebuie să-și aleagă o armată de 300 de spartani. Surprins de mulțimea mare de voluntari care vor să-l urmeze în viitoarea luptă de la Termopile, regele are nevoie să facă o selecție a războinicilor. Astfel, el a decis să le dea următoarea problemă:

Se dă un arbore cu N noduri (etichetate cu numere consecutive începând de la 1) cu rădăcina în nodul 1, în care fiecare muchie are asociat un cost. Se definește un lanț în jos în arbore ca fiind orice lanț simplu ce unește un nod A cu alt nod B din subarborele lui A. Cu alte cuvinte, un lanț în jos este un lanț de la A la B în care A este strămoș al lui B. Definim costul unui lanț în jos ca fiind suma costurilor muchiilor din care este format lanțul.

Numim acoperire a unui arbore o partiționare a muchiilor în lanțuri disjuncte, a căror reuniune este arborele inițial. Regele Leonidas dorește să acopere întreg arborele cu lanțuri în jos, însa are un număr limitat de lanțuri, notat în continuare cu S.

Se cere să se determine cel mai mic număr K pentru care să existe o partiționare completă a arborelui cu maxim S lanțuri astfel încât costul fiecărui lanț să fie cel mult K. Dacă nu există un astfel de număr K, să se afișeze -1.

Pentru că și tu vrei să lupți alături de Leonidas pentru libertatea Spartei, trebuie să rezolvi această problemă ca să-ți asiguri un loc în primii 300 de spartani. Leonidas este un rege înțelept. Ca să se asigure că nu vor exista Spartani care vor încerca să ghicească rezultatul, el vă cere să răspundeți la T astfel de probleme.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

Fișiere
Candale Silviu (silviu)
concurs

Clasa 11 Teoria Grafurilor Arbori cu rădăcină

Rezolvă

Detalii

Problema	Rege1	Operații I/O	`rege1.in`/`rege1.out`
Limita timp	1.5 secunde	Limita memorie	Total: `64 MB` / Stivă `8 MB`
Id soluție	`#49936199`	Utilizator	Lezau Andrei (Lezau_Andrei)
Fișier	rege1.cpp	Dimensiune	1.81 KB
Data încărcării	20 Martie 2024, 13:58	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

rege1.cpp:1:1: error: stray '\`' in program
 \`\`\`#include <bits/stdc++.h>

 ^
rege1.cpp:1:1: error: stray '\`' in program
rege1.cpp:1:1: error: stray '\`' in program
rege1.cpp:1:4: error: stray '#' in program
 \`\`\`#include <bits/stdc++.h>

    ^
rege1.cpp:101:1: error: stray '\`' in program
 \`\`\`
 ^
rege1.cpp:101:1: error: stray '\`' in program
rege1.cpp:101:1: error: stray '\`' in program
rege1.cpp:1:5: error: 'include' does not name a type
 \`\`\`#include <bits/stdc++.h>

     ^
rege1.cpp:4:1: error: 'ifstream' does not name a type
 ifstream fin("rege1.in");

 ^
rege1.cpp:5:1: error: 'ofstream' does not name a type
 ofstream fout("rege1.out");

 ^
rege1.cpp:11:20: error: 'vector' has not been declared
 int BFS(int start, vector <vector <pair <int, int>>> &a, vector <int> &visited, int ma_val)

                    ^
rege1.cpp:11:27: error: expected ',' or '...' before '<' token
 int BFS(int start, vector <vector <pair <int, int>>> &a, vector <int> &visited, int ma_val)

                           ^
rege1.cpp: In function 'int BFS(int, int)':
rege1.cpp:13:6: error: 'queue' was not declared in this scope
      queue pair<<int, int>> q;

      ^
rege1.cpp:13:12: error: expected ';' before 'pair'
      queue pair<<int, int>> q;

            ^
rege1.cpp:14:5: error: 'q' was not declared in this scope
     q.push(start, 0);

     ^
rege1.cpp:22:26: error: 'a' was not declared in this scope
         for (auto next : a[node])

                          ^
rege1.cpp:23:18: error: 'visited' was not declared in this scope
             if (!visited[next.first])

                  ^
rege1.cpp:26:13: error: expected ';' before '}' token
             }

             ^
rege1.cpp:19:13: warning: unused variable 'cost' [-Wunused-variable]
         int cost = q.front().second();

             ^
rege1.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }

 ^
rege1.cpp: In function 'int main()':
rege1.cpp:34:5: error: 'fin' was not declared in this scope
     fin >> t;

     ^
rege1.cpp:44:9: error: 'vector' was not declared in this scope
         vector <vector <pair<int, int>>> a (n + 1);

         ^
rege1.cpp:44:25: error: 'pair' was not declared in this scope
         vector <vector <pair<int, int>>> a (n + 1);

                         ^
rege1.cpp:44:30: error: expected primary-expression before 'int'
         vector <vector <pair<int, int>>> a (n + 1);

                              ^
rege1.cpp:44:30: error: expected ';' before 'int'
rege1.cpp:45:17: error: expected primary-expression before 'int'
         vector <int> g_out(n + 1, 0);

                 ^
rege1.cpp:45:17: error: expected ';' before 'int'
rege1.cpp:46:17: error: expected primary-expression before 'int'
         vector <int> g_in(n + 1, 0);

                 ^
rege1.cpp:46:17: error: expected ';' before 'int'
rege1.cpp:51:13: error: 'a' was not declared in this scope
             a[x].push_back(make_pair(y, c));

             ^
rege1.cpp:51:42: error: 'make_pair' was not declared in this scope
             a[x].push_back(make_pair(y, c));

                                          ^
rege1.cpp:54:13: error: 'g_out' was not declared in this scope
             g_out[x]++;

             ^
rege1.cpp:55:13: error: 'g_in' was not declared in this scope
             g_in[y]++;

             ^
rege1.cpp:59:13: error: 'cout' was not declared in this scope
             cout << g_out[i] << ' ';

             ^
rege1.cpp:59:21: error: 'g_out' was not declared in this scope
             cout << g_out[i] << ' ';

                     ^
rege1.cpp:60:9: error: 'cout' was not declared in this scope
         cout << endl;

         ^
rege1.cpp:60:17: error: 'endl' was not declared in this scope
         cout << endl;

                 ^
rege1.cpp:62:21: error: 'g_in' was not declared in this scope
             cout << g_in[i] << ' ';

                     ^
rege1.cpp:68:16: error: 'g_in' was not declared in this scope
             if(g_in[i] > 1 || g_out[i] > 1) brnch++;

                ^
rege1.cpp:68:31: error: 'g_out' was not declared in this scope
             if(g_in[i] > 1 || g_out[i] > 1) brnch++;

                               ^
rege1.cpp:72:13: error: 'fout' was not declared in this scope
             fout << -1;

             ^
rege1.cpp:90:9: error: 'vector' was not declared in this scope
         vector <int> visited (n + 1, 1e9);

         ^
rege1.cpp:90:17: error: expected primary-expression before 'int'
         vector <int> visited (n + 1, 1e9);

                 ^
rege1.cpp:90:17: error: expected ';' before 'int'
rege1.cpp:91:26: error: 'a' was not declared in this scope
         int val = BFS(1, a, visited, mid);

                          ^
rege1.cpp:91:29: error: 'visited' was not declared in this scope
         int val = BFS(1, a, visited, mid);

                             ^
rege1.cpp:95:24: error: 'mid_d' was not declared in this scope
             mi_d = min(mid_d, val);

                        ^
rege1.cpp:95:34: error: 'min' was not declared in this scope
             mi_d = min(mid_d, val);

                                  ^

Cum funcționează evaluarea?

www.pbinfo.ro permite evaluarea a două tipuri de probleme:

probleme la care rezolvarea presupune scrierea unui program complet
probleme la care rezolvarea presupune scrierea unei secvențe de program - câteva instrucțiuni, o listă de declarații, una sau mai multe funcții, etc.

Problema Rege1 face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:

Programul sursă este compilat folosind compilatorul corespunzător. Dacă în urma compilării se obțin erori sau avertismente, acestea sunt afișate în această pagină.
Dacă programul a fost compilat, executabilul obținut va fi rulat, furnizându-i-se unul sau mai multe seturi de date de intrare, în concordanță cu restricțiile specifice problemei. Pentru fiecare set de date se obține un anumit punctaj, în raport cu corectitudinea soluției tale.

Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.