Lista de probleme 46

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#1691 Arbore1

Se dă un arbore (graf conex aciclic) cu N noduri. Vrem să eliminăm noduri (împreună cu muchiile adiacente) din arborele dat, astfel încât numărul de componente conexe ale grafului rămas să fie maxim. Aflați care este numărul maxim de componente conexe pe care le putem obține și câte submulțimi distincte de noduri se pot elimina din arbore astfel încât să rămână la final acest număr maxim de componente conexe.

Un graf conex cu N noduri și M muchii poate fi privit ca o clepsidră cu centrul în nodul X, 1 ≤ X ≤ N, dacă putem împărți toate nodurile, mai puțin nodul X, în două submulțimi nevide astfel încât orice drum de la un nod dintr-o mulțime la un nod din cealaltă mulțime trece prin nodul X. Voi trebuie să determinați numărul de moduri distincte în care putem privi graful ca o clepsidră pentru fiecare din cele N noduri alese drept centru, modulo 666013. Două moduri se consideră distincte dacă cele două submulțimi aferente sunt diferite. Ordinea submulțimilor într-un mod este relevantă, dar ordinea nodurilor în cadrul unei mulțimi nu este. Spre exemplu, soluțiile ({1,2,3}, {4,5}) şi ({4,5}, {1,2,3}) sunt distincte, dar soluţiile ({4,5}, {1,2,3}) şi ({4,5}, {1,3,2}) nu sunt distincte.

#1199 Metrou

Această problemă este dedicată celor care așteaptă metroul cu cea mai mare ardoare: locuitorii din Drumul Taberei.

Se dă planul unei rețele de metrou cu N stații și M tuneluri bidirecționale între stații. Două stații de metrou se numesc vecine dacă există un tunel între ele în acest plan. Fiecare stație i are asociat un profit p[i] dat.

Henry a fost recent promovat dintr-un post de angajat al departamentului de curățenie pe postul de project manager al firmei. Deoarece nu există fonduri pentru construirea întregii rețele de metrou, Henry trebuie să aleagă o submulțime de stații care vor fi construite, astfel încât oricare două stații alese să nu fie vecine în planul inițial. Pentru a-și păstra poziția în companie, suma profiturilor stațiilor alese în această submulțime trebuie să fie maximă.

Dându-se N, M, profiturile aduse de fiecare din cele N stații și planul inițial al rețelei, să se determine suma maximă a profiturilor stațiilor pe care le poate alege Henry astfel încât oricare două stații alese să nu fie vecine în planul inițial.

#2165 graf1

Se știe că într-un graf neorientat conex, între oricare două vârfuri există cel putin un lanț iar lungimea unui lanț este egală cu numărul muchiilor care-l compun. Definim noțiunea lanț optim între două vârfuri X și Y ca fiind un lanț de lungime minimă care are ca extremități vârfurile X și Y. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe lanțuri optime, depinzând de configurația grafului. Fiind dat un graf neorientat conex cu N vârfuri etichetate cu numerele de ordine 1, 2, …, N și două vârfuri ale sale notate X și Y (1 ≤ X, Y ≤ N, X≠Y ), se cere să scrieți un program care determină vârfurile care aparțin tuturor lanțurilor optime dintre X și Y.

#1021 Cartite

Cârtițele sunt animale de dimensiuni mici care își duc traiul pe suprafețe de teren deschis, având ca dușman principal vulpea. Lângă o pădure se află o zonă agricolă în forma dreptunghiulară, împărțită în pătrățele de aceeași dimensiune. Zona agricolă este reprezentată printr-un tablou bidimensional cu M linii și N coloane, având liniile și coloanele numerotate începând cu 1. În aceasta zona agricolă trăiește o cârtiță și K vulpi.

Pentru cârtiță cunoaștem coordonatele ei (linia și coloana) pe care se găsește, la fel și pentru vulpi, care stau la pânda pentru a ataca cârtita în momentele ei de neatenție.
Pe suprafața terenului cârtita se poate deplasa din patrațelul în care se afla doar într-unul dintre cele 4 pătrățele vecine pe direcțiile nord, sud, est sau vest.
Vulpile pot ataca instantaneu pe o raza de acțiune de lungime 0, 1 sau 2 pe orizontala și verticala, inclusiv în poziția unde se găsesc, după care tot instantaneu se întorc în pozițiile inițiale. În figura de mai jos sunt desenate pătrățele unde poate ataca o vulpe poziționață în pătrățelul cu cifra reprezentând raza de acțiune.

Pentru a micșora riscul de deplasare în zona agricolă cârtița sapă în pământ un sistem de G galerii, care leagă între ele pătrățele din zona agricola. Aceste galerii nu se intersectează sub pamânt, ci doar la suprafață, trecerea dintr-o galerie în alta, care se intersectează în același pătrățel făcându-se printr-un sistem ce nu îi pune viata în pericol. Galeriile sunt indicate prin coordonatele pătrățelelor pe care le unesc. Acestea sunt săpate astfel încât, dacă pornim dintr-un capăt al unei galerii le putem parcurge pe toate. Nu exista doua galerii care sa pornească din același pătrățel și să ajungă tot în același pătrățel (galeriile sunt distincte).

Cârtița dorește sa se plimbe prin toate galeriile de sub teren trecând o singura data prin fiecare, dar pentru acest lucru trebuie sa ajungă nevătămată mergând la suprafața terenului la un pătrățel de unde să intre în sistemul de galerii.

Determinați:

1. cel mai apropiat pătrățel de poziția inițială a cârtitei prin care ea poate să intre în galerie pentru a se plimba, precum și lungimea traseului parcurs la suprafață astfel încât fiecare pătrățel de pe traseu sa nu fie atacat de nicio vulpe;
2. traseul de plimbare numai prin galerii, specificat prin coordonatele pătrățelelor care constituie capetelor acestora.

#1136 Dragoni

Supărați că lansarea părții a treia a filmului lor preferat s-a amânat până în iunie 2018, Henry și Hetty s-au gândit la propriul scenariu pentru finalul trilogiei:

Într-o lume în care vikingii pot zbura cu dragonii există N insule. Hiccup, șeful tribului de vikingi aflat pe insula 1, știe M rute directe de zbor bidirecționale între insule. Pentru fiecare j intre 1 si M, ruta j unește insulele A j și B j și are lungime D j.

Pe fiecare insulă i, (1 ≤ i ≤ n) există dragoni din specia i care pot zbura fără a se opri pentru odihnă o distanță maximă Dmax i. Cu alte cuvinte, dragonii de pe insula i vor putea parcurge orice rută j, (1 ≤ j ≤ m) pentru care Dj ≤ Dmaxi, indiferent de ce alte drumuri au făcut anterior.

Hiccup dorește să ajungă de pe insula 1 pe insula N pentru a-l salva pe Toothless, dragonul lui. Pentru a ajunge acolo, el va lua inițial un dragon din specia 1 (de pe insula 1). Apoi, dacă la un moment dat Hiccup se află pe o insula i, (1 ≤ i ≤ n) având cu el un dragon din specia t, el poate:

  1. Să zboare de pe insula i pe o altă insulă x cu dragonul pe care îl are, folosind o rută directă j între insulele i si x, bineînțeles doar dacă Dj ≤ Dmaxt.
  2. Să schimbe dragonul din specia t pe care îl are cu un dragon din specia i aflat pe insula respectivă.

Cerințe:

a. Să se determine distanța maxima Dmaxi caracteristică unui dragon la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula 1.
b. Să se determine distanța minimă pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula 1 pe insula N.

Arhipelagul Zopopan este format din n insule de formă triunghiulară numerotate de la 1 la n. Fiecare insulă este localizată prin coordonatele carteziene ale vârfurilor.

Administrația dorește să cumpere elicoptere pentru a realiza transportul între insule. Un elicopter va putea să asigure o rută între două insule pe distanța minimă obținută pe orizontală sau verticală (paralel cu axele de coordonate). În plus, datorită capacității rezervorului o astfel de rută nu poate să depășească o valoare k – număr natural. Elicopterele parcurg rutele în ambele sensuri.
Investiția trebuie să îndeplinească următoarele condiții:

  1. Numărul de elicoptere cumpărate să fie minim.
  2. Numărul de perechi de insule între care se poate realiza transportul, folosind unul sau mai multe elicoptere să fie maxim.
  3. Suma lungimii tuturor rutelor să fie minimă.

Să se scrie un program care pentru n, k şi coordonatele vârfurilor insulelor cunoscute, determină:

  1. numărul minim de elicoptere ce vor fi cumpărate de administraţie;
  2. numărul perechilor neordonate de insule între care se poate realiza transportul prin elicoptere direct sau indirect;
  3. suma distantelor parcurse de toate elicopterele cumpărate (distanța parcursă de un elicopter se consideră distanța dintre insulele între care acesta asigură transportul).

Cătălin avea un singur prieten dar, fiind foarte sociabil, el se împrietenește automat cu toți prietenii prietenului său și cu prietenii prietenilor acestuia ș.a.m.d. (s-a inspirat din modelul Facebook).

Inițial, în grupul de persoane, nimeni nu are prieteni dar, pe parcursul timpului, se leagă noi relații de prietenie.

Definim două tipuri de operații:

  • 1 x y – ce reprezintă faptul că x se împrietenește cu y.
  • 2 p – Cătălin vă întreabă care este numărul de prieteni pe care îi poate avea, dacă inițial ar fi prieten doar cu p. Se va ține cont doar de relațiile de prietenie stabilite până în acel moment.

#1497 Nunta

La o nuntă sunt invitate n persoane, numerotate de la 1 la n. Se știe că o parte din ele se cunosc două câte două, fie că sunt rude, fie de la serviciu, fie sunt prieteni sau vecini. Astfel se vor forma un număr K minim de grupuri astfel încât în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut. Pentru fiecare grup de cel puțin două persoane se stabileşte un lider – persoana cu numărul de ordine minim. Aceste grupuri vor fi numerotate de la 1 la K în ordinea crescătoare a numerelor de ordine ale liderilor. Ca sa se ivească cât mai puține situații stânjenitoare, organizatorul nunții ar dori să aranjeze o masă principală cu cel puţin n/2+1 invitaţi, la care să fie aşezate unul sau mai multe astfel de grupuri întregi numerotate cu valori consecutive.

Fiind date n, numărul de persoane, m, numărul de perechi de invitaţi care se cunosc între ei și cele m perechi, să se determine numărul minim de grupuri formate din cel puțin doi invitați astfel încât, în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut, precum şi numărul variantelor distincte în care se poate organiza masa cu cel puţin n/2+1 invitaţi din grupurile formate.

#1979 rbtree

Gigel se joacă cu un graf orientat cu N noduri. Inițial toate nodurile grafului sunt transparente, dar lui Gigel îi place schimbarea. Fire ambițioasă, el colorează unele noduri în roșu, altele în negru, iar pe celelalte în alb (probabil din cauza crizei de vopsea colorată din 2017).

Gigel recrutează o armată de furnici pe care o așează în nodul 1, cu el în fruntea lor și se hotărăște să cucerească graful.În fiecare moment, Gigel poate trimite un număr de furnici din orice nod X (în care se află deja furnici) în vecinii lui X, cu condiția ca cel puțin o furnică să rămână în nodul X. Excepție de la această regulă face nodul 1, cel în care se află Gigel, unde nu este obligatoriu să rămână furnici.

Dacă într-un nod se află Gigel sau cel puțin o furnică, atunci acel nod se numește ocupat. Graful este cucerit atunci când Gigel a ocupat cel puțin un nod roșu și cel puțin un nod negru.

Sa se determine numărul minim de furnici pentru ca Gigel să cucerească graful.

Info Oltenia 2017, Clasele XI-XII, individual