Splititing a string into multiple lines with each line having at most N non-space characters

BBrandon (28)
Bessie the cow is working on an essay for her writing class. Since her handwriting is quite bad, she decides to type the essay using a word processor.
The essay contains N words (1≤N≤100), separated by spaces. Each word is between 1 and 15 characters long, inclusive, and consists only of uppercase or lowercase letters. According to the instructions for the assignment, the essay has to be formatted in a very specific way: each line should contain no more than K (1≤K≤80) characters, not counting spaces. Fortunately, Bessie's word processor can handle this requirement, using the following strategy:

If Bessie types a word, and that word can fit on the current line, put it on that line.
Otherwise, put the word on the next line and continue adding to that line.
Of course, consecutive words on the same line should still be separated by a single space. There should be no space at the end of any line.

Unfortunately, Bessie's word processor just broke. Please help her format her essay properly!

INPUT FORMAT (file word.in):
The first line of input contains two space-separated integers N and K.
The next line contains N words separated by single spaces. No word will ever be larger than K characters, the maximum number of characters on a line.

OUTPUT FORMAT (file word.out):
Bessie's essay formatted correctly.
SAMPLE INPUT:
10 7
hello my name is Bessie and this is my essay
SAMPLE OUTPUT:
hello my
name is
Bessie
and this
is my
essay
Including "hello" and "my", the first line contains 7 non-space characters. Adding "name" would cause the first line to contain 11>7 non-space characters, so it is placed on a new line.

Can anyone help me with solving this? It's a problem from a USACO training camp of mine that I don't really know how to solve since I'm not that good with strings (so comments would be nice).

And I kinda also need help with another problem if you can do more (I have a solution that works for some imputs, but it's really bad and I don't want to show it).

Bessie is running a race of length K (1≤K≤109) meters. She starts running at a speed of 0 meters per second. In a given second, she can either increase her speed by 1 meter per second, keep it unchanged, or decrease it by 1 meter per second. For example, in the first second, she can increase her speed to 1 meter per second and run 1 meter, or keep it at 0 meters per second and run 0 meters. Bessie's speed can never drop below zero.
Bessie will always run toward the finish line, and she wants to finish after an integer amount of seconds (ending either at or past the goal line at this integer point in time). Furthermore, she doesn’t want to be running too quickly at the finish line: at the instant in time when Bessie finishes running K meters, she wants the speed she has just been traveling to be no more than X (1≤X≤105) meters per second. Bessie wants to know how quickly she can finish the race for N (1≤N≤1000) different values of X.

SCORING:
Test cases 2-4 satisfy N=X=1.
Test cases 5-10 satisfy no additional constraints.
INPUT FORMAT (file race.in):
The first line will contain two integers K and N.
The next N lines each contain a single integer X.

OUTPUT FORMAT (file race.out):
Output N lines, each containing a single integer for the minimum time Bessie needs to run K meters so that she finishes with a speed less than or equal to X.
SAMPLE INPUT:
10 5
1
2
3
4
5
SAMPLE OUTPUT:
6
5
5
4
4
When X=1, an optimal solution is:

Increase speed to 1 m/s, travel 1 meter
Increase speed to 2 m/s, travel 2 meters, for a total of 3 meters
Keep speed at 2 m/s, travel 5 meters total
Keep speed at 2 m/s, travel 7 meters total
Keep speed at 2 m/s, travel 9 meters total
Decrease speed to 1 m/s, travel 10 meters total
When X=3, an optimal solution is:

Increase speed to 1 m/s, travel 1 meter
Increase speed to 2 m/s, travel 3 meters total
Increase speed to 3 m/s, travel 6 meters total
Keep speed at 3 m/s, travel 9 meters total
Keep speed at 3 m/s, travel 12 meters total
Note that the following is illegal when X=3:

Increase speed to 1 m/s, travel 1 meter
Increase speed to 2 m/s, travel 3 meters total
Increase speed to 3 m/s, travel 6 meters total
Increase speed to 4 m/s, travel 10 meters total
This is because at the instant when Bessie has finished running 10 meters, her speed is 4 m/s.

againtry (2313)
Can anyone help me with solving this? It's a problem from a USACO training camp of mine that I don't really know how to solve since I'm not that good with strings (so comments would be nice).

And I kinda also need help with another problem if you can do more (I have a solution that works for some imputs, but it's really bad and I don't want to show it).


Unless you post the relevant snippets of code or pseudocode you have written and having trouble with what's the ethical difference between this and a blatant attempt at plagiarism.

BBrandon (28)
Unless you post the relevant snippets of code or pseudocode you have written and having trouble with what's the ethical difference between this and a blatant attempt at plagiarism.


For starters, I'm not publically publishing the code and I'm not trying to make any money off of it. I've also mentioned that I'm trying to learn about strings and I'm struggling so I would prefer comments in the code as well, but sure, I'll try to post some snippets of my (rather terrible) code if I can load it up.
againtry (2313)
By all means post your code. It's not my site.

BTW thanks for pointing to the USACO site. It's a great site and has noble ambitions like Project Euler where you are competing against yourself effectively.

My gripe is public solutions tend to destroy the fun/challenge especially when the question is so completely open-ended, alsmost like the one's who come her and just want their homework done for them.

I'm glad you're not in that camp and simply and honestly enjoy the programming game and want to learn more - most of us do.

Bring on your snippets :)

BBrandon (28)

I apologize if I am missing some coding logic on what plagiarism is, as all I know is when you copy it and claim it as your code, and I do not have any solutions for the string problem because I am really bad at strings so far and I want to see a solution to help me better understand the problem and how to solve it. However, I do have a pretty rudimentary solution for the racing problem... (I'm still working on it)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
#include <fstream>
#include <iostream>
using namespace std;

// driver code
int main() {
  ifstream fin ("file race.in");
  ofstream fout ("file race.out");
  int K;
  int N;
  fin >> K >> N;
  int X[N-1];
  for (int counter1 = 0; counter1 < N; ++counter1) { //Collects the maximal speed cases
    fin >> X[counter1];
  }
  for (int counter = 0; counter < N; ++counter) { //Starts solving for each case
    int speed = 0;
    int remaindis = K;
    int time = 0;
    for (int counter2 = 1; speed < X[counter] && remaindis > 0; ++counter2) { //Raises speed up to the maximum speed
        speed = speed + 1;
        time = counter2;
    }
    if (remaindis <= 0) { //Checks if distance is already 0 or less; if so, code stops and prints the time needed for this case and moves on, if not, code continues on
        fout << time << endl;
    }
    else {
        for (int counter3 = time; remaindis > 0 && remaindis >= ((speed + 1) + speed); ++counter3) { //Checks if the remaining distance would be possible for a speed increase (and then decrease) past the speed limit
            speed = speed + 1;
            time = counter3;
        }
        if (remaindis <= 0) { //Checks if distance is already 0 or less; if so, code stops and prints the time needed for this case and moves on, if not, code continues on
            fout << time << endl;
            }
        else {
            fout << "error" << endl;
            }
    }
  }
}
Last edited on
BBrandon (28)
This part is especially causing me trouble! It needs to identify whether increasing the speed to a certain amount and then decreasing it back to the maximum amount (variable K) would be possible, and then executes that and then prints the result.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
else {
        for (int counter3 = time; remaindis > 0 && remaindis >= ((speed + 1) + speed); ++counter3) { //Checks if the remaining distance would be possible for a speed increase (and then decrease) past the speed limit
            speed = speed + 1;
            time = counter3;
        }
        if (remaindis <= 0) { //Checks if distance is already 0 or less; if so, code stops and prints the time needed for this case and moves on, if not, code continues on
            fout << time << endl;
            }
        else {
            fout << "error" << endl;
            }
    }
  }
}
BBrandon (28)
Made a few more edits to the problem-causing parts (I also fixed a few minor problems with the part leading up to it)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
else {
        for (int counter3 = time; remaindis > 0; ++counter3) {
          if (remaindis >= speed + speed + 1) {
            speed = speed + 1;
          }
          else if (speed > K) {
            speed = speed - 1;
          }
          fout << remaindis << " ";
          remaindis = remaindis - speed;
          time = counter3;
        }
      fout << time << endl;
    }
  }
}

Now, I just need to figure out a way for the program to reduce the speed to K before it the remaining distance turns to 0.
BBrandon (28)
Okay, I think I've got it for the second quest, but I still need help with the first question. Any solutions would be nice to see (and comments within them would be even better!).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#include <fstream>
#include <iostream>
using namespace std;

// driver code
int main() {
  ifstream fin ("race.in");
  ofstream fout ("race.out");
  int K;
  int N;
  fin >> K >> N;
  int X[N-1];
  for (int counter1 = 0; counter1 < N; ++counter1) { //Collects the maximal speed cases
    fin >> X[counter1];
  }
  for (int counter = 0; counter < N; ++counter) { //Starts solving for each case
    int speed = 0;
    int remaindis = K;
    int time = 0;
    for (; speed < X[counter] && remaindis > 0; ++time) { //Raises speed up to the maximum speed
        speed = speed + 1;
        remaindis = remaindis - speed;
        
    }
    if (remaindis <= 0) { //Checks if distance is already 0 or less; if so, code stops and prints the time needed for this case and moves on, if not, code continues on
        fout << time << endl;
    }
    else {
        for (; remaindis > 0; ++time) {
          if (remaindis >= (speed + speed + 1)) {
            speed = speed + 1;
          }
          else if (speed > X[counter]) {
            speed = speed - 1;
          }
          remaindis = remaindis - speed;
        }
      fout << time << endl;
    }
  }
}
againtry (2313)
In the interests of clarity (for me anyway) I set out your code so it fits in areasonable width (about 80 characters), made the block-bracket arrangement clearer and added a few comments.

It doesn't solve the speed issue but I think it might help you concentrate on the logic. You say it "checks if the remaining distance would be possible ... " but it's not clear how that check is carried out..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
#include <fstream>
#include <iostream>
using namespace std;

// driver code
int main()
{
    ifstream fin ("file race.in");
    ofstream fout ("file race.out");
    
    int K = 0; // <--
    int N = 0; // <--
    
    fin >> K >> N;
    
    int X[N-1]; // <-- ??? DECLARE A DYNAMIC ARRAY WITH new
    for (int counter1 = 0; counter1 < N; ++counter1)
    {
        //Collects the maximal speed cases
        fin >> X[counter1];
    }
    for (int counter = 0; counter < N; ++counter)
    {
        //Starts solving for each case
        int speed = 0;
        int remaindis = K;
        int time = 0;
        for (
             int counter2 = 1;
             speed < X[counter] && remaindis > 0;
             ++counter2)
        {
            //Raises speed up to the maximum speed
            speed = speed + 1;
            time = counter2;
        }
        if (remaindis <= 0)
        {
            // Checks if distance is already 0 or less; if so, code stops
            // and prints the time needed for this case and moves on, if not,
            // code continues on
            fout << time << endl;
        }
        else
        {
            for
                (
                 int counter3 = time;
                 remaindis > 0 && remaindis >= ((speed + 1) + speed); //???
                 ++counter3
                 )
            {
                //Checks if the remaining distance would be possible for a speed
                //increase (and then decrease) past the speed limit How???
                speed = speed + 1;
                time = counter3;
            }
            if (remaindis <= 0)
            {
                //Checks if distance is already 0 or less; if so, code stops
                //and prints the time needed for this case and moves on,
                //if not, code continues on
                fout << time << endl;
            }
            else
            {
                fout << "error" << endl;
            }
        }
    }
}
BBrandon (28)
Oh yeah; I've made a few more updates to the code to partially fix that condition, but there are still a few scenarios I finding an incorrect output.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
#include <fstream>
#include <iostream>
using namespace std;

// driver code
int main() {
  ifstream fin ("race.in");
  ofstream fout ("race.out");
  int K;
  int N;
  fin >> K >> N;
  int X[N-1];
  for (int counter1 = 0; counter1 < N; ++counter1) { //Collects the maximal speed cases
    fin >> X[counter1];
  }
  for (int counter = 0; counter < N; ++counter) { //Starts solving for each case
    int speed = 0;
    int remaindis = K;
    int time = 0;
    for (; speed < X[counter] && remaindis > 0; ++time) { //Raises speed up to the maximum speed
        speed = speed + 1;
        remaindis = remaindis - speed;
        
    }
    if (remaindis <= 0) { //Checks if distance is already 0 or less; if so, code stops and prints the time needed for this case and moves on, if not, code continues on
        fout << time << endl;
    }
    else {
        for (; remaindis > 0; ++time) {
          int summation = 0;
          for (int counter2 = speed; counter2 > 0; --counter2) {
            summation = summation + counter2;
          }
          fout << summation << "ss "; //debug
          if (remaindis >= (summation + speed + 1)) {
            speed = speed + 1;
          }
          else if (remaindis >= summation + speed) {
            speed = speed;
          }
          else if (speed > X[counter] && remaindis <= summation + speed) {
            speed = speed - 1;
          }
          remaindis = remaindis - speed;
        }
      fout << time << endl;
    }
  }
}
againtry (2313)
but there are still a few scenarios I finding an incorrect output.

OK, I don't have the solution, mainly because you haven't described the problem and haven't pinned it down.

Here's what you do.

Extract/copy the code to a new test main()
Assign hard-coded values to the variables.
Now, work out what the expected output is. Even add some cout's or add breakpoints and trace the values.

Do it line by line and check that each small piece is making sense and what you expect.
BBrandon (28)
Thanks for your help! I've devised a solution that works with all of my test scenarios (it was actually a really silly mistake I made in the summation when the miles needed to be ran were odd)! Here's a preview of my final code below...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
#include <fstream>
#include <iostream>
using namespace std;

// driver code
int main() {
  ifstream fin ("race.in");
  ofstream fout ("race.out");
  int K;
  int N;
  fin >> K >> N;
  int X[N];
  for (int counter1 = 0; counter1 < N; ++counter1) { //Collects the maximal speed cases
    fin >> X[counter1];
  }
  for (int counter = 0; counter < N; ++counter) { //Starts solving for each case
    int speed = 0;
    int remaindis = K;
    int time = 0;
    for (; speed < X[counter] && remaindis > 0; ++time) { //Raises speed up to the maximum speed
        speed = speed + 1;
        remaindis = remaindis - speed;
    }
    if (remaindis <= 0) { //Checks if distance is already 0 or less; if so, code stops and prints the time needed for this case and moves on, if not, code continues on
        fout << time << endl;
    }
    else {
        for (; remaindis > 0; ++time) {
          int summation = ((speed)*(speed-1))/2-((X[counter]-1)*(X[counter]))/2;
          if (remaindis >= (summation + speed + speed + 1)) {
            speed = speed + 1;
          }
          else if (remaindis >= summation + speed) {
            speed = speed;
          }
          else if (speed > X[counter] && remaindis <= summation + speed) {
            speed = speed - 1;
          }
          remaindis = remaindis - speed;
          
        }
      fout << time << endl;
    }
  }
}
Last edited on
againtry (2313)
Excellent! Well done for finding the bug and fixing it yourself.

I can't look at it straight away but I'll do so in the next couple of hours and make some sort of comment.

( line 12 is not good you can't reliably declare an array that way ...
... checkout arrays and dynamic memory
http://www.cplusplus.com/doc/tutorial/arrays/
http://www.cplusplus.com/doc/tutorial/dynamic/ )
againtry (2313)
line 12: Since you are reading in the value of N you have to create a dynamic array.

1
2
3
4
5
6
7
8
9
 
int* X = new int[N];

// program blah blah
// followed later on when you're finished with X by:

delete[] X;
X = nullptr; // some say is good practice, some don't n=bother

// then just treat X[i] as a 'normal' array


And except for your excessively long lines, I don't have any comments to add :)
Topic archived. No new replies allowed.