Pe vremea maurilor, transmiterea unor mesaje codificate între două persoane se făcea folosind un cifru numit nod. Cele două persoane alegeau în secret o poveste. Aceasta era scrisă într-o carte folosind litere mici și mari ale alfabetului englez, pe P pagini, numerotate de la 1 la P, fiecare conținând exact R rânduri, numerotate în cadrul fiecărei pagini de la 1 la R, iar fiecare rând fiind format din exact C cuvinte, numerotate în cadrul fiecărui rând de la 1 la C.
Un cuvânt al mesajului de transmis era codificat prin poziția sa în povestea aleasă de cei doi, folosind trei numere scrise cu cifre romane, ce indicau în ordine: numărul paginii, numărul rândului în cadrul paginii, respectiv al cuvântului în cadrul rândului.
Mesajul astfel codificat era scris pe trei linii. Pe prima linie erau scrise numerele paginilor, pe a doua linie numerele rândurilor, iar pe a treia linie erau scrise numerele de ordine ale cuvintelor.
Presupunem că mesajul este format din primul cuvânt de pe al cincilea rând al celei de a doua pagini și din al patrulea cuvânt de pe rândul al doilea al primei pagini. Mesajul putea fi transmis pe trei linii în modul următor:
II I(numerele paginilor)V II(numerele rândurilor)I IV(numerele cuvintelor)
Cifrele romane sunt scrise cu majusculele M, D, C, L, X, V, I, iar valorile corespunzătoare lor sunt în ordine: 1000, 500, 100, 50, 10, 5, 1. Valoarea unui număr scris cu cifre romane se calculează parcurgând de la stânga la dreapta cifrele numărului astfel:
- cifra curentă se adună la valoarea obținută până în acel moment, dacă cifra următoare este mai mică sau egală cu ea;
- cifra curentă se scade din valoarea obținută până în acel moment, dacă cifra următoare este mai mare decât ea;
- ultima cifră se adună întotdeauna la valoarea obținută până în acel moment.
De exemplu pentru numărul MCDXLVI scris cu cifre romane, se obține valoarea 1446 în sistem zecimal, astfel: 1000-100+500-10+50+5+1, iar pentru numărul XXI scris cu cifre romane se obține valoarea 21 în sistemul zecimal astfel: 10+10+1.
Cerința
Cunoscându-se textul poveștii ales de cei doi și mesajul codificat de ei scrieți un program care rezolvă următoarele două cerințe:
a) Rescrie mesajul codificat folosind scrierea cu cifre din sistemul zecimal.
b) Afișează toate cuvintele mesajului decodificat în ordinea în care acestea apar în poveste.
Date de intrare
Fişierul nod.in conține:
- pe prima linie numărul
1, dacă se cere rezolvarea doar a cerinței a) sau numărul2, dacă se cere rezolvarea cerinței b); - pe următoarele trei linii mesajul codificat după regulile descrise în enunț;
- dacă primul număr din fișier este
2atunci a cincea linie conține trei numere naturaleP,RșiC, separate între ele prin câte un spaţiu, cu semnificaţia din enunţ; - pe următoarele
PxRlinii este scris textul poveștii, fiecare linie conținândCcuvinte, separate prin câte un spațiu.
Date de ieșire
Dacă primul număr din fișierul de intrare este 1 atunci fişierul nod.out va conține, în aceeași ordine, pe trei linii, numerele din mesajul codificat scrise în sistem zecimal. Numerele vor fi despărțite în cadrul liniilor prin câte un spațiu.
Dacă primul număr din fișierul de intrare este 2 atunci fişierul nod.out va conține pe o singură linie cuvintele mesajului decodificat, în ordinea din poveste. Cuvintele vor fi separate prin câte un spațiu.
Restricții și precizări
1 ≤ P ≤ 2000;1 ≤ R ≤ 25;1 ≤ C ≤ 151 ≤lungimea unui cuvânt din poveste≤ 12- orice număr scris cu cifre romane are cel mult
10majuscule - mesajul decodificat va conține cel mult
20de cuvinte
Exemplul 1
nod.in
1 III II I II V II VI I IV
nod.out
3 2 1 2 5 2 6 1 4
Explicație
Testul de intrare indică rezolvarea primei cerințe, adică cerința a).
Numerele de pe fiecare linie sunt scrise în aceeași ordine, în sistemul zecimal.
Exemplul 2
nod.in
2 I III II I II I I II I II I II II II IV 3 2 4 La Olimpiada problemele pot avea una sau mai multe cerinte Pentru unele probleme comisia poate decide ca prima cerinta sa fie evaluata si separat
nod.out
La Olimpiada comisia decide prima
Explicație
Testul de intrare indică rezolvarea celei de a doua cerințe, adică cerința b). Cuvintele identificate în poveste sunt:
La – prin (I,I,I)
prima – prin (III,I,II)
comisia – prin (II,II,II)
Olimpiada – prin (I,I,II)
decide – prin (II,II,IV)
Cuvintele mesajului decodificat, în ordinea din poveste, sunt:
La Olimpiada comisia decide prima
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Nod:
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("nod.in");
ofstream g("nod.out");
struct cuvinte{
int pag, rand, cuv;
};
char sir[600]="", numar[11]="",*p, sep[]=" ";
int n,k,P,R,C;
cuvinte t[26];
void extrage_nr();
int calculeaza(int x);
void transforma(char numar[11],int k);
void ordonare();
void cauta_cuvinte();
void afisare();
int main()
{
f>>k; f.get();
extrage_nr();
if(k==1)
{
for(int d=1;d<=3;d++)
for(int i=1; i<=n;i++)
{
switch (d)
{
case 1:g<<t[i].pag; break;
case 2:g<<t[i].rand; break;
case 3:g<<t[i].cuv; break;
}
if(i<n)
g<<" ";
else
g<<'\n';
}
}
else
{
ordonare();
cauta_cuvinte();
}
f.close();g.close();
return 0;
}
void extrage_nr()
{
int i;
for(i=1;i<=3;i++)
{n=0;
f.getline(sir,600);//cout<<sir<<endl;
p=strtok(sir,sep);
while (p)
{
n++;
strcpy(numar, p);
transforma(numar,i);
p=strtok(NULL,sep);
}
}
}
void transforma(char numar[11],int d)
{
int i,l,cif1,cif2,nr=0;
l=strlen(numar);
for(i=0;i<l-1;i++)
{
cif1=calculeaza(numar[i]);
cif2=calculeaza(numar[i+1]);
if(cif1<cif2)
nr=nr-cif1;
else
nr=nr+cif1;
}
if(l==1)
nr=calculeaza(numar[i]);
else
nr=nr+cif2;
switch (d)
{
case 1:t[n].pag=nr;break;
case 2:t[n].rand=nr;break;
case 3:t[n].cuv=nr;break;
}
}
int calculeaza(int x)
{
int cif;
switch (x)
{
case 'M':cif=1000;break;
case 'D':cif=500;break;
case 'C':cif=100;break;
case 'L':cif=50;break;
case 'X':cif=10;break;
case 'V':cif=5; break;
case 'I':cif=1;break;
}
return cif;
}
void ordonare()
{
int i,sw; cuvinte aux;
do
{
sw=1;
for(i=1;i<n;i++)
if(t[i].pag>t[i+1].pag || (t[i].pag==t[i+1].pag && t[i].rand>t[i+1].rand) || (t[i].pag==t[i+1].pag && t[i].rand==t[i+1].rand && t[i].cuv>t[i+1].cuv))
{
aux=t[i];
t[i]=t[i+1];
t[i+1]=aux;
sw=0;
}
}while (sw==0);
}
void cauta_cuvinte()
{ int i=1,nrct=0, nrc=0;
char *p;
f>>P>>R>>C;f.get();
nrct=(t[1].pag-1)*R*C+(t[1].rand-1)*C+ t[1].cuv;
while(f.getline(sir,600) && i<=n)
{
p=strtok(sir,sep);
while (p)
{
nrc++;
if(nrc==nrct)
{
if (i<n)
g<<p<<" ";
else
g<<p;
i++;
nrct=(t[i].pag-1)*R*C+(t[i].rand-1)*C+ t[i].cuv;
}
p=strtok(NULL,sep);
}
}
}
void afisare()
{
int i;
for(i=1;i<=n;i++)
{
g<<t[i].pag<<" "<<t[i].rand<<" "<<t[i].cuv<<'\n';
}
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1205 Nod
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1205 Nod de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!