Diferențe pentru problema/ctrlnode între reviziile #3 si #30

== include(page="template/taskheader" task_id="ctrlnode") ==

_Aceasta problema este varianta originală a problemei controlnode, dată la Testarea IQ-Academy Clasa a 8-a, anul 2023_
 

Ansible reprezintă o serie de utilitare software ce pot fi folosite în stil programatic, implementând cod, ce are ca scop următoarele dar nu numai: managementul serverelor prin configurarea și aprovizionarea acestora cu pachetele și programelor informatice necesare pentru o cât mai bună comunicare între acestea și nodul de control ( serverul de pe care acțiunea de coordonare este inițiată ).
Mai multe detalii aici:

Grupele sunt despărțite între ele prin câte o linie liberă, iar după ultima grupă va exista o linie formată din caractere “#” , cel puțin 3, cel mult 20, ceea ce indică finalul inventarului. Fiecare entiate – fie ea grupă ori server IP, va fi scrisă pe o singură linie, făcându-se astfel distincția între fiecare dintre ele. În final, vor mai fi prezente în fișier un de caractere și un număr. Primul dintre ele reprezintă o grupă, fie ea G. Prima cerință constă în afișarea tuturor serverelor aflate în subordinea acelei grupe, direct sau indirect, în ordine lexicografică. Ultima linie va conține unul din numerele 1 și 2, reprezentând numerele de ordine pentru cele 2 cerințe ale problemei.
Un IPv6 are următoarea structură:

	y[~1~] : y[~2~] : y[~3~] : y[~4~] : y[~5~] : y[~6~] : y[~7~] : y[~8~]
Fiecare element yi    ( 0 < i <= 8 ) este format din 4 caractere hexazecimale, fie ele ‘x[~1~]x[~2~]x[~3~]x[~4~]’ , unde xi  este orice valoare în mulțimea 0 - 9 și a – f (unde a – f reprezintă primele 6 litere mici din alfabetul latin și reprezintă valorile 10-15 din baza 16 – hexazecimală) . Astfel, șirul y[~1~]:y[~2~]:y[~3~]:y[~4~] reprezintă identificatorul de rețea din care face parte serverul curent, în vreme ce y[~5~]:y[~6~]:y[~7~]:y[~8~] reprezintă numărul de ordine al serverului curent în cadrul rețelei sale. Ordinea lexicografică a două servere este definită în felul următor: Fie două servere ( să le zicem A și B ) având IPv6-urile:

A —> y[~1~] : y[~2~] : y[~3~] : y[~4~] : y[~5~] : y[~6~] : y[~7~] : y[~8~]
B —> z[~1~] : z[~2~] : z[~3~] : z[~4~] : z[~5~] : z[~6~] : z[~7~] : z[~8~]

A este mai mic decât B dacă există un i ( 0 < i <= 8 ) , astfel încât ( z[~1~] = y[~1~], z[~2~] = y[~2~], ..., z[~i-1~] = y[~i-1~] și y[~i~] < z[~i~]). În acest sens, yi este mai mic decât zi dacă și numai dacă numărul hexazecimal format din caracterele ce îl compun pe yi este mai mic decât numărul hexazecimal format din caracterele ce îl compun pe zi, ceea ce e înseamnă că reprezentarea zecimală în baza 10 a lui yi să fie mai mică decât cea a lui zi.

A este mai mic decât B dacă există un i ( 0 < i <= 8 ) , astfel încât ( z[~1~] = y[~1~], z[~2~] = y[~2~], ..., z[~i-1~] = y[~i-1~] și y[~i~] < z[~i~]). În acest sens, y[~i~] este mai mic decât z[~i~] dacă și numai dacă numărul hexazecimal format din caracterele ce îl compun pe yi este mai mic decât numărul hexazecimal format din caracterele ce îl compun pe z[~i~], ceea ce e înseamnă că reprezentarea zecimală în baza 10 a lui y[~i~] să fie mai mică decât cea a lui zi.

h2. Cerință

    1. Să se afișeze în ordinea lexicografică a IPv6-urilor toate serverele aflate în subordinea directă sau indirectă lui G.
    2. Dintre serverele din subordinea lui G să se afișeze care este rețeaua care are cele mai multe servere în componență.

1. Să se afișeze în ordinea lexicografică a IPv6-urilor toate serverele aflate în subordinea directă sau indirectă lui G.
 
2. Dintre serverele din subordinea lui G să se afișeze care este rețeaua care are cele mai multe servere în componență.

h2. Date de intrare
Fișierul de intrare $ctrlnode.in$ va fi compus în felul următor:

[group*]

[group *]

Entity1
Entity2
....
Entityk   (k <= 20)

[...

....

....
#######

group* | all

group * | all

c

Unde “*” poate fi orice număr natural mai mic decât 1 milion, iar “Entity*” poate fi o grupă de servere sau în sine un server. În final c poate fi 1 sau 2, în funcție de cerința de rezolvat.

Unde “ * ” poate fi orice număr natural mai mic decât 1 milion, iar “Entity *” poate fi o grupă de servere sau în sine un server. În final c poate fi 1 sau 2, în funcție de cerința de rezolvat.

h2. Date de ieșire

h2. Restricții

* $... ≤ ... ≤ ...$

 
*  N, M ≤ 10[^6^]
*  K ≤ 20
*  Pentru teste în valoare de 58% cerința va fi 1)
*  Pentru teste în valoare de 42% cerința va fi 2)
*  Dintre acestea, pentru teste în valoare de 45% G = ‘all’. Pentru aceste teste, grupa ‘all’ va fi explicit definită, ceea ce înseamnă că va fi mai ușor a se detecta relațiile de subordine între entități.
*  Pentru restul de 55% această definire nu va fi efectuată, rămânând la latitudinea concurentului a scrie un program ce va organiza serverele și grupele corect.
*  Pentru 76% dintre teste N, M ≤ 10[^4^] .
*  Se garantează că aceeași grupă nu apare în 2 locuri diferite în fișierul de intrare ( nu apare ca fiind descris , adica intre paranteze patrate , de mai mult de o singura data , dar nici nu apare subordonat direct de mai mult de o singura data )
*  IP-urile de asemenea POT aparea de mai mult de o data in fisierul de intrare

h2. Exemplu
table(example).
|_. ctrlnode.in |_. ctrlnode.out |

| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.

|  [all]
group1
group2
group3
[group1]
2459:ab46:0023:1111:2433:2354:7686:5670
2459:ab46:0023:1111:2433:2754:7686:5670
[group2]
2459:ab46:0023:1111:3243:2353:8888:0000
2459:ab46:0023:1111:3467:3563:5555:1111
ffaa:2334:2343:9913:6845:4302:2aaa:bbbb
ffaa:2334:2343:9913:4363:4253:2451:cccc
[group3]
1111:2222:3333:4444:5555:6666:7777:aaaa
#######
all
1
| 1111:2222:3333:4444:5555:6666:7777:aaaa
2459:ab46:0023:1111:2433:2354:7686:5670
2459:ab46:0023:1111:2433:2754:7686:5670
2459:ab46:0023:1111:3243:2353:8888:0000
2459:ab46:0023:1111:3467:3563:5555:1111
ffaa:2334:2343:9913:4363:4253:2451:cccc
ffaa:2334:2343:9913:6845:4302:2aaa:bbbb

|

| [all]
group1
group2
group3
[group1]
2459:ab46:0023:1111:2433:2354:7686:5670
2459:ab46:0023:1111:2433:2754:7686:5670
[group2]
2459:ab46:0023:1111:3243:2353:8888:0000
2459:ab46:0023:1111:3467:3563:5555:1111
ffaa:2334:2343:9913:6845.4302:2aaa:bbbb
ffaa:2334:2343:9913:4363:4253:2451:cccc
[group3]
1111:2222:3333:4444:5555:6666:7777:aaaa
#######
all
2
| 2459:ab46:0023:1111
|
| [group1]
4525:3243:8941:afc4:2345:1113:3245:aaaa
5376:2354:1111:2345:abcd:efab:1589:0234
7823:1324:1113:2345:1111:3445:2343:1345
[group3]
1456:2456:2457:1345:1104:1459:8888:0000
group2
[group2]
0000:0000:1111:2222:3333:4444:5555:6666
[group4]
group1
8881:3435:1245:1245:0001:0002:0003:3566
#######
group4
1
| 4525:3243:8941:afc4:2345:1113:3245:aaaa
5376:2354:1111:2345:abcd:efab:1589:0234
7823:1324:1113:2345:1111:3445:2343:1345
8881:3435:1245:1245:0001:0002:0003:3566
|

h3. Explicație

...

Primul exemplu: Aici extragem practic toate serverele prezente, deoarece prin definitie toate serverele apartin grupei “all”. Sortate lexicografic rezulta output-ul prezentat.
 
Al doilea exemplu: Aceeasi structura cu primul exemplu. Remarcam ca cea mai prezenta retea este 2459:ab46:0023:1111  (apare de 4 ori)
 
Al treilea exemplu: Dorim sa extragem toate serverele din grupa a 4-a. Observam ca grupa ‘all’ nu este definita aici. Deci ce este de facut ? Observam ca grupele care nu sunt subordonate altora, fiind cele mai generale sunt grupa a 4-a si grupa a 3-a. Cum se intereseaza doar grupa a 4-a, vom explora doar componentele acesteia. Printre altele aceasta grupa are ca subordonat direct un IP ( ce este extras in scopul de a fi afisat). De asemenea, grupa 4 mai contine si grupa 1. In grupa 1 gasim alte 3 servere. Extragem si Ip-urile acestora. In total, cele 4 servere sunt afisate in ordine crescatoare, acesta constituind si rezultatul final.

== include(page="template/taskfooter" task_id="ctrlnode") ==