Pentru a putea rula codul, te rugăm să te autentifici.

main.cpp

​x
 
#include <iostream>
​
using namespace std;
​
int main()
{
    cout << "Hello, World!" << endl;
    return 0;
}

ID #810 · Olimpiada Locală de Informatică 2025, Brașov, clasa a XI-a · Probleme diverse

Problema Chestionar

Dificilă · 8

Memorie: 64 MB / 32 MB

Timp: 0.3 secunde

I/O: Fișiere

Șeful lui Matei îi oferă drept primă sarcină la noul loc de muncă implementarea unui chestionar pentru utilizatorii unei aplicații. Mai exact, Matei trebuie să utilizeze un fișier de intrare în care fiecare linie i are forma următoare: t_i r_i k j₁ j₂ … j_k, unde t_i reprezintă timpul necesar alegerii răspunsului la întrebarea i, r_i reprezintă relevanța întrebării, k reprezintă numărul de posibile răspunsuri ale întrebării, iar indicii j₁, j₂, …, j_p, …, j_k faptul că pentru răspunsul cu indicele p ales, următoarea întrebare adresată utilizatorului va fi cea cu indicele j_p. Dacă valoarea indicelui j_p este 0, chestionarul se finalizează după alegerea acelui răspuns. Întrebările sunt numerotate de la 1, iar prima întrebare a chestionarului este mereu cea cu indicele 1. Matei a implementat chestionarul, însă, are nevoie de ajutor pentru următoarele cerințe ale angajatorului.

Cerință

Chestionarul a fost trimis către utilizatorii aplicației, iar acum trebuie să analizați rezultatele:

Care este traseul care obține timpul minim de finalizare al chestionarului? Utilizatorii încep, desigur, răspunzând la întrebarea 1.
Se dă traseul de întrebări și răspunsuri găsit cel mai abordat de către utilizatori. Eficientizați acest traseu, eliminând întrebări astfel încât să obțineți relevanța maximă, fără ca timpul total al traseului să depășească valoarea T. Eliminarea unei întrebări în acest context rezultă în legarea răspunsului întrebării anterioare la întrebarea succesivă pe traseu. Se poate elimina inclusiv prima întrebare.

Date de intrare

Fișierul chestionar.in conține pe prima linie un număr întreg, N, reprezentând numărul de întrebări ale chestionarului. Pe următoarele N linii se află specificate trecerile dintre întrebări, conform cerinței. Pe linia N+2 se află valoarea C, reprezentând numărul cerinței care trebuie rezolvată. Pentru:

C=1: nu se dau alte date de intrare
C=2: pe același rând se află și valoarea T, cu semnificația din enunț. Pe rândul N+3 se oferă traseul cel mai abordat: întâi numărul de răspunsuri selectate de utilizator pe parcursul traseului, urmat apoi de un șir de indici de răspunsuri ale întrebărilor.

Date de ieșire

Fișierul chestionar.out conține pentru:

C=1: un întreg, valoarea timpului minim de rezolvare a chestionarului
C=2: un întreg, relevanța maximă care se poate obține fără a depăși timpul total T

Restricții și precizări

3 ≤ n ≤ 10000 (unde n este numărul de întrebări);
Pentru teste în valoare de 50 puncte C=1;
Pentru teste în valoare de 50 puncte C=2;
1 ≤ t_i ≤ 10000, 1 ≤ r_i ≤ 10000;
1 ≤ k ≤ 2500;
Lungimea maximă a traseului cel mai abordat de la cerința 2 este 5000.

Exemple

chestionar.in

5
2 5 3 2 4 5
3 3 2 3 3
1 1 2 0 0
3 5 2 3 5
2 2 2 0 0
1

chestionar.out

Explicație

Chestionarul conține 5 întrebări. Următoarele trasee sunt valide:

Q1 Q2 Q3 și Q1 Q4 Q3, găsite dacă utilizatorul alege primul răspuns la prima întrebare și orice răspuns la întrebarea 2, respectiv al doilea răspuns pentru Q1 și primul răspuns pentru Q4. Timpul total obținut pentru aceste trasee este de 6 minute.
Q1 Q4 Q5 dacă utilizatorul alege al doilea răspuns pentru întrebarea Q1 și apoi al doilea răspuns pentru întrebarea Q4. Timpul obținut pentru acest traseu este de 7 minute.
Q1 Q5 dacă utilizatorul alege al treilea răspuns pentru întrebarea Q1. Timpul obținut este de 4 minute.

Prin urmare, timpul minim de finalizare al chestionarului este de 4 minute.

chestionar.in

5
2 5 3 2 4 5
3 3 2 3 3
1 1 2 0 0
3 5 2 3 5
2 2 2 0 0
2 3
3 2 1 1

chestionar.out

Explicație

Traseul cel mai format din 3 răspunsuri. Utilizatorul începe cu întrebarea 1, la care alege răspunsul 2 și este trimis către întrebarea Q4. La întrebarea Q4 alege răspunsul 1 și ajunge la întrebarea Q3. Similar, alege răspunsul 1 și se termină chestionarul. Prin urmare traseul abordat este Q1 Q4 Q3. Pentru a nu se depăși limita de T=3 minute se pot elimina fie întrebările Q1 și Q3 (rămânem cu exact 3 minute, relevanța 5), fie întrebarea Q4 (rămânem cu exact 3 minute, relevanță totală 6). Așadar, soluția este cea din urmă, eliminarea întrebării 4.

ID	#810	Autor	Catrina Mirela
Set	Olimpiada Locală de Informatică 2025, Brașov, clasa a XI-a	Adăugată de	Alexis Alexis lexington
Capitol	Clasa a IX-a/Probleme avansate/Probleme diverse
Licență	© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate. Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor. Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.

Indicații oficiale de rezolvare a problemei

Lorem ipsum, dolor sit amet consectetur adipisicing elit. Aperiam rem vel architecto dolore, nulla laboriosam atque laudantium sint commodi in molestiae excepturi dicta inventore eum, quos porro illum ratione ea! Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

#include <bits/stdc++.h>

    using namespace std;

    int main() {
        int n;
        cin >> n;
        cout << n * n << endl;
        return 0;
    }

Lorem:

Subtitle

Lorem:

Pentru a vizualiza indicațiile problemei, te rugăm să te autentifici.

Autentifică-te

Indicații oficiale de rezolvare a problemei

#include <bits/stdc++.h>

    using namespace std;

    int main() {
        int n;
        cin >> n;
        cout << n * n << endl;
        return 0;
    }

Lorem:

Subtitle

Lorem:

Pentru a vizualiza rezolvarea problemei, te rugăm să te autentifici.

Autentifică-te

Soluții trimise la problema Chestionar

Soluții trimise	0
Soluții de 100 de puncte	0
Soluții de luna aceasta La fel de multe ca luna trecută.	0 +0
Rata de succes Rata dintre numărul de persoane care au obținut 100 de puncte și numărul total de persoane care au încercat problema.	N/A

Autentifică-te pentru a vedea soluțiile tale.

Autentifică-te

Toate soluțiile tale le găsești aici. Găsești toate detaliile evaluării mai târziu, precum punctaje și sfaturi primite.
Poți să editezi soluțiile tale și să le retrimiți. Reia mai târziu de unde ai rămas, pentru că poți modifica soluții și să le reevaluezi.
Profesorii pot să vadă soluțiile tale și să îți trimită sugestii. Astfel, îți este mai ușor să înveți informatica, primind sfaturi bune chiar de la școală.

Ultimele soluții trimise 0

10000000	1000000	1000	10	10000
100000	10	10000000	1000	10000
10000	100000	10	1000	100000
100000	100000	1000	100000	1000
10	10000000	1000000	10000000	10
100000	100	100	100000	100000
100	1000	10000	1000000	10
100000	100	10000000	10	10000000
1000	100	10	10	100000
1000	100	10000000	100	10000000
Tabelul se actualizează în timp real. ?? / ??

Căutare probleme sau lecții	`/`
Primul rezultat	`Enter`
Rulează codul	`Ctrl + Enter`
Meniu shortcuturi	`?`
Ieși din meniul curent	`Esc`

Bacalaureat și admiteri

Olimpiade și concursuri

Rezolvă probleme

Materia de olimpiadă

Problema Chestionar

Cerință

Date de intrare

Date de ieșire

Restricții și precizări

Exemple

chestionar.in

chestionar.out

Explicație

chestionar.in

chestionar.out

Explicație

Indicații oficiale de rezolvare a problemei

Subtitle

Indicații oficiale de rezolvare a problemei

Subtitle

Soluții trimise la problema Chestionar

Statistici

Autentifică-te pentru a vedea soluțiile tale.

Ultimele soluții trimise 0

Comentarii 0

Autentifică-te pentru a putea comenta.

Prelucrare text

Testare cod

InfoAs AI

Începe să scrii…

Bacalaureat și admiteri

Olimpiade și concursuri

Rezolvă probleme

Materia de olimpiadă

Problema Chestionar

Cerință

Date de intrare

Date de ieșire

Restricții și precizări

Exemple

chestionar.in

chestionar.out

Explicație

chestionar.in

chestionar.out

Explicație

Indicații oficiale de rezolvare a problemei

Subtitle

Indicații oficiale de rezolvare a problemei

Subtitle

Soluții trimise la problema Chestionar

Statistici

Autentifică-te pentru a vedea soluțiile tale.

Ultimele soluții trimise 0

Comentarii 0

Autentifică-te pentru a putea comenta.

Prelucrare text

Testare cod

InfoAs AI

Setări

Dispunere

Alte setări

Utilizăm Cookies

Shortcuturi