Detalii evaluare #41994243

Rezumat problemă

#2355 card

În orașul Imios se află n galerii ce au locații interesante de vizitat (muzee, expoziții, castele), notate de la 1 la n. O galerie conține m locații, notate de la 1 la m. Fiecare locație are atribuit un număr de puncte, unic ca valoare. Orașul are multe birouri de informare turistică, de unde turiștii pot cumpăra un card de o zi pentru vizitarea locațiilor. Pe fiecare card se înregistrează punctul de plecare, notat prin 2 numere: numărul galeriei și cel al locației, din care se pot vizita cel mult k locații din oraș, diferite de punctul de plecare. Cardul are înregistrat un număr de puncte, ce vor fi utilizate în locațiile vizitate. Alegând o locație ce are x puncte, turistul poate selecta 4 categorii de vizitare, ce modifică punctele de pe card astfel:

  • categoria rapidă: numărul de puncte de pe card se reduce cu dublul lui x
  • categoria extinsă: numărul de puncte de pe card se reduce cu x/2 puncte
  • categoria medie: la numărul de puncte de pe card se adaugă x puncte
  • categoria clasică: din numărul de puncte de pe card se scad x puncte.

Alexandru a cumpărat un card și dorește să viziteze cât mai puține locații și să utilizeze toate punctele de pe card. Împreună cu cardul, a primit o hartă electronică a locațiilor din oraș, codificată printr-o matrice h, având n linii și m coloane, pe care este înregistrat numărul de puncte al fiecărei locații. Pe hartă, punctul de plecare, înregistrat pe card, conține numărul de puncte disponibile pe card pentru vizitare. A fost informat că după vizitarea unei locații, se poate deplasa numai într-o locație vecină cu aceasta în cele 8 direcții (N, NE, E, SE, S, SV, V, NV). Fiecare locație poate fi vizitată o singură dată, pe baza cardului. Alexandru a decis că dacă are mai multe variante posibile de vizitare, din care să aleagă, va opta pentru acea variantă în care ultima locație are cel mai mic număr de puncte. Dacă există mai multe variante de vizitare care au același număr minim de puncte pentru ultima locație, va opta pentru varianta în care prima locație are cel mai mic număr de puncte. Două variante de vizitare diferă prin: locațiile lor, ordinea locațiilor vizitate și categorii de vizitare alese pentru locații.

Să se scrie un program care obține numărul de variante posibile de vizitare a unor locații din oraș, care conțin cât mai puține locații vizitate din punctul de plecare, ce asigură utilizarea tuturor punctelor de pe card și lista punctelor din locațiile vizitate, în ordinea vizitării lor, pentru varianta pe care Alexandru o alege.

Olimpiada Municipala de Informatica, Iasi, 2018

Detalii

Problema card Operații I/O card.in/card.out
Limita timp 3 secunde Limita memorie Total: 32 MB / Stivă 8 MB
Id soluție #41994243 Utilizator Drăgan Alexandru (Alexander12)
Fișier card.cpp Dimensiune 2.05 KB
Data încărcării 10 Februarie 2023, 18:19 Scor / rezultat 100 puncte

Evaluare


Mesaj compilare


Rezultat evaluare

Test Timp Mesaj evaluare Scor posibil Scor obținut
0 0 secunde OK. 10 10
1 0 secunde OK. 10 10
2 0.04 secunde OK. 10 10
3 0.004 secunde OK. 10 10
4 0.036 secunde OK. 10 10
5 0.008 secunde OK. 10 10
6 0.012 secunde OK. 10 10
7 0.02 secunde OK. 10 10
8 0.164 secunde OK. 10 10
9 0.024 secunde OK. 10 10
Punctaj total 100

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 card 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ă.