Despre acest subiect
Etapa 2
Sursa documentelor: Facultatea de Informatică UVT – Concursul FI. Verifică răspunsurile cu baremul după ce rezolvi subiectul.
Se încarcă profesorii disponibili…
Subiect și barem
Sursa: Facultatea de Informatică UVT – Concursul FI
Subiectul și răspunsurile sunt în același PDF. Afișăm documentul complet, cu toate paginile.
Subiectul și baremul în format text
Text extras automat din documentul original. Pentru formule, tabele, imagini și așezarea răspunsurilor, verifică întotdeauna PDF-ul.
Subiect și barem · 1 pagină
Subiect și barem · pagina 1
UNIVERSITATEA DE VEST TIMIS, OARA FACULTATEA DE MATEMATICĂ S, I INFORMATICĂ Concurs FMI ed. VI-a 2021 Informatică Problema Se dau n intervale închise [a1, b1], [a2, b2], . . ., [an, bn] s, i un număr natural k (k < n). Presupunem că: (i) cele 2n extremităt, i ale intervalelor sunt valori întregi distincte; (ii) niciunul dintre intervale nu este inclus într-un alt interval. Propunet, i un algoritm cât mai eficient care să determine câte intervale intersectează exact alte k intervale. De exemplu, pentru setul de intervale [1, 3], [4, 8], [2, 5], [6, 9] s, i k = 2 există două intervale care satisfac cerint, a: [2, 5] se intersectează cu: [1, 3], [4, 8]; [4, 8] se intersectează cu: [2, 5], [6, 9]. Prezentat,i pe scurt ideea de rezolvare s, i descriet,i solut,ia în pseudocod sau într-un limbaj de programare la alegere (C/C++, Pascal, Python). BAREM Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct. Teste valide pe platforma stepik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct. În urma explicat, iilor de la proba orală Rezolvare completă în n2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct. sau în nlog(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 pct. Descrierea ideii de rezolvare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct. Implementare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct. Idee de rezolvare în nlog(n) Pentru că intervalele nu se pot cont, ine unele pe altele s, i pentru că avem capete unice, un algoritm eficient O(nlog(n)) este: Pas 1 O(nlog(n)): Sortăm crescător capetele intervalelor a1,b1, a2, b2, . . ., an, bn folosind o sortare de complexitate nlog(n), păstrând informat, ii despre: tip capăt (stânga - S, dreapta - D) s, i identificator de interval. Pentru exemplul propus stocăm următoarele informat, ii: capete interval 1 2 3 4 5 6 8 9 identificator interval (ID) 1 3 1 2 3 4 2 4 tip_capat S S D S D S D D Pas 2 O(n): Se parcurge s, irul sortat anterior s, i dacă întâlnim un capăt stânga vom nota indexul de pozit, ie într-un alt vector, iar când intâlnim un capăt dreapta calculăm câte intervale intersecteazâ intervalul dat, prin diferent, a indicilor extremităt, ilor. pentru i ← 1, 2n execută dacă tip_capat[i] = S atunci intersectii[ID[i]] = i // capatul stang altfel intersectii[ID[i]] = i - intersectii[ID[i]] - 1 // capatul stang minus cel drept − 1 Pas 3 O(n): Se parcurge vectorul intersectii s, i se numără câte elemente sunt egale cu k (cerut în enunt, ). 1
Continuă pregătirea
Vezi arhiva completăAlte subiecte de la aceeași facultate
Concurs de pregătire · 2021Informatică · Etapa 1Deschide fișa Concurs de pregătire · 2021Matematică · Clasa a XI-a, etapa 1Deschide fișa Concurs de pregătire · 2021Matematică · Clasa a XII-a, etapa 1Deschide fișa Examen de admitere · 2021Informatică · Sesiunea iulie; subiect oficialDeschide fișa Examen de admitere · 2021Matematică · Sesiunea iulie; subiect oficialDeschide fișa Concurs de pregătire · 2022Informatică · Etapa 1Deschide fișa
Răspunsuri directe
Ce trebuie să știi despre acest subiect?
Ce document de admitere este acesta?
Pagina prezintă concurs de pregătire din 2021 pentru Informatică, la Facultatea de Informatică. Documentul este etichetat după instituție, facultate, program și tipul probei folosind inventarul public verificat. Consultă metodologia actuală a instituției pentru condițiile examenului viitor.
Există și barem sau răspunsuri pentru acest subiect?
Da. Pagina include baremul sau răspunsurile publice asociate acestui subiect, afișate separat ori în același document atunci când sursa le publică împreună. Verifică fiecare rezolvare după ce ai terminat varianta și urmărește exact criteriile de punctare indicate de instituție.
Cum folosesc acest subiect în pregătirea pentru admitere?
Rezolvă documentul fără ajutor și respectă timpul prevăzut de metodologia examenului. Corectează cu baremul disponibil, marchează capitolele unde ai pierdut puncte și repetă exerciții similare. Compară apoi cu alte probe din aceeași facultate și confirmă programa curentă pe site-ul oficial al instituției.
