Lista de probleme 448

Filtrare

Dificultate

Operații intrare/ieșire

Un nou joc vă este adus de Vlad. O tablă de n*m căsuțe goale, câteva cartonașe și o singură întrebare! Voi știți răspunsul?

#1651 Graf

Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care media aritmetică a ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică.

Cu ocazia sărbătoririi marii victorii de la ONI2017, cei 10 Bistrițeni au pornit la drum cu scopul de a-și întemeia o țară. După multe dezbateri, aceștia s-au hotărât să o numească Zoomba. Și au mers ei ce au mers, până au ajuns într-un ținut pustiu, iar atunci, marele Zoli a spus: “Și aici să fie întemeiată Zoomba!” (La început, Zoomba nu are niciun oraș). Iulia are sarcina de a construi orașele, iar Maria va construi drumurile ce vor conecta orașele. Astfel, se disting următoarele evenimente:

  • 1: Iulia construiește un nou oraș. Dacă ultimul oraș construit este orașul x, atunci noul oraș va fi x + 1 (Dacă nu există niciun oraș în acel moment, atunci noul oraș construit va fi 1).
  • 2 x y c: Maria propune construcția unui drum bidirecțional ce leagă orașul x de orașul y de cost c.
  • 3 x: Zoli se întreabă care este costul minim pentru a lega un număr maxim de orașe (folosind drumurile propuse de Maria) cu scopul construirii unui județ (un județ este o grupare de orașe în care se poate ajunge din orice oraș în orice alt oraș) ce conține orașul x.

Scrieți un program care procesează M evenimente de tipurile precizate mai sus, și afișează în fișierul de ieșire rezultatele evenimentelor de tipul 3.

#2018 rogvaiv

Vecinul meu, Dorel, tocmai s-a mutat la casă şi vrea să-şi vopsească gardul. Fiind îndrăgostit de frumos, a cumpărat 7 cutii de vopsea: roşu, orange, galben, verde, albastru, indigo şi violet. Acum însă, are o dilemă: în câte moduri poate vopsi cele n uluci ale gardului, ştiind că fiecare ulucă poate fi vopsită cu oricare dintre culorile cumpărate?

#1652 RF

Se dă un graf orientat în care arcele au asociate costuri (numere naturale nenule). Să se determine câte arce (x,y) din graf au costul egal cu costul drumului de cost minim de la x la y.

#1666 Arbrush

Eșuînd în a-și regăsi adevărata identitate, Brush se refugiază în magicul tărâm al arborilor. Arbotra o sună și îi dă următoarea problemă: se dă un arbore cu N noduri, o rădăcină fixată, și M întrebări de forma: câte perechi neordonate de noduri pot forma, luând noduri doar din subarborele nodului X (inclusiv pe X).

Dijkstra are nevoie de ajutorul vostru pentru a-și duce la bun sfârșit datoria. Acesta vrea să afle drumurile de lungime minimă de la casa prietenului său Vlad la celelalte case ale vecinilor. Nu are foarte mult timp la dispoziție așa ca trebuie să vă mișcați repede. Îl veți ajuta?

#2493 recc

Ana Mia are o recurență liniară de forma P[N] = A[1]*P[N-1] + A[2]*P[N-2] + A[3]*P[N-3] + A[4]*P[N-4], N ≥ 5. Studiind-o, îi vine o idee MAXIMĂ de problemă: “Pentru câte cvadriplete (P[1], P[2], P[3], P[4]) din mulțimea numerelor naturale [1, B] valoarea P[N] modulo K are valoarea X?”

Se consideră un șir T de segmente în plan, ale căror extremități au coordonate numere întregi. Considerând subșirul SS al segmentelor care nu conțin alte puncte coliniare de coordonate numere întregi, în afară de extremități, să se determine lungimea subșirului maximal crescător al șirului SS, unde relația de ordine crescător(Si, Sj) se traduce prin Lungimea(SSi)<=Lungimea(SSj).

#2338 skipass

La un parc de sporturi de iarnă au venit G grupuri de schiori numerotate de la 1 la G. Aceștia coboară pe
una dintre cele 2 pârtii disponibile dar urcă cu același teleschi. Teleschiul folosește T-bar-uri, o modalitate eficientă de a urca schiorii pe vârful pârtiei.

Un T-bar poate trage maxim 2 schiori odată. Deoarece sunt 2 pârtii, se formează 2 rânduri de oameni de-o parte și de alta a punctului de urcare în teleschi. Se știe că 2 schiori nu vor folosi același T-bar decât dacă fac parte din același grup. De asemenea, niciun schior nu se baga în fața altuia (toți sunt foarte corecți și răbdători). Atunci când un T-bar sosește, primul om de la una dintre cozi se urcă în el și pleacă sau așteaptă să se
urce încă cineva (din același grup cu el). Acest al doilea schior trebuie sa fie totuși primul de la coada lui (nimeni nu se bagă în față).

Care este numărul minim de T-bar-uri ce trebuie folosite astfel încât toți schiorii de la ambele rânduri să ajungă în vârful pârtiei?