https://wiki.universitas.ro/index.php?action=history&feed=atom&title=2006_-_Mana 2026-05-01T03:50:09Z Revision history for this page on the wiki MediaWiki 1.42.1 https://wiki.universitas.ro/index.php?title=2006_-_Mana&diff=9023&oldid=prev 2024-01-04T21:06:45Z

<p>Pagină nouă: == Cerinţa == Înștiințat de atacul orcilor, Gandalf și-a luat măsurile de precauție. Credinciosul spion i-a adus acestuia o hartă care arată pozițiile celor &#039;&#039;&#039;n&#039;&#039;&#039; orci. Harta poate fi reprezentată ca un sistem cartezian de coordonate. Gandalf vrea să folosească o vrajă astfel încât să anihileze cel puțin &#039;&#039;&#039;k&#039;&#039;&#039; orci. De asemenea, acesta vrea să folosească cât mai puțină mana. Știind că, dacă utilizează &#039;&#039;&#039;r&#039;&#039;&#039; mana (&#039;&#039;&#039;r&#039;&#039;&#039; număr natural), și v...</p> <p><b>New page</b></p><div>== Cerinţa ==<br /> Înștiințat de atacul orcilor, Gandalf și-a luat măsurile de precauție. Credinciosul spion i-a adus acestuia o hartă care arată pozițiile celor &#039;&#039;&#039;n&#039;&#039;&#039; orci. Harta poate fi reprezentată ca un sistem cartezian de coordonate. Gandalf vrea să folosească o vrajă astfel încât să anihileze cel puțin &#039;&#039;&#039;k&#039;&#039;&#039; orci. De asemenea, acesta vrea să folosească cât mai puțină mana. Știind că, dacă utilizează &#039;&#039;&#039;r&#039;&#039;&#039; mana (&#039;&#039;&#039;r&#039;&#039;&#039; număr natural), și vraja este folosită în punctul de coordonate &#039;&#039;&#039;(x,y)&#039;&#039;&#039;, acesta anihilează toți orcii din interiorul cercului cu centrul în &#039;&#039;&#039;(x,y)&#039;&#039;&#039; de rază &#039;&#039;&#039;r&#039;&#039;&#039;, aflați mana minimă necesară pentru a anihila &#039;&#039;&#039;k&#039;&#039;&#039; orci.<br /> == Date de intrare ==<br /> Fișierul de intrare &#039;&#039;&#039;manain.txt&#039;&#039;&#039; conține pe prima linie două numere naturale &#039;&#039;&#039;n&#039;&#039;&#039;, &#039;&#039;&#039;k&#039;&#039;&#039;, cu semnificațiile din enunț. Pe următoarele &#039;&#039;&#039;n&#039;&#039;&#039; linii se găsesc câte două numere întregi separate printr-un spațiu, reprezentând abscisa respectiv ordonata fiecărui orc de pe hartă.<br /> == Date de ieșire ==<br /> Fișierul de ieșire &#039;&#039;&#039;manaout.txt&#039;&#039;&#039; va conține pe prima linie numărul &#039;&#039;&#039;r&#039;&#039;&#039;, reprezentând mana minimă pe care o poate utiliza Gandalf pentru a anihila &#039;&#039;&#039;k&#039;&#039;&#039; orci.<br /> == Restricţii şi precizări ==<br /> * &#039;&#039;&#039;1 &amp;les; k &amp;les; n &amp;les; 100&#039;&#039;&#039;<br /> * Numerele din fișierul de intrare sunt întregi cuprinse între &#039;&#039;&#039;-100000&#039;&#039;&#039; și &#039;&#039;&#039;100000&#039;&#039;&#039;.<br /> == Exemplul 1 ==<br /> ;&#039;&#039;&#039;manain.txt&#039;&#039;&#039;<br /> 5 3<br /> 3 3<br /> 5 3<br /> 1 -5<br /> -4 1<br /> 0 3<br /> ;&#039;&#039;&#039;manaout.txt&#039;&#039;&#039;<br /> 3<br /> == Exemplul 2 ==<br /> ;&#039;&#039;&#039;manain.txt&#039;&#039;&#039;<br /> 5 3<br /> 3 3<br /> 5 3<br /> 1 -5<br /> -4 1<br /> 1000001 3<br /> ;&#039;&#039;&#039;manaout.txt&#039;&#039;&#039;<br /> Datele de intrare nu corespund restrictiilor impuse<br /> == Rezolvare ==<br /> &lt;syntaxhighlight lang=&quot;python&quot; line&gt;<br /> from math import sqrt, ceil<br /> <br /> <br /> def distanta(p1, p2):<br /> return sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)<br /> <br /> <br /> def mana_minima(n_val, k_val, orci_val):<br /> if not (1 &lt;= k_val &lt;= n_val &lt;= 100):<br /> return &quot;Datele de intrare nu corespund restrictiilor impuse&quot;<br /> if any(abs(orc[0]) &gt; 100000 or abs(orc[1]) &gt; 100000 for orc in orci_val):<br /> return &quot;Datele de intrare nu corespund restrictiilor impuse&quot;<br /> <br /> distante = []<br /> for orc in orci_val:<br /> distante_orc = sorted(distanta(orc, orc2) for orc2 in orci_val)<br /> distante.append(distante_orc[k_val - 1])<br /> return ceil(min(distante))<br /> <br /> <br /> with open(&#039;manain.txt&#039;, &#039;r&#039;) as fin:<br /> n, k = map(int, fin.readline().strip().split())<br /> orci = [list(map(int, line.split())) for line in fin]<br /> result = mana_minima(n, k, orci)<br /> <br /> with open(&#039;manaout.txt&#039;, &#039;w&#039;) as fout:<br /> fout.write(str(result))<br /> &lt;/syntaxhighlight&gt;<br /> == Explicatie ==<br /> Gandalf poate să folosească vraja în punctul de abscisă &#039;&#039;&#039;2,5&#039;&#039;&#039; și ordonată &#039;&#039;&#039;3&#039;&#039;&#039;.</div>

Brianna Waltner