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?

3
Contributors
5
Replies
6
Views
9 Years
Discussion Span
Last Post by FREEZX

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

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

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

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.``````

Thank you soo much you just made my day xD.