Soluții trimise

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

ID   Utilizator Problema Data încărcării Stare
Gherghesanu Alex (AlexGHM) card 08 Februarie 2024, 22:27 Evaluare finalizată 100
Rusu Cezar (Cezar_Rusu) card 08 Februarie 2024, 15:42 Evaluare finalizată 100
Rusu Cezar (Cezar_Rusu) card 08 Februarie 2024, 15:39 Evaluare finalizată 70
Benchea Matei (matei__b) card 08 Februarie 2024, 09:22 Evaluare finalizată 100
Cristiana Balcanu (pancakes) card 06 Februarie 2024, 22:56 Evaluare finalizată 100
Cristiana Balcanu (pancakes) card 06 Februarie 2024, 22:11 Evaluare finalizată 0
Budaca Miruna Maria (BudacaMirunaMaria) card 02 Februarie 2024, 20:56 Evaluare finalizată 100
Iordache Alexandru (Hackerul_Gogu) card 31 Ianuarie 2024, 08:26 Evaluare finalizată 60
Iordache Alexandru (Hackerul_Gogu) card 31 Ianuarie 2024, 08:24 Evaluare finalizată 10
Iordache Alexandru (Hackerul_Gogu) card 31 Ianuarie 2024, 08:15 Evaluare finalizată 0
Buzdugan Mihnea-Andrei (Buzdugan_Mihnea_Andrei) card 26 Ianuarie 2024, 19:52 Evaluare finalizată 100
Plesescu Alex-Albert (AlexPlesescu) card 26 Ianuarie 2024, 17:56 Evaluare finalizată 100
Pricop Cristian (PricopCristian) card 26 Ianuarie 2024, 17:43 Evaluare finalizată 100
Shaan Stefan (Shaan_Stefan) card 26 Ianuarie 2024, 17:24 Evaluare finalizată 100
Andrei Paul (paul_andrei_0304) card 26 Ianuarie 2024, 13:48 Evaluare finalizată 100
Buruiana Rares Andrei (Bufu) card 25 Ianuarie 2024, 13:46 Evaluare finalizată 0
Savin Alexandru-Stefan (Alex10123) card 21 Ianuarie 2024, 15:02 Evaluare finalizată 100
Savin Alexandru-Stefan (Alex10123) card 21 Ianuarie 2024, 14:56 Evaluare finalizată 10
Baragau Rares Andreas (Baragau_Rares_Andreas) card 20 Ianuarie 2024, 22:04 Evaluare finalizată 100
Baragau Rares Andreas (Baragau_Rares_Andreas) card 20 Ianuarie 2024, 20:38 Evaluare finalizată 0
Baragau Rares Andreas (Baragau_Rares_Andreas) card 20 Ianuarie 2024, 17:10 Evaluare finalizată 0
Maftei Tudor (TudorMaf) card 20 Ianuarie 2024, 14:01 Evaluare finalizată 100
Tomita Matey (mateytomita) card 20 Ianuarie 2024, 12:48 Evaluare finalizată 100
Stoleriu Radu (RaduStoleriu) card 20 Ianuarie 2024, 11:51 Evaluare finalizată 100
Vasiliu David (Vasiliu_David) card 20 Ianuarie 2024, 09:50 Evaluare finalizată 100
Gorea-Zamfir Claudiu-Cristian (gorea_claudiu) card 20 Ianuarie 2024, 09:49 Evaluare finalizată 100
Ciobanu Alexia (Alexia_Ciobanu) card 10 Ianuarie 2024, 19:56 Evaluare finalizată 100
Ciobanu Alexia (Alexia_Ciobanu) card 10 Ianuarie 2024, 19:56 Evaluare finalizată 0
Ciobanu Alexia (Alexia_Ciobanu) card 10 Ianuarie 2024, 19:52 Evaluare finalizată 70
Toncea Andrei (andrei170) card 15 Decembrie 2023, 18:09 Evaluare finalizată 100
POPESCU ANDREI (andreip99) card 13 Decembrie 2023, 14:42 Evaluare finalizată 100
Anca Leuciuc (AncaLeuciuc) card 11 Decembrie 2023, 21:35 Evaluare finalizată 100
Nicula Andreea (Andrusca2008) card 04 Decembrie 2023, 15:34 Evaluare finalizată 100
Diaconeasa Mihai (Mihai_999) card 12 Noiembrie 2023, 19:08 Evaluare finalizată 100
Pavalache Albert (Albert_2006) card 09 Noiembrie 2023, 18:30 Evaluare finalizată 100
Pavalache Albert (Albert_2006) card 09 Noiembrie 2023, 18:30 Evaluare finalizată 100
Pavalache Albert (Albert_2006) card 09 Noiembrie 2023, 18:27 Evaluare finalizată 0
Militaru Mihai (Mihaimilitaru2022) card 05 Noiembrie 2023, 15:49 Evaluare finalizată 100
alexandru iordache (Alexi123) card 22 Octombrie 2023, 11:03 Evaluare finalizată 100
Milandru Nicon-David (DomnulMilandru) card 17 Octombrie 2023, 12:35 Evaluare finalizată 100
Milandru Nicon-David (DomnulMilandru) card 17 Octombrie 2023, 10:50 Evaluare finalizată 0
Acatrinei Teodor (acatrineite) card 06 Octombrie 2023, 14:56 Evaluare finalizată 100
Dracea Andora (Andora_fan) card 04 August 2023, 18:08 Evaluare finalizată 100
prof CNTV (tudor) card 04 August 2023, 11:17 Evaluare finalizată 100
Iernutan Alexandru Razvan (Iernutan_Alexandru_Razvan) card 23 Iulie 2023, 13:11 Evaluare finalizată 100
Adrian Statescu (thinkphp) card 04 Iulie 2023, 17:57 Evaluare finalizată 100
Jula Andreea (candycigarettes) card 29 Mai 2023, 20:35 Evaluare finalizată 100
Carp Iulia (iuliacarp1234) card 24 Mai 2023, 18:47 Evaluare finalizată 100
cont de teste (iulia_the_rocker) card 24 Mai 2023, 18:45 Evaluare finalizată 100
cont de teste (iulia_the_rocker) card 24 Mai 2023, 18:39 Evaluare finalizată 100