https://wiki.universitas.ro/index.php?action=history&feed=atom&title=3468_-_weekend 2026-06-17T10:11:34Z Revision history for this page on the wiki MediaWiki 1.42.1 https://wiki.universitas.ro/index.php?title=3468_-_weekend&diff=9960&oldid=prev 2024-06-03T15:20:54Z

<p>Pagină nouă: == Enunt == În acest weekend tocmai s-au pus în vânzare bilete pentru concertul celui mai în vogă artist. Cum acesta este extrem de popular, un număr de n persoane s-au așezat la coadă la casa de bilete. Pentru simplitate, prima persoană așezată la coadă va avea indicele 1, a doua va avea indicele 2 și așa mai departe. Deoarece statul la coadă este extrem de plictisitor, fiecare om a început să numere câte persoane mai scunde decât el se află în fața s...</p> <p><b>New page</b></p><div>== Enunt ==<br /> <br /> În acest weekend tocmai s-au pus în vânzare bilete pentru concertul celui mai în vogă artist. Cum acesta este extrem de popular, un număr de n persoane s-au așezat la coadă la casa de bilete. Pentru simplitate, prima persoană așezată la coadă va avea indicele 1, a doua va avea indicele 2 și așa mai departe.<br /> <br /> Deoarece statul la coadă este extrem de plictisitor, fiecare om a început să numere câte persoane mai scunde decât el se află în fața sa. Se cunoaște că înălțimile oamenilor sunt reprezentate cu numere naturale nenule.<br /> <br /> Din lipsă de imaginație, oamenii care stau la coadă nu au reușit sa ducă jocul până la capăt, așa că o vom face noi. Cunoscând câte persoane mai scunde decât el are în față fiecare om care stă la coadă, se cere să se determine înălțimea fiecărui om din șir.<br /> <br /> Dacă există mai multe soluții valide, se cere afișată soluția minim lexicografică. Dacă există două șiruri valide de înălțimi ale celor n persoane A1, A2 ,…, An și B1, B2, …, Bn spunem că șirul A este mai mic lexicografic decât B dacă există un număr natural i mai mic sau egal decât n astfel încât Ai &lt; Bi și Aj = Bj, oricare ar fi j = 1..i-1.<br /> == Cerinţa ==<br /> Fiind dat șirul inițial de observații ale oamenilor care stau la coadă, să se reconstruiască șirul minim lexicografic care poate reprezenta înălțimile acestora.<br /> == Date de intrare ==<br /> Fișierul de intrare &#039;&#039;&#039;weekend.in&#039;&#039;&#039; va avea pe prima linie numărul &#039;&#039;&#039;n&#039;&#039;&#039;. Pe linia a doua se va afla un șir de &#039;&#039;&#039;n&#039;&#039;&#039; numere naturale despărțite printr-un spațiu, valoarea aflată pe poziția &#039;&#039;&#039;i&#039;&#039;&#039; semnificând numărul de persoane strict mai scunde decât persoana &#039;&#039;&#039;i&#039;&#039;&#039; și cu indice mai mic decât &#039;&#039;&#039;i&#039;&#039;&#039;.<br /> <br /> <br /> == Date de ieșire ==<br /> În fișierul de ieșire &#039;&#039;&#039;weekend.out&#039;&#039;&#039; se va afișa șirul înălțimilor. Pe linia a i-a din fișierul de ieșire se va afla înălțimea persoanei cu indicele i.<br /> == Restricţii şi precizări ==<br /> * Se garantează că setul de date este corect și va exista mereu cel puțin o soluție.<br /> * Două sau mai multe persoane NU pot avea aceeași înălțime.<br /> * &#039;&#039;&#039;1 ≤ N ≤ 200.000&#039;&#039;&#039;<br /> * Pentru 40% din teste, N &lt;= 5.000<br /> <br /> == Exemplul 1 ==<br /> ; weekend.in<br /> <br /> 4<br /> 0 1 1 0<br /> ; weekend.out<br /> <br /> 2<br /> 4<br /> 3<br /> 1<br /> == Explicație ==<br /> Observăm că acesta este cel mai mic șir lexicografic care satisface șirul de observații din input. O altă soluție ar fi fost șirul 2 5 3 1, dar acesta este mai mare lexicografic.<br /> &lt;br&gt;<br /> <br /> == Rezolvare ==<br /> &lt;syntaxhighlight lang=&quot;python&quot; line&gt;<br /> with open(&quot;weekend.in&quot;, &quot;r&quot;) as fin:<br /> n = int(fin.readline().strip())<br /> observations = list(map(int, fin.readline().split()))<br /> <br /> heights = [0] * n<br /> <br /> for i in range(n - 1, -1, -1):<br /> taller_count = observations[i]<br /> height = 1<br /> for j in range(taller_count):<br /> height = max(heights[i + j + 1] + 1, height)<br /> heights[i] = height<br /> <br /> with open(&quot;weekend.out&quot;, &quot;w&quot;) as fout:<br /> for height in heights:<br /> fout.write(str(height) + &quot;\n&quot;)<br /> <br /> &lt;/syntaxhighlight&gt;</div>

RebecaBud