9_drum
1
Liceul Teoretic de Informatică „Grigore Moisil” Iaşi CONCURS NAŢIONAL DE INFORMATICĂ Clasa a IX -a Problema 1 – drum 100 puncte Sursa: drum.c, drum.cpp, drum.pas Oraşele Nordemos şi Suderim sunt separate de un munte foarte înalt. Inginerul Negrimon a fost desemnat să construiască un drum prin munte care să unească cele două oraşe. Harta care i s-a pus la dispoziţie descrie muntele ca o matrice cu N linii şi M coloane numerotate de la 1 la N, respectiv de la 1 la M . Un drum reprezintă o succesiune de elemente din matrice cu proprietatea că oricare două elemente consecutive sunt alăturate, pe linie sau pe coloană. Un drum uneşte oraşul Nordemos (linia 1) şi oraşul Suderim (linia N). Valorile din matrice reprezintă densităţile rocilor din munte în acele zone. Pentru fiecare drum posibil se poate calcula valoarea dmax, egală cu densitatea maximă a rocilor pe care le traversează. Negrimon trebuie să construiască un drum pentru care valoarea dmax este cea mai mică. Cerinţa Ajută-l pe Negrimon să afle cea mai mică dintre densităţile dmax corespunzătoare drumurilor care unesc Nordemos şi Suderim în condiţiile de mai sus. Date de intrare Pe prima linie a fişierului drum.in se află valorile N M VMAX, separate prin câte un spaţiu, reprezentând numărul de linii, numărul de coloane, respectiv densitatea maximă posibilă a rocilor. Următoarele VMAX linii, conţin informaţii despre fiecare densitate de la 1 la VMAX. Astfel, linia k+1 din fişier are următoarea structură: nr p 1 p 2 p 3 … p nr unde nr este numărul de poziţii pe care apare densitatea k iar p 1 p 2 p 3 … p nr reprezintă poziţiile din matrice pe care apare aceasta (valorile sunt separate prin câte un spaţiu). Poziţiile din matrice sunt numerotate consecutiv, de la 1 la N*M, în sensul parcurgerii pe linii, începând cu linia 1. Pe fiecare linie elementele se numerotează de la stânga la dreapta. Date de ieşire În fişierul drum.out se va afla o singură valoare ce reprezintă densitatea căutată conform cerinţelor de mai sus. Restricţii 1 ≤ N,M ≤ 500 1 ≤ VMAX ≤ N*M 0 ≤ nr ≤ N*M Pentru fiecare poziţie din matrice, densitatea se citeşte exact o dată. Pot fi densităţi care nu apar în matrice (nr=0). Timp de execuţie: 0.13 sec/test Memorie totală disponibilă/stivă: 64MB / 8MB stivă Dimensiunea maximă a sursei: 10KB drum.in drum.out Explicaţii 5 5 11 2 3 8 1 23 1 19 1 11 5 9 12 13 15 20 3 4 24 25 1 5 4 10 14 17 21 6 1 2 6 16 18 22 1 7 0 8 Densitatea 1 apare pe două poziţii în matrice: 3 şi 8; densitatea 2 apare doar pe poziţia 23 etc. 9 9 1 6 7 9 10 1 5 8 4 5 5 8 5 9 8 9 3 5 8 9 2 6 6 Unul dintre drumurile cu proprietatea din enunţ este cel evidenţiat, valoarea dmax pentru acest drum este 8 şi nu există alt drum cu o densitate dmax mai mică. Densitatea 11 nu apare în matrice deoarece numărul de apariţii este 0.
description
u
Transcript of 9_drum
Liceul Teoretic de Informatică „Grigore Moisil” Iaşi
CONCURS NAŢIONAL DE INFORMATICĂ Clasa a IX-a
Problema 1 – drum 100 puncte Sursa: drum.c, drum.cpp, drum.pas
Oraşele Nordemos şi Suderim sunt separate de un munte foarte înalt. Inginerul Negrimon a fost desemnat să construiască un drum prin munte care să unească cele două oraşe. Harta care i s-a pus la dispoziţie descrie muntele ca o matrice cu N linii şi M coloane numerotate de la 1 la N, respectiv de la 1 la M . Un drum reprezintă o succesiune de elemente din matrice cu proprietatea că oricare două elemente consecutive sunt alăturate, pe linie sau pe coloană. Un drum uneşte oraşul Nordemos (linia 1) şi oraşul Suderim (linia N). Valorile din matrice reprezintă densităţile rocilor din munte în acele zone. Pentru fiecare drum posibil se poate calcula valoarea dmax, egală cu densitatea maximă a rocilor pe care le traversează. Negrimon trebuie să construiască un drum pentru care valoarea dmax este cea mai mică.
Cerinţa Ajută-l pe Negrimon să afle cea mai mică dintre densităţile dmax corespunzătoare drumurilor care unesc Nordemos şi Suderim în condiţiile de mai sus.
Date de intrare Pe prima linie a fişierului drum.in se află valorile N M VMAX, separate prin câte un spaţiu, reprezentând numărul de linii, numărul de coloane, respectiv densitatea maximă posibilă a rocilor. Următoarele VMAX linii, conţin informaţii despre fiecare densitate de la 1 la VMAX. Astfel, linia k+1 din fişier are următoarea structură: nr p1 p2 p3 … pnr unde nr este numărul de poziţii pe care apare densitatea k iar p1 p2 p3 … pnr reprezintă poziţiile din matrice pe care apare aceasta (valorile sunt separate prin câte un spaţiu). Poziţiile din matrice sunt numerotate consecutiv, de la 1 la N*M, în sensul parcurgerii pe linii, începând cu linia 1. Pe fiecare linie elementele se numerotează de la stânga la dreapta.
Date de ieşire În fişierul drum.out se va afla o singură valoare ce reprezintă densitatea căutată conform cerinţelor de mai sus.
Restricţii 1 ≤ N,M ≤ 500 1 ≤ VMAX ≤ N*M 0 ≤ nr ≤ N*M Pentru fiecare poziţie din matrice, densitatea se citeşte exact o dată. Pot fi densităţi care nu apar în matrice (nr=0).
Timp de execuţie: 0.13 sec/test Memorie totală disponibilă/stivă: 64MB / 8MB stivă Dimensiunea maximă a sursei: 10KB
drum.in drum.out Explicaţii 5 5 11 2 3 8 1 23 1 19 1 11 5 9 12 13 15 20 3 4 24 25 1 5 4 10 14 17 21 6 1 2 6 16 18 22 1 7 0
8 Densitatea 1 apare pe două poziţii în matrice: 3 şi 8; densitatea 2 apare doar pe poziţia 23 etc. 9 9 1 6 7 9 10 1 5 8 4 5 5 8 5 9 8 9 3 5 8 9 2 6 6 Unul dintre drumurile cu proprietatea din enunţ este cel evidenţiat, valoarea dmax pentru acest drum este 8 şi nu există alt drum cu o densitate dmax mai mică. Densitatea 11 nu apare în matrice deoarece numărul de apariţii este 0.
