[TEMA] Text de lungime maxima - eliminare cuvinte a.i. fiecare cuvant sa inceapa cu ultima litera a cuvantului precedent

Problema de la OJI 2009 cls X - deci nu trebuie sa ne ducem cu materia prea departe pentru rezolvare

Cerinţă
Pentru un text dat, se cere să se afişeze numărul de cuvinte din text, apoi numărul minim de cuvinte ce pot fi eliminate astfel încât în textul rămas orice cuvânt (cu excepţia ultimului) să se termine cu aceeaşi literă cu care începe cuvântul următor, iar în final să se afişeze cuvintele din text rămase după eliminare, fiecare cuvant fiind afişat pe câte o linie.
Date de intrare
Fişierul text.in conţine un text scris pe mai multe linii. Pe fiecare linie se află cuvinte formate din litere mici ale alfabetului latin. Cuvintele sunt despărţite între ele prin exact câte un spaţiu.
Date de iesire
Fişierul text.out va conţine pe primele doua linii două numerele x şi y, unde x va fi numărul de cuvinte din text, iar y numărul minim de cuvinte ce trebuie eliminate. Pe liniile următoare se vor afişa, în ordine, cuvintele rămase după eliminarea celor y cuvinte, câte un cuvant pe o linie.
Restricţii şi precizări
• Numărul de cuvinte din text este maximum 20000.
• Lungimea maximă a unui cuvânt este 20.
• Fiecare linie de text din fişierul de intrare are cel mult 200 de caractere.
• În fişier pot exista rânduri goale.

Exemplu
text.in text.out Explicaţii
pentru ca nu are
timp ion spune ca nu urmareste nici
emisiuni interesante si evident nici altfel
de
emisiuni


19
13
ion
nu
urmareste
emisiuni
interesante
evident Din întregul text care este format din 19 cuvinte se elimină 13 cuvinte şi se obţin, în ordine, cuvintele: ion, nu, urmareste, emisiuni, interesante,
evident
Timp maxim de executare/test : 0.1 sec
Total memorie disponibilă : 2 MB (din care 1 MB pentru stivă)
Dimensiune maximă a sursei: 5 KB

Sa elimine cat mai putine cuvinte adica sa se determine cea mai lunga secventa de cuvinte care incep cu ultima litera a celuilalt.Cum as putea sa scot aceasta secventa?Idei mai simple?daca nu sunt idei mai simple,unde as putea stoca cuvintele inafara de liste?matrice de caractere?

Pot folosi strtok ptr a numara cuvintele de pe o linie,dar cum fac sa le numar de ep toate liniile?getline?

Edited by VladBtz, 28 February 2015 - 17:52.

Titlu tembel: "text". Ti-am pus un titlu mai reprezentativ. Invata sa iti sintetizezi problema intr-un titlu: asta arata ca ai reusit sa intelegi cerinta. Sa nu se mai repete.

 OriginalCopy, on 28 februarie 2015 - 17:37, said:

ok,acum sugestii?

Pentru un inceput creaza un array cu fiecare cuvant indexat si de fiecare data cand vrei sa faci referire la un cuvant, folosesti indexul din acel array. Nu vei mai avea de-a face cu stringuri, ci doar cu numere de acum inainte.

Mai creaza si doua array-uri de marime 26 (sau cate litere va avea alfabetul pe care il vei folosi).

In primul array vei salva o lista (probabil tot array) cu cuvintele (indecsii din array-ul mare cu toate cuvintele din primul paragraf, dupa cum am spus, vei lucra doar cu indecsi din acel array - nu cu stringuri) care incep cu litera respectiva.

In al doilea array vei salva o lista cu cuvintele care se termina cu litera respectiva (0 inseamna 'a', 1 = 'b', s.a.m.d.).

Revino cu codul care face acest aranjament si cu propriile tale idei despre cum ai putea proceda.

Nota: poti construi aceste array-uri inca din timpul citirii datelor. Probabil vei mai putea optimiza (nu citirea, aia e oricum O(n), ci codul pe care va urma sa il scrii pentru rezolvarea problemei insesi) stocastic si construind doua histograme pentru inceputurile si sfarsiturile de cuvinte.

Edited by OriginalCopy, 28 February 2015 - 18:14.

fara liste si array-uri ,am si specificat ca e vorba de cls X .

 VladBtz, on 28 februarie 2015 - 18:05, said:

Nu cunosc programa din scolile romanesti, dar problema nu poate fi rezolvata fara array-uri (int wordList[10])

Edited by OriginalCopy, 28 February 2015 - 18:07.

 VladBtz, on 28 februarie 2015 - 18:05, said:

Pana in a Xa (nu sunt sigur daca in a IX-a sau a X-a) sigur se studiaza array-uri. Si in alta ordine de idei, cum de lucrezi cu siruri de caractere fara array-uri?

Edited by Gady_paul, 28 February 2015 - 18:37.

 Gady_paul, on 28 februarie 2015 - 18:36, said:

Cred ca mai degraba nu stia ca alea se numesc array-uri.

prin arrayuri ce voiai sa spui mai exact?



cred ca as intelege mai bine daca m-as uita pe codu comisiei,dar nu e decat varianta .pas .Imi poate traduce cineva din Pascal in C/C++?

http://www.girlshare.ro/34508130.8

Edited by VladBtz, 28 February 2015 - 23:11.

Eu efectiv nu inteleg limitarea unui elev la materia studiată. Dacă vreau sa realizez un sablon pentru o functie, nu am voie?! Sau o clasa?! Să tratez excepții?

Nu am participat la nici o olimpiada de informatica in liceu, dar pe zi ce trece imi pare din ce in ce mai puțin rău. Și cu toate astea urmez o facultate de profil...

Inițial mi-a părut rău că nu am participat la OJI-uri, dar.... incep să-mi schimb părerea.

 VladBtz, on 28 februarie 2015 - 23:03, said:

Incerc eu sa-l "traduc" in C++, dar sa vad daca-mi iese...e scris urat rau de tot codul.

ok,sa postezi traducerea aici ,poate o sa iti scape ceva

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
using namespace std;
string copiaza(string str, int stanga, int dreapta)
{
	string rezultat;
	for (int i = stanga; i <= dreapta; i++)
		rezultat.push_back(str[i]);
	return rezultat;
}
void citire(ifstream& fisier, vector<string>& cuvinte)
{
	string linie;
	int i;
	while (getline(fisier, linie))
	{
		if (linie == " ")
			continue;
		while (linie[0] == ' ')
			linie.erase(linie.begin());
		while (linie[linie.size() - 1] == ' ')
			linie.erase(linie.size() - 1);
		i = linie.find(' ');
		while (i > 0)
		{
			cuvinte.push_back(copiaza(linie, 0, i - 1));
			linie.erase(linie.begin(), linie.begin() + i + 1);
			i = linie.find(' ');
		}
		cuvinte.push_back(linie);
	}
}
void dinamica(vector<string>& cuvinte, vector<int>& l, vector<int>& p,
			  vector<int>& lmax, vector<int>& pmax, int *lsol, int *psol)
{
	int i;
	char litera;
	for (i = 0; i < cuvinte.size(); i++)
	{
		litera = cuvinte[i][0];
		l[i] = lmax[litera - 'a'] + 1;
		p[i] = pmax[litera - 'a'];
		litera = cuvinte[i][cuvinte[i].size() - 1];
		if (l[i] > lmax[litera - 'a'])
		{
			lmax[litera - 'a'] = l[i];
			pmax[litera - 'a'] = i;
		}
	}
	*lsol = 0;
	for (i = 'a'; i <= 'z'; i++)
		if (lmax[i - 'a'] > *lsol)
		{
			*lsol = lmax[i - 'a'];
			*psol = pmax[i - 'a'];
		}
}
void scriere(ofstream& fisier, vector<string>& cuvinte, vector<int>& l,
			 vector<int>& p, int lsol, int psol)
{
	fisier << cuvinte.size() << " " << cuvinte.size() - lsol << "\n";
	int i = psol;
	while (p[i] != 0)
	{
		l[p[i]] = i;
		i = p[i];
	}
	while(i != psol)
	{
		fisier << cuvinte[i] << " ";
		i = l[i];
	}
	fisier << cuvinte[psol] << "\n";
}
int main(void)
{
	ifstream fisierInput("text.in", ifstream::in);
	ofstream fisierOutput("text.out", ofstream::out);
	vector<string> cuvinte;
	vector<int> l, p, lmax, pmax;
	int lsol = 0, psol = 0;
	for (int i = 'a'; i <= 'z'; i++)
	{
		lmax.push_back(0);
		pmax.push_back(0);
	}
	citire(fisierInput, cuvinte);
	for (int i = 0; i < cuvinte.size(); i++)
	{
		l.push_back(0);
		p.push_back(0);
	}
	dinamica(cuvinte, l, p, lmax, pmax, &lsol, &psol);
	scriere(fisierOutput, cuvinte, l, p, lsol, psol);
	fisierInput.close();
	fisierOutput.close();
	return 0;
}

Unele variabile inca au denumiri tampite...asa erau si in pascal si nu le-am modificat ca sa nu le incurc, oricum n-as fi stiut ce nume sa le pun ca nu prea am inteles algoritmul.

 VladBtz, on 28 februarie 2015 - 23:03, said:

Ti-am dat si exemplu, trebuie sa inveti sa citesti mai bine

 OriginalCopy, on 28 februarie 2015 - 18:07, said:

 EnachescuAlin, on 01 martie 2015 - 02:12, said:

In rest ai tradus codul mot-a-mot?Si partea cu .push_back asa era si in pascal?

Imi da eroare direct cand dau run.la functia string copiaza string nu se face albastru in codeblocks .

Edited by VladBtz, 01 March 2015 - 11:36.

La mine pe linux functioneaza. Cum sa fie push_back in pascal? Incearca sa compilez cu -std=c++11. Zi si tu ce eroare iti da.

http://www.girlshare.ro/34513494.4


si are marimea 4Kb


iti functioneaza in sensul ca ai bagat cuvintel;e si ti-a dat rasp corect?

Edited by VladBtz, 01 March 2015 - 18:47.

 VladBtz, on 01 martie 2015 - 18:46, said:

Da! Cel mai probabil cred ca n-ai crea fisierul text.in.