comment_impartire.txt

Constrangeri:
	* timp de executie: 1 sec

Explicatie:
Rezolvam problema prin metoda programarii dinamice. Odata impartit fisierul in cuvinte,
pentru fiecare grup de cuvinte consecutive calculam penalitatea p asociata unei linii
care le contine.

	* l[i] = lungimea cuvantului i
	* p[i][j] = t[i][j] * t[i][j], daca t[i][j] >= 0
				infinit, daca t[i][j] < 0
				, unde
					* width = lungimea maxima unei linii
					* t[i][j] = width - (l[i] + ... + l[j]) - (j - i)

Calcului lui p se poate face in O(N^2), pastrand sumele partiale ale lungimilor cuvintelor.

Un pas suplimentar este necesar pentru tratarea ultimei linii a paragrafului. Solutia este
sa fortam la 0 valorile p[i][j] pentru intervalele de cuvinte i..j ce ar putea incapea
pe ultima linie.

Avand aceste penalitati calculate, putem gasi impartirea optima in linii. Pentru aceasta,
definim c[i] ca fiind costul minim ce poate fi obtinut pentru cuvintele de la inceputul
paragrafului pana la cuvantul i. c[i] poate fi calculat in doua variante:

	1. incercand sa punem toate cuvintele pana la i pe aceeasi linie, adica p[0][i]
	2. incercand sa impartim cuvintele 0..i in linii ce au cuvintele 0..k si o linie
	   noua, ce contine cuvintele k + 1..i. 

Pentru a putea reconstitui solutia optima, odata cu c[i] calculam si w[i], ca fiind
numarul de ordine al cuvantului de la inceputul ultimei linii in solutia partiala ce
corespunde lui c[i].

	* c[i] = min(p[0][i], min_k (c[k] + p[k + 1][i]), unde k < i)
	* w[i] = 0, daca c[i] = p[0][i]
			 k + 1, daca c[i] = min_k (c[k] + p[k + 1][i]), cu k < i

Din valorile w[i], plecand de la ultima linie putem construi inapoi solutia optima. Daca
ultima linie incepe cu cuvantul w[u], penultima linie se va termina la cuvantul w[u] - 1 si
va incepe la cuvantul w[w[u] - 1]. Aceeasi regula se aplica pana la inceputul paragrafului.

Complexitate:
	* timp: O(N^2) + O(N^2) = O(N^2)
	* memorie: O(N^2) + O(N) + O(N) = O(N^2)

Observatie:
Pentru aceasta problema exista si un algoritm mai eficient, de complexitate O(N) ca timp,
ce se foloseste de anumite caracteristici ale functiei de cost. Deoarece datele de intrare
au o dimensiune mica, algoritmul in O(N^2) este suficient.

impartire.out

1 12 23 33 44 55 67 78 88 98 109
1 11 21 34 46 58 68 79 90 104 115 126 138 149 161 172 184 194 207 216 228 238 249 262
1 7 16 23 31 39 49 57 64 72 79 87 95 105 112 120 127 137 147 157 163 172 180
1 15 29 41 57 70 80 87 97 108
1 12 27 39 52 65 76 88 101 115 131 145 159 174 185 200 212 228
1 15 29 42 54 67 81 97 111 123 137 152 163 177 189 200 211 226 242 256 269 283 296 313 328 340 354 370 382 399 411 425 436 451 465 478 493 507 519 532 545 558 570 584
1 16 29 45 59 75 90 106 119 132 148 165 181 197 213 227 242 260 275 289 303 318 332 347 364 378 396 411 426 439 452 469 484 500 516 533 549 563 578 593 604 617 633 648 664 679 692 706 722 738
1 16 31 45 60 73 84 98 110 122 137 152 166 180 194 209 224 237 250 262 275 289 304 320 333 347 360 372 384 401 410 421 436 450 466 477 493 508 524 537
1 7 15 23 30 37 46 53 60 67 74 82 90 95 102 110 117 125 133 140 148 153 160 166 172 179 187 196 202 210 218 225 232 239 245 253 259 268 272 280 287 294
1 16 30 42 57 69 84 98 112 128 142 156 171 184 200 215 232 246 261 277 292 308 323 340 356 372 389 405 420 434 450 465 478 492 509 526 541 555 569 582 597 612 627 640 654 669 684 698 714 730 744

impartire.txt

80 Lorem ipsum dolor sit amet, consectetur adipiscing elit. In ut viverra elit. Quisque ultricies lacinia magna, eu pharetra nulla porttitor in. Cras ornare blandit sodales. Ut ullamcorper tincidunt nulla, non dignissim metus viverra ut. Quisque semper tortor in mi vehicula ullamcorper. Donec eget orci sodales, sodales justo quis, ultrices dui. Aliquam diam felis, pulvinar eget massa ac, eleifend auctor nulla. Nulla nec nulla nulla. Morbi sit amet convallis nisl. Curabitur in elit sit amet diam fringilla porttitor. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Quisque pulvinar id sapien eget tempus. Praesent pellentesque facilisis leo nec iaculis. Praesent rutrum odio non augue scelerisque, non condimentum tellus placerat. Fusce vestibulum vestibulum nunc nec pulvinar.
60 In the beginning when God created the heavens and the earth, the earth was a formless void and darkness covered the face of the deep, while a wind from God swept over the face of the waters. Then God said, `Let there be light'; and there was light. And God saw that the light was good; and God separated the light from the darkness. God called the light Day, and the darkness he called Night. And there was evening and there was morning, the first day. And God said, `Let there be a dome in the midst of the waters, and let it separate the waters from the waters.' So God made the dome and separated the waters that were under the dome from the waters that were above the dome. And it was so. God called the dome Sky. And there was evening and there was morning, the second day. And God said, `Let the waters under the sky be gathered together into one place, and let the dry land appear.' And it was so. God called the dry land Earth, and the waters that were gathered together he called Seas. And God saw that it was good. Then God said, `Let the earth put forth vegetation: plants yielding seed, and fruit trees of every kind on earth that bear fruit with the seed in it.' And it was so. The earth brought forth vegetation: plants yielding seed of every kind, and trees of every kind bearing fruit with the seed in it. And God saw that it was good. And there was evening and there was morning, the third day.
50 The evening altogether passed off pleasantly to the whole family. Mrs. Bennet had seen her eldest daughter much admired by the Netherfield party. Mr. Bingley had danced with her twice, and she had been distinguished by his sisters. Jane was as much gratified by this as her mother could be, though in a quieter way. Elizabeth felt Jane's pleasure. Mary had heard herself mentioned to Miss Bingley as the most accomplished girl in the neighbourhood; and Catherine and Lydia had been fortunate enough never to be without partners, which was all that they had yet learnt to care for at a ball. They returned, therefore, in good spirits to Longbourn, the village where they lived, and of which they were the principal inhabitants. They found Mr. Bennet still up. With a book he was regardless of time; and on the present occasion he had a good deal of curiosity as to the event of an evening which had raised such splendid expectations. He had rather hoped that his wife's views on the stranger would be disappointed; but he soon found out that he had a different story to hear.
80 Wombed in sin darkness I was too, made not begotten. By them, the man with my voice and my eyes and a ghostwoman with ashes on her breath. They clasped and sundered, did the coupler's will. From before the ages He willed me and now may not will me away or ever. A _lex eterna_ stays about Him. Is that then the divine substance wherein Father and Son are consubstantial? Where is poor dear Arius to try conclusions? Warring his life long upon the contransmagnificandjewbangtantiality. Illstarred heresiarch' In a Greek watercloset he breathed his last: euthanasia. With beaded mitre and with crozier, stalled upon his throne, widower of a widowed see, with upstiffed omophorion, with clotted hinderparts.
75 The nineteenth century dislike of romanticism is the rage of Caliban not seeing his own face in a glass. The moral life of man forms part of the subject-matter of the artist, but the morality of art consists in the perfect use of an imperfect medium. No artist desires to prove anything. Even things that are true can be proved. No artist has ethical sympathies. An ethical sympathy in an artist is an unpardonable mannerism of style. No artist is ever morbid. The artist can express everything. Thought and language are to the artist instruments of an art. Vice and virtue are to the artist materials for an art. From the point of view of form, the type of all the arts is the art of the musician. From the point of view of feeling, the actor's craft is the type. All art is at once surface and symbol. Those who go beneath the surface do so at their peril. Those who read the symbol do so at their peril. It is the spectator, and not life, that art really mirrors. Diversity of opinion about a work of art shows that the work is new, complex, and vital. When critics disagree, the artist is in accord with himself. We can forgive a man for making a useful thing as long as he does not admire it. The only excuse for making a useless thing is that one admires it intensely.
80 Siddhartha had learned to trade, to use his power over people, to enjoy himself with a woman, he had learned to wear beautiful clothes, to give orders to servants, to bathe in perfumed waters. He had learned to eat tenderly and carefully prepared food, even fish, even meat and poultry, spices and sweets, and to drink wine, which causes sloth and forgetfulness. He had learned to play with dice and on a chess-board, to watch dancing girls, to have himself carried about in a sedan-chair, to sleep on a soft bed. But still he had felt different from and superior to the others; always he had watched them with some mockery, some mocking disdain, with the same disdain which a Samana constantly feels for the people of the world. When Kamaswami was ailing, when he was annoyed, when he felt insulted, when he was vexed by his worries as a merchant, Siddhartha had always watched it with mockery. Just slowly and imperceptibly, as the harvest seasons and rainy seasons passed by, his mockery had become more tired, his superiority had become more quiet. Just slowly, among his growing riches, Siddhartha had assumed something of the childlike people's ways for himself, something of their childlikeness and of their fearfulness. And yet, he envied them, envied them just the more, the more similar he became to them. He envied them for the one thing that was missing from him and that they had, the importance they were able to attach to their lives, the amount of passion in their joys and fears, the fearful but sweet happiness of being constantly in love. These people were all of the time in love with themselves, with women, with their children, with honours or money, with plans or hopes. But he did not learn this from them, this out of all things, this joy of a child and this foolishness of a child; he learned from them out of all things the unpleasant ones, which he himself despised. It happened more and more often that, in the morning after having had company the night before, he stayed in bed for a long time, felt unable to think and tired. It happened that he became angry and impatient, when Kamaswami bored him with his worries. It happened that he laughed just too loud, when he lost a game of dice. His face was still smarter and more spiritual than others, but it rarely laughed, and assumed, one after another, those features which are so often found in the faces of rich people, those features of discontent, of sickliness, of ill-humour, of sloth, of a lack of love. Slowly the disease of the soul, which rich people have, grabbed hold of him. Like a veil, like a thin mist, tiredness came over Siddhartha, slowly, getting a bit denser every day, a bit murkier every month, a bit heavier every year. As a new dress becomes old in time, loses its beautiful colour in time, gets stains, gets wrinkles, gets worn off at the seams, and starts to show threadbare spots here and there, thus Siddhartha's new life, which he had started after his separation from Govinda, had grown old, lost colour and splendour as the years passed by, was gathering wrinkles and stains, and hidden at bottom, already showing its ugliness here and there, disappointment and disgust were waiting. Siddhartha did not notice it. He only noticed that this bright and reliable voice inside of him, which had awoken in him at that time and had ever guided him in his best times, had become silent.
80 I am Basil Elton, keeper of the North Point light that my father and grandfather kept before me. Far from the shore stands the gray lighthouse, above sunken slimy rocks that are seen when the tide is low, but unseen when the tide is high. Past that beacon for a century have swept the majestic barques of the seven seas. In the days of my grandfather there were many; in the days of my father not so many; and now there are so few that I sometimes feel strangely alone, as though I were the last man on our planet. From far shores came those white-sailed argosies of old; from far Eastern shores where warm suns shine and sweet odors linger about strange gardens and gay temples. The old captains of the sea came often to my grandfather and told him of these things which in turn he told to my father, and my father told to me in the long autumn evenings when the wind howled eerily from the East. And I have read more of these things, and of many things besides, in the books men gave me when I was young and filled with wonder. But more wonderful than the lore of old men and the lore of books is the secret lore of ocean. Blue, green, gray, white or black; smooth, ruffled, or mountainous; that ocean is not silent. All my days have I watched it and listened to it, and I know it well. At first it told to me only the plain little tales of calm beaches and near ports, but with the years it grew more friendly and spoke of other things; of things more strange and more distant in space and time. Sometimes at twilight the gray vapors of the horizon have parted to grant me glimpses of the ways beyond; and sometimes at night the deep waters of the sea have grown clear and phosphorescent, to grant me glimpses of the ways beneath. And these glimpses have been as often of the ways that were and the ways that might be, as of the ways that are; for ocean is more ancient than the mountains, and freighted with the memories and the dreams of Time. Out of the South it was that the White Ship used to come when the moon was full and high in the heavens. Out of the South it would glide very smoothly and silently over the sea. And whether the sea was rough or calm, and whether the wind was friendly or adverse, it would always glide smoothly and silently, its sails distant and its long strange tiers of oars moving rhythmically. One night I espied upon the deck a man, bearded and robed, and he seemed to beckon me to embark for far unknown shores. Many times afterward I saw him under the full moon, and ever did he beckon me. Very brightly did the moon shine on the night I answered the call, and I walked out over the waters to the White Ship on a bridge of moonbeams. The man who had beckoned now spoke a welcome to me in a soft language I seemed to know well, and the hours were filled with soft songs of the oarsmen as we glided away into a mysterious South, golden with the glow of that full, mellow moon. And when the day dawned, rosy and effulgent, I beheld the green shore of far lands, bright and beautiful, and to me unknown. Up from the sea rose lordly terraces of verdure, tree-studded, and shewing here and there the gleaming white roofs and colonnades of strange temples. As we drew nearer the green shore the bearded man told me of that land, the land of Zar, where dwell all the dreams and thoughts of beauty that come to men once and then are forgotten. And when I looked upon the terraces again I saw that what he said was true, for among the sights before me were many things I had once seen through the mists beyond the horizon and in the phosphorescent depths of ocean. There too were forms and fantasies more splendid than any I had ever known; the visions of young poets who died in want before the world could learn of what they had seen and dreamed. But we did not set foot upon the sloping meadows of Zar, for it is told that he who treads them may nevermore return to his native shore.
80 Life is a well of delight; but where the rabble also drink, there all fountains are poisoned. To everything cleanly am I well disposed; but I hate to see the grinning mouths and the thirst of the unclean. They cast their eye down into the fountain: and now glanceth up to me their odious smile out of the fountain. The holy water have they poisoned with their lustfulness; and when they called their filthy dreams delight, then poisoned they also the words. Indignant becometh the flame when they put their damp hearts to the fire; the spirit itself bubbleth and smoketh when the rabble approach the fire. Mawkish and over-mellow becometh the fruit in their hands: unsteady, and withered at the top, doth their look make the fruit-tree. And many a one who hath turned away from life, hath only turned away from the rabble: he hated to share with them fountain, flame, and fruit. And many a one who hath gone into the wilderness and suffered thirst with beasts of prey, disliked only to sit at the cistern with filthy camel-drivers. And many a one who hath come along as a destroyer, and as a hailstorm to all cornfields, wanted merely to put his foot into the jaws of the rabble, and thus stop their throat. And it is not the mouthful which hath most choked me, to know that life itself requireth enmity and death and torture-crosses: -- But I asked once, and suffocated almost with my question: What? is the rabble also NECESSARY for life? Are poisoned fountains necessary, and stinking fires, and filthy dreams, and maggots in the bread of life? Not my hatred, but my loathing, gnawed hungrily at my life! Ah, ofttimes became I weary of spirit, when I found even the rabble spiritual! And on the rulers turned I my back, when I saw what they now call ruling: to traffic and bargain for power -- with the rabble! Amongst peoples of a strange language did I dwell, with stopped ears: so that the language of their trafficking might remain strange unto me, and their bargaining for power. And holding my nose, I went morosely through all yesterdays and to-days: verily, badly smell all yesterdays and to-days of the scribbling rabble! Like a cripple become deaf, and blind, and dumb -- thus have I lived long; that I might not live with the power-rabble, the scribe-rabble, and the pleasure-rabble. Toilsomely did my spirit mount stairs, and cautiously; alms of delight were its refreshment; on the staff did life creep along with the blind one. What hath happened unto me? How have I freed myself from loathing? Who hath rejuvenated mine eye? How have I flown to the height where no rabble any longer sit at the wells? Did my loathing itself create for me wings and fountain-divining powers? Verily, to the loftiest height had I to fly, to find again the well of delight! Oh, I have found it, my brethren! Here on the loftiest height bubbleth up for me the well of delight! And there is a life at whose waters none of the rabble drink with me! Almost too violently dost thou flow for me, thou fountain of delight! And often emptiest thou the goblet again, in wanting to fill it!
40 Candide, all stupefied, could not yet very well realise how he was a hero. He resolved one fine day in spring to go for a walk, marching straight before him, believing that it was a privilege of the human as well as of the animal species to make use of their legs as they pleased. He had advanced two leagues when he was overtaken by four others, heroes of six feet, who bound him and carried him to a dungeon. He was asked which he would like the best, to be whipped six-and-thirty times through all the regiment, or to receive at once twelve balls of lead in his brain. He vainly said that human will is free, and that he chose neither the one nor the other. He was forced to make a choice; he determined, in virtue of that gift of God called liberty, to run the gauntlet six-and-thirty times. He bore this twice. The regiment was composed of two thousand men; that composed for him four thousand strokes, which laid bare all his muscles and nerves, from the nape of his neck quite down to his rump. As they were going to proceed to a third whipping, Candide, able to bear no more, begged as a favour that they would be so good as to shoot him. He obtained this favour; they bandaged his eyes, and bade him kneel down. The King of the Bulgarians passed at this moment and ascertained the nature of the crime. As he had great talent, he understood from all that he learnt of Candide that he was a young metaphysician, extremely ignorant of the things of this world, and he accorded him his pardon with a clemency which will bring him praise in all the journals, and throughout all ages.
80 Strange, indeed, would be my conduct, O men of Athens, if I who, when I was ordered by the generals whom you chose to command me at Potidaea and Amphipolis and Delium, remained where they placed me, like any other man, facing death -- if now, when, as I conceive and imagine, God orders me to fulfil the philosopher's mission of searching into myself and other men, I were to desert my post through fear of death, or any other fear; that would indeed be strange, and I might justly be arraigned in court for denying the existence of the gods, if I disobeyed the oracle because I was afraid of death, fancying that I was wise when I was not wise. For the fear of death is indeed the pretence of wisdom, and not real wisdom, being a pretence of knowing the unknown; and no one knows whether death, which men in their fear apprehend to be the greatest evil, may not be the greatest good. Is not this ignorance of a disgraceful sort, the ignorance which is the conceit that a man knows what he does not know? And in this respect only I believe myself to differ from men in general, and may perhaps claim to be wiser than they are: -- that whereas I know but little of the world below, I do not suppose that I know: but I do know that injustice and disobedience to a better, whether God or man, is evil and dishonourable, and I will never fear or avoid a possible good rather than a certain evil. And therefore if you let me go now, and are not convinced by Anytus, who said that since I had been prosecuted I must be put to death; (or if not that I ought never to have been prosecuted at all); and that if I escape now, your sons will all be utterly ruined by listening to my words -- if you say to me, Socrates, this time we will not mind Anytus, and you shall be let off, but upon one condition, that you are not to enquire and speculate in this way any more, and that if you are caught doing so again you shall die; -- if this was the condition on which you let me go, I should reply: Men of Athens, I honour and love you; but I shall obey God rather than you, and while I have life and strength I shall never cease from the practice and teaching of philosophy, exhorting any one whom I meet and saying to him after my manner: You, my friend, -- a citizen of the great and mighty and wise city of Athens, -- are you not ashamed of heaping up the greatest amount of money and honour and reputation, and caring so little about wisdom and truth and the greatest improvement of the soul, which you never regard or heed at all? And if the person with whom I am arguing, says: Yes, but I do care; then I do not leave him or let him go at once; but I proceed to interrogate and examine and cross-examine him, and if I think that he has no virtue in him, but only says that he has, I reproach him with undervaluing the greater, and overvaluing the less. And I shall repeat the same words to every one whom I meet, young and old, citizen and alien, but especially to the citizens, inasmuch as they are my brethren. For know that this is the command of God; and I believe that no greater good has ever happened in the state than my service to the God. For I do nothing but go about persuading you all, old and young alike, not to take thought for your persons or your properties, but first and chiefly to care about the greatest improvement of the soul. I tell you that virtue is not given by money, but that from virtue comes money and every other good of man, public as well as private. This is my teaching, and if this is the doctrine which corrupts the youth, I am a mischievous person. But if any one says that this is not my teaching, he is speaking an untruth. Wherefore, O men of Athens, I say to you, do as Anytus bids or not as Anytus bids, and either acquit me or not; but whichever you do, understand that I shall never alter my ways, not even if I have to die many times.

wordwrap.cpp

#include <fstream>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

template<typename T>
class matrix
{
    vector<T> data_;
    size_t cols_;

public:
    matrix(size_t rows, size_t cols)
        : data_(rows * cols), cols_(cols)
    {
    }

    T & operator()(size_t row, size_t col)
    {
        return data_[row * cols_ + col];
    }
};

int main()
{
    ifstream in("impartire.txt");
    
    string line;
    while (getline(in, line))
    {
        vector<string> words;
        istringstream line_stream(line);

        int width;
        string s;
        line_stream >> width;
        while (line_stream >> s)
            words.push_back(s);

        size_t n = words.size();

        int inf = numeric_limits<int>::max();

        matrix<int> penalties(n, n);
        for (size_t i = 0; i < n; i++)
        {
            int len = 0;
            for (size_t j = i; j < n; j++)
            {
                len += words[j].length();
                int cost = width - len - (j - i);
                if (cost < 0)
                    penalties(i, j) = inf;
                else
                    penalties(i, j) = cost * cost;
            }
        }

        for (size_t i = n - 1; ; i--)
        {
            if (penalties(i, n - 1) == inf)
            {
                for (size_t j = i + 1; j < n; j++)
                    penalties(i + 1, j) = 0;
                break;
            }
            if (i == 0)
                break;
        }
        if (penalties(0, n - 1) != inf)
        {
            for (size_t j = 0; j < n; j++)
                penalties(0, j) = 0;
        }

        vector<int> costs(n), line_first_words(n);
        for (size_t i = 0; i < n; i++)
        {
            line_first_words[i] = 0;
            costs[i] = penalties(0, i);
            for (size_t k = 0; k < i; k++)
            {
                int c = penalties(k + 1, i);
                if (c != inf)
                {
                    c += costs[k];
                    if (c < costs[i])
                    {
                        line_first_words[i] = k + 1;
                        costs[i] = c;
                    }
                }
            }
        }

        vector<int> wrap_points;
        size_t j = n - 1;
        do
        {
            wrap_points.push_back(line_first_words[j]);
            j = line_first_words[j];
        } while (j-- > 0);

        for (size_t j = wrap_points.size() - 1; ; j--)
        {
            cout << wrap_points[j] + 1;
            if (j == 0)
                break;
            else
                cout << ' ';
        }
        cout << endl;
    }
}