Acest site foloseşte cookies. Navigând în continuare, vă exprimaţi acordul asupra folosirii cookie-urilor.

Lista de probleme 7

Filtrare

Mai multe opțiuni

#3904 SeqCuts

Se dă șir de N caractere, format din litere mici ale alfabetului englez, din care trebuie eliminate K secvențe disjuncte de lungime L. Care este cel mai mic şir din punct de vedere lexicografic ce se poate obține după eliminarea tuturor celor K secvențe.

ad-hoc

Rezolvă

#4687 Feast

Se dă un șir de \(N\) numere întregi. Să se aleagă maxim \(K\) secvențe disjuncte astfel încât suma elementelor incluse în secvențe să fie maximă.

NOISG 2019, problema 3

Rezolvă

#1373 reactivi

Într-un laborator de analize chimice se utilizează N reactivi. Se ştie că, pentru a evita accidentele sau deprecierea reactivilor, aceştia trebuie să fie stocaţi în condiţii de mediu speciale. Mai exact, pentru fiecare reactiv x, se precizează intervalul de temperatură [minx, maxx] în care trebuie să se încadreze temperatura de stocare a acestuia.
Reactivii vor fi plasaţi în frigidere. Orice frigider are un dispozitiv cu ajutorul căruia putem stabili temperatura (constantă) care va fi in interiorul acelui frigider (exprimată într-un număr întreg de grade Celsius).

OJI 2004, Clasa a IX-a

Rezolvă

#681 orase1

Pe axa reală există N orașe, numerotate cu numerele 1, 2, 3, …, N. Deși într-o lume unidimensională lucrurile par a fi mult mai simple, totuși majoritatea locuitorilor sunt nemulțumiți de distanțele mari parcurse între orașe în scopul rezolvării diferitelor probleme. Astfel, pentru o mai bună organizare, s-a supus la vot și s-a decis promovarea a cel mult K orașe la rangul de centru adminstrativ. Centrele trebuie amplasate într-un mod isteț, în așa fel încât distanța maximă calculată dintre distanțele de la fiecare oraș la cel mai apropiat centru administrativ să fie cât mai mică. Întrucât costurile de administrare ale unui astfel de centru sunt ridicate, se dorește să se amplaseze un număr cât mai mic de centre administrative astfel încât distanța maximă să nu fie modificată.

Lot Juniori, Vaslui, 2014

Rezolvă

#3032 sufle

Sufle este un personaj cu urechi ascuțite, îndrăgostit de algoritmică. El are o antipatie profundă față de Aisimok, cel care îl tot provoacă să rezolve probleme folosind tot felul de formule. Sufle a botezat aceste probleme Emsiteanap. Astăzi Aisimok i-a aruncat tânărului Sufle o nouă provocare:

Pentru oricare două numere naturale se definește următoarea operație:

  • se consideră reprezentările în baza 2 pentru cele două numere;
  • se alege o poziție în reprezentarea binară a primului număr;
  • se schimbă cifra situată pe acea poziție în primul număr cu cifra aflată pe exact aceeași
    poziție în al doilea număr. (Observați cum Aisimok, obsedat de matematică, nu a folosit termenul bit, tocmai pentru a-l irita pe Sufle.)

Pentru un șir oarecare de numere naturale, se poate aplica de oricâte ori și asupra oricăror două numere operația descrisă mai sus. Scopul final este ca suma pătratelor numerelor din șir să ajungă la valoarea minim posibilă. Denumim costul șirului acestă valoare minimă.

Pentru a deveni și mai antipatic, Aisimok îi cere lui Sufle să calculeze aceast cost pentru mai multe subsecvențe ale unui șir dat. Costul unei subsecvențe este egal cu costul șirului definitit de subsecvența dată.

Cerința: Pentru un șir cunoscut și pentru mai multe subsecvențe date să se calculeze suma minimă a pătratelor numerelor din subsecvență după aplicare a operației descrise, de oricâte ori se consideră necesar și asupra oricăror numere din subsecvență.

Baraj ONI 2017

Rezolvă

#2785 galeti

Avem n găleți numerotate de la stânga la dreapta numere de la 1 la n. Fiecare găleată conține inițial 1 litru de apă. Capacitatea fiecărei găleți se consideră nelimitată. Vărsăm gălețile una în alta, respectând o anumită regulă, până când toată apa ajunge în prima găleată din stânga. Vărsarea unei găleți presupune un anumit efort. Cunoscând numărul de găleți n și un număr natural e, să se determine o succesiune de vărsări în urma căreia toată apa ajunge în găleata cea mai din stânga și efortul total depus este exact e.

OJI 2018, clasele XII-XII

Rezolvă

#2514 warcraft

Durotan, căpetenia clanului Frostwolf, face o ultima încercare în a cuceri clanurile rivale (Orcish Horde). Conform ierarhiei Orcish, căpeteniile de clan sunt denumite warchief, în timp ce liderii triburilor sunt denumiți șamani. Triburile din care fac parte căpeteniile sunt triburi dominante, iar triburile conduse de șamani sunt triburi vasale. Pe planetă există N triburi, numerotate de la 1 la N. Șamanul unui trib are anumite abilități de luptă. Căpetenia unui clan este șamanul tribului său. Abilitățile de luptă cunoscute de șamani sunt numerotate de la 1 la M. De-a lungul timpului între triburile aceluiași clan s-au stabilit relații de vasalitate. Dacă tribul 1 este trib dominant al tribului vasal 2, iar tribul 2 are ca vasal tribul 3, vom spune că tribul 3 se află în zona de influență a triburilor 1 și 2. Triburile 1,2,3 alcătuiesc un clan. Puterea unei căpetenii depinde de numărul triburilor ce alcătuiesc clanul, precum și de abilitățile de luptă învățate. Căpetenia unui clan are anumite abilități de luptă, dar poate să-și însușească (învețe) și abilități de luptă unice de la șamanii triburilor clanului aflate în zona sa de influență. Prin abilități de luptă unice înțelegem abilități cunoscute doar de un singur șaman din totalitatea triburilor clanului. Fiind cunoscute pentru cele N triburi abilitățile fiecărui șaman, relațiile de vasalitate între triburi, numărul de ordine al unui trib al clanului Frostwolf, să se determine:
  • numărul total de clanuri
  • numărul de triburi din clanul Frostwolf înainte de duel
  • numărul maxim de triburi pe care Duroton le poate avea după invocarea codului Mak’gora.

Lot juniori Câmpulung Muscel, 2018

Rezolvă