Skip to main content
Učilnica FRI 24/25
  • Home
  • More
Close
Toggle search input
English ‎(en)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
You are currently using guest access
Log in
Učilnica FRI 24/25
Home
Expand all Collapse all
  1. aps1uni
  2. Požrešni algoritmi
  3. Akrobati

Akrobati

Completion requirements
Due: Sunday, 12 November 2023, 11:59 PM

Skupina akrobatov razmišlja o novi točki, v kateri bi postavili čim višji človeški stolp, ki bi bil sestavljen iz vseh $N$ članov skupine. Pri tem bi vsak akrobat stal na ramenih nekega drugega akrobata (oz. spodnji akrobat na tleh). Za vsakega člana poznamo njegovo težo $t_i$ in moč $m_i$. Akrobat z močjo $m$ lahko na svojih ramenih podpira stolp akrobatov s skupno težo največ $m$. Naleteli pa so na težavo pri določanju vrstnega reda članov v stolpu. Napišite program, ki bo ugotovil, ali se akrobati s podanimi težami in močmi lahko razvrstijo tako, da sestavijo stolp ali ne.

Omejitve podatkov:

  • $1 \leq T \leq 100$
  • $0 \leq t_i, m_i \leq 10^{9}$
  • Število akrobatov v vseh $T$ testnih primerih skupaj ne bo preseglo $10^5$.

Vhodni in izhodni podatki:

V prvi vrstici se nahaja število $T$, ki predstavlja število primerov oz. skupin akrobatov. Posamezni primeri si nato sledijo en za drugim. Vsak primer se začne s številom akrobatov $N$ v prvi vrstici. V drugi vrstici so s presledkom ločene teže akrobatov $t_i$, v tretji pa njihove moči $m_i$.

Za vsako skupino akrobatov izpišite DA ali NE, glede na to, ali lahko sestavijo človeški stolp.

Primer vhoda:

2
5
7 3 10 5 2
25 6 40 11 2
2
6 2
1 5

Pravilen izhod:

DA
NE
You are currently using guest access (Log in)
Get the mobile app
Powered by Moodle
Obvestilo o avtorskih pravicah