| Fișierul intrare/ieșire | ctrlnode.in, ctrlnode.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | David Demetriad | Adăugată de |
David Demetriad
•
demetriad-dagpag
|
| Timp de execuție pe test | 0.5 sec | Limită de memorie | 65536 KB |
| Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Control Node 2
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:
https://en.wikipedia.org/wiki/Ansible_(software)
Modul de lucru cu serverele este reprezentat de un inventar ( o listă de servere grupate după diferite criterii cum ar fi rețeaua de care aparțin conform sistemului IPv6 sau scopul / tipul lor: web, database etc.). Formatul de completare al acestor fișiere este în felul următor:
[nume_server]
Grupa1/ server1
Grup2/ server2
...
Asta înseamnă că o grupă poate avea orice nume format din litere și cifre, iar aceasta să aibă în subordine atât mai multe grupe de servere, cât și servere individuale descrise prin IP-ul lor ( eventual descriindu-se și un alias, adică un locțiitor pentru adresa sa ). În final, mai există grupa “all” ce include fiecare altă subgrupa și astfel toate serverele. În problema de față notațiile vor fi simplificate. Mai precis serverele vor apărea sub forma adresei lor IPv6 ( așa cum vom explica mai jos ), iar grupele vor apărea după următorul format: “group
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ă:
y1 : y2 : y3 : y4 : y5 : y6 : y7 : y8
Fiecare element yi ( 0 < i <= 8 ) este format din 4 caractere hexazecimale, fie ele ‘x1x2x3x4’ , 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 y1:y2:y3:y4 reprezintă identificatorul de rețea din care face parte serverul curent, în vreme ce y5:y6:y7:y8 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 —> y1 : y2 : y3 : y4 : y5 : y6 : y7 : y8
B —> z1 : z2 : z3 : z4 : z5 : z6 : z7 : z8
A este mai mic decât B dacă există un i ( 0 < i <= 8 ) , astfel încât ( z1 = y1, z2 = y2, ..., zi-1 = yi-1 și yi < zi). Î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.
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ță.
Date de intrare
Fișierul de intrare ctrlnode.in va fi compus în felul următor:
[group *]
Entity1
Entity2
....
Entityk (k <= 20)
....
....
#######
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.
Date de ieșire
În fișierul de ieșire ctrlnode.out va conține în funcție de cerință următoarele: 1. IP-urile ( de tipul IPv6 ) în ordine lexicografică unele sub altele, afișate în același format în care au fost citite. 2. Rețeaua cu cele mai multe noduri, aflate în subordinea directă sau indirectă a grupei G. ( primele 4 numere hexazecimale din IP separate prin caracterul ‘:’ ). În cazul în care există mai multe rețele de acest fel se va afișa rețeaua cu numărul cel mai mic de ordine. (lexicografic).
Restricții
- N, M ≤ 106
- 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 ≤ 104 .
- 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
Exemplu
| ctrlnode.in | ctrlnode.out |
|---|---|
| [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 |
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.
