I need help!!!

[FREEZX]

I need to make a program that will extract numbers from a file sorted like bowling cones, like this:

1
2 5
2 2 7
1 6 4 8
2 9 4 7 3

and than calculate the maximum a bowler can score if the ball can go down on the next number diagonally. My question is what is the most efficient way i can solve this problem. The maximum number of lines is 100, and the time limit is 1 second, so brute force isn't the way to solve it. Any ideas?

[NicAx64]

if your input set ( problem space ) is a random set. Then burte forcing is the only way. Even backtracking is also impossible.

[FREEZX]

This is what i coded so far.

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main () 
{
  string line;
  int nol;
  ifstream myfile("kuglanje.in");
  if (myfile.is_open())
  {
      getline (myfile,line);
      nol=atoi(line.c_str());
      string buf;
      int omfg[nol][nol];
      int chk;
      int maxpos;
      int position;
      int position1;
      int rez=0;
      int bufint;
      int max=0;
      int ansnum;
      string ans;
      for(int i=0; i<nol; i++)
      {
              getline (myfile, ans);
              for(int x=0; x<i+1; x++)
              {
                      if(x==0)
                      {
                             position = ans.find(" ");
                             buf=ans.substr(0,position);
                             omfg[i][x] = atoi(buf.c_str());
                             chk=omfg[i][x];
                      }
                      else
                      {
                      position1 = ans.find(" ");
                      buf=ans.substr(position+1, position1);
                      omfg[i][x]=atoi(buf.c_str());
                      chk=omfg[i][x];
                      cout<<omfg[i][x];
                      }
                      if(omfg[i][x]>=max)
                      {
                                    max=omfg[i][x];
                                    maxpos=position;
                      }
                      position=position1;
              }
              max=0;       
      }
      rez=omfg[0][0];
      for(nol; nol>0; nol--)
             {
              
             }                                   
      myfile.close();
      ofstream outf("kuglanje.out");
      outf<<rez;
      outf.close(); 
  }
  else cout << "Fajlot nemoze da se otvori!";
  system("pause");
  return 0;
}

Any suggestions on how the brute forcing should implement in the code

[FREEZX]

BTW the input's first line says how many lines does the bowling triangle have.

[siddhant3s]

Your problem is just like (actually same as) Project Euler problem 18 & 67 http://projecteuler.net/index.php?section=problems&id=18

I cracked the problem. I used down to up approach. Well I am feeling a lot lazy to type down my algorithm. But never mind. When we answer at Project Euler, we get access to a forum where we all discuss what all algorithm may have been possible. So here is the algorithm I used which I am copy/pasting from that forum. ( I have edited it so that it match your problem as we were given a different triangle)

31 Jul 2004 04:38 am 
mather    mather is from USA
Not sure if you all know this already, but starting at the base proves much superior in this problem... e.g.:


[B]1[/B]	6	4	8
[B]2[/B]	[B]9[/B]	4	7	3

If you reached '1' you would choose 9' over '2', so just add it to '9' to give you '10'.


2	2	7
[B]10[/B]	6	4	8
2	[B]9[/B]	4	7	3


Likewise, add the 9 to  6 and 7,to 4 and 8. this gives you:

2	2	7
10	15	11	15
--	--	--	--	--
This eliminates the last row....
Proceed like this up the triangle... whatever integer appears at the peak is the maximum sum.

[FREEZX]

Thank you soo much you just made my day xD.