[algogeeks] Minimum sum of Array
Hello All! I have a given array of numbers and I have to change the sign of numbers to find out the minimum sum. The minimum sum will be 0 or greater than 0. Here is couple of test cases 1. [ 1 , 2 , 3 , 2 , 4 ]. Changing the sign [ -1 , -2 , -3 , 2 , 4 ] so minimum sum will be 0. 2. [ 3 , 5 , 7 , 11 , 13 ]. Changing the sign [ -3 , -5 , 7 , -11 , 13 ] so minimum sum is 1. So technically this problem boils down to divide the set into two subset and find out the minimum difference. I though of DP but the number of element in array could 10^5 so could some one please tell me how to solve this problem ? I didn't assume that number will be positive because it was not given in the problem. Regards Mukesh Tiwari --
[algogeeks] Re: Remove spaces
If its allowed in Haskell then only one line is enough.
import Data.List
stringWithspace :: String - String
stringWithspace xs = unwords.words $ xs
You can run this program on ideone [ http://ideone.com/RloOE ]
On Aug 12, 8:00 pm, ankit sambyal ankitsamb...@gmail.com wrote:
Guys sorry for posting the buggy code . Here is the working code :
void delExtraSpaces (char Str[])
{
int Pntr = 0;
int Dest = 0;
int flag=0;
while (Str[Pntr]!='\0')
{
if (Str[Pntr] != ' ')
{
Str[Dest++] = Str[Pntr];
flag=0;}
else if(Str[Pntr]==' ' flag==0)
{
Str[Dest++] = Str[Pntr];
flag=1;
}
Pntr++;
}
Str[Dest] = '\0';
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST+Heap
What you explained is the property of Treap data structure . You can have a look at wiki [ http://en.wikipedia.org/wiki/Treap ] or you can search google for treap. On Jun 8, 8:15 pm, Akshata Sharma akshatasharm...@gmail.com wrote: A rooted binary tree with keys in its nodes has the binary search tree property (BST property) if, for every node, the keys in its left subtree are smaller than its own key, and the keys in its right subtree are larger than its own key. It has the heap property if, for every node, the keys of its children are all smaller than its own key. You are given a set of n binary tree nodes that each contain an integer i and an integer j. No two i values are equal and no two j values are equal. We must assemble the nodes into a single binary tree where the i values obey the BST property and the j values obey the heap property. If you pay attention only to the second key in each node, the tree looks like a heap, and if you pay attention only to the first key in each node, it looks like a binary search tree.Describe a recursive algorithm for assembling such a tree -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: TLE in KPEQU [ Haskell ]
Solved . Just changed my count function count :: Integer - Integer - Integer count 0 _ = 0 count n p = div n p + count ( div n p ) p -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Setnja Wrong Answer [ Haskell Code ]
Hello all , i am trying to solve this problem https://www.spoj.pl/problems/SETNJA/ but getting WA. Could some one please tell me what is wrong with algorithm. import qualified Data.ByteString.Char8 as BS import Data.List as L solve :: BS.ByteString - Integer solve xs = solverHelp xs 1 where solverHelp ys p | BS.null ys == True = p | otherwise = case BS.head ys of 'L' - solverHelp ( BS.tail ys ) 2*p 'R' - solverHelp ( BS.tail ys ) ( 2*p + 1 ) 'P' - solverHelp ( BS.tail ys ) p '*' - solverHelp ( BS.tail ys ) p + solverHelp ( BS.tail ys ) ( 2*p ) + solverHelp ( BS.tail ys ) ( 2*p + 1 ) main = BS.interact $ BS.unlines . map ( BS.pack . show . solve ) . BS.lines -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Recurrence quadratic...
hello Allysson here is the link for discussion of problem http://groups.google.co.in/group/comp.programming/browse_thread/thread/4a06904cbbd7c2d3/69c5adbf6badbd8c#69c5adbf6badbd8c On Oct 22, 5:19 am, Allysson Costa [EMAIL PROTECTED] wrote: Dear friends, I have a recurrence to solve but I'm lost T(N)= [T(N-1)]^2. Then I need to develop this recurrence by iteration/expasion. T(n-1)=[(T(N-2)]^2 T(n-2)=[(T(N-3)]^2 T(n-3)=[(T(N-4)]^2 Then T(N)= [T(N-1)]^2 T(N)= [T(N-2)]^4 T(N)= [T(N-3)]^8 T(N)= [T(N-4)]^4 . : T(N)=[T(N-k)]^2^k For T(1) -- N-k=1 -- k=N-1 Then T(N)=[T(1)]^2^N-1 I stop here and don't know how to show the closed form of recurrence. Any suggestions. Thanks. Allysson --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Spiral number
Hello everybody , i am trying to solve this(http://online- judge.uva.es/ p/v9/903.html) problem and input constrants are such that it is not possible to store the the numbers in the array and print those numbers. So i use the algorithm 1)get the number and return its coordinate 2) take the input all adjacent coordiantes and return the number belonging to that coordinate . i am facing the problem in second part that is if i have given coordiante how to get the number belonging to that coordinate, lets consider the spiral 21 22 23 24 25 26 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13 let the coordinate of 1 is (0,0) ie origin then coordinate of 11 will be (2,0) and so on . now my problem is if i give coordiante (2,-1) then my program should return 12 . thnkx in advance --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] efficient method of exponation
hello everybody . for a given value i have to find a lowest possible steps in exponation . i searched on net and i find three ways binary method [steps will be log2(n)+number of 1 bits in binary expression of n -1] ,factor method [l(n)=1+l(n-1) if n is prime else n=k*p then l(n)=l(k)+l(p)] . now my problem is that i don't have algorithm for power tree so that i can compare all the three vlaues to find out lowest value . thnkx --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Sum of Gaussian factor
ya you are right . this is project euler problem . until now i have found that i can determine how many devisiors of number in sqrt(n) but what are the divisiors above aqrt(n) i am not able to determine. if sqrt(n) is perfect square and there are k factors upto sqrt(n) then total number of divisiors will be (2*k-1) otherwise (2*k). i.e.25 is perfect squre and sqrt(25)=5 .There are only two divisiors 1 and 5 then total number of divisiors of 25 will (2*2-1)=3 but here problem arise . after sqrt(n) i can not find what will be other factors . if some how i can over come this problem than for each divisior of number i have to find out all the prime factors and check out how many of them are in form of 4k+1 and how many are of 4k+3 . for all 4k +1 prime numbers i have to find p=a^2+b^2. but still i don't know how much it will be efficient becoz till now i haven't coded this problem . On Jun 26, 6:08 am, Lego Haryanto [EMAIL PROTECTED] wrote: This is most likely about a Project Euler problem. A tough one, I don't know how to get the result under 60s time limit. To capture the Gaussian factors a+bi that divides an integer, I generated pairs of a and b (which is relatively prime to each other), and for each, I observed the a^2+b^2 denominator to see the smallest n which can divide a^2+b^2, ... something like that. I'm sure you already note that if a+bi is a factor, then a-bi is also a factor, and similiarly when a != b, b-ai and b+ai are also Gaussian factors. My solution is very ugly but it does solve the problem in a little bit over 60 seconds. I'm sure there exists more elegant solution for this. Best, -Lego On 6/22/07, mukesh tiwari [EMAIL PROTECTED] wrote: hello everybody . i want to know algorithm for finding gaussian factor of real number . like for 5 there are five gaussian factors 1, 1+2i, 1-2i, 2+i, 2-i, 5 and there sum is 12 . so can any one help me on this topic . i search lot on google but could not find any anything . if u have any such kind of link so kindly send me . thnkx in advance . -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Problem with conditional statement
Hi everybody i am trying to solve problem http://acm.uva.es/p/v105/10512.html. my solution is (x+y)y=P(1) (x-y)x=Q (2) (1+(y/x))xy=P (1)//taking x outside (1-(y/x))x^2=Q (2) dividing 1 and 2 and let (y/x)=k (1+k)k/(1-k)=P/Q; solving for k k=-(P+Q) +-sqrt((P+Q)^2+4PQ)/2Q; since x=y so we can not take -ve sign as it will make |k|1 which is not possible so i take only +ve sign ; solution is possible only when (P+Q)^2+4PQ is perfect square . after determining k we can find out x and y so my values are x=+-sqrt(Q/(1-k)); and y=+-sqrt(Pk/(1+k)); now my problem is based on for each value of x we have two values of y so we have 4 pair of values .So which value to output . thnkx in advance . --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Need Algorithm for Persistence number
Hi everbody , i am trying to solve this problem http://acm.uva.es/p/v105/10527.html but i am not getting any efficient algorithm . One algorithm i applied while(n9) for i=2 to 9 if(n%i=0)//then i is factor of n and may be a digit in the number store i for further processing n=n/i now the problem with this algorithm is supose we have input 45 so answer should be 59 as from defintion 59 - 45 but my algorithm is giving the answer is 335 as 335 - 45 but i have to find out minimum number .Kindly help me . Thnkx in advance . --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] need help for graph problem ...
hello friends i m trying to solve problem
http://online-judge.uva.es/p/v5/523.html
in this problem i using floyd's algorithm i m able to figure out total cost
but i m not able to figure out the path . may be the reason that i did not
understand the algorithm fully and i use it as a black box but now i have
to go inside blackbox so plz help me to figure out the path...
here is my code ...
#includeiostream
using namespace std;
#define inf 100
int pathcost[1000][1000],pre[1000][1000];
int takeinput()
{
int j,k=0,m;
char c;
while(cin.get(c) c!='\n')
{
if((c='0' c='9') || (c=='-'))
{
cin.unget();
cinpathcost[0][k];
if(pathcost[0][k]==-1)
pathcost[0][k]=inf;
k++;
}
}
return(k);
}
int main()
{
int m1,citytax[1000],w,i,j,k,t1,t2;
char c;
scanf(%d,m1);
getchar();//one for \n and anthor for blank line
getchar();
while(m1--)
{
w=takeinput();
//printf(w=%d\n,w);
for( i=1;iw;i++)
for( j=0;jw;j++)
{
cinpathcost[i][j];
if(pathcost[i][j]==-1)
pathcost[i][j]=inf;
}
for(i=0;iw;i++)
cincitytax[i];
getchar();
for(i=0;iw;i++)
for(j=0;jw;j++)
pre[i][j]=i;
for(k=0;kw;k++)
{
for(i=0;iw;i++)
{
for(j=0;jw;j++)
{
if(pathcost[i][j]pathcost[i][k]+pathcost[k][j]+citytax[k])
{
pathcost[i][j]=pathcost[i][k]+pathcost[k][j]+citytax[k];
pre[i][j]=pre[k][j];
}
}
}
}
while(cin.get(c) c!='\n')
{
cin.unget();
cint1t2;
printf(From %d to %d :\n,t1,t2);
printf(Total cost : %d\n,pathcost[t1-1][t2-1]);
getchar();
}
printf(\n);
}
}
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] getting wrong answer for problem
hi friends i m trying to solve this problem
http://acm.uva.es/p/v111/11151.html but getting wrong answer..
my algorithm is i m trying to enumarate all the n*(n+1)/2 substrings of
string ,where n is string length...
and checking for palindrom ..
suppose i have input ADAM .then all possible substrings will be
ADAM
ADA
DAM
AD
DA
AM
A
D
A
M
now ADA is lagest palindrome
but i don't know why i m getting WA... or plz tell me wheather my algorithm
is right or wrong
here is my code .plz check it ..
#includestdio.h
#includestring.h
int chkpalin(char* a,int k,int n)
{
int w;
for(w=k;w=n;w++)
if(a[w]!=a[n+k-w])
return(0);
return(1);
}
main()
{
char str[1010],c;
int i,j,k,n,w,v;
scanf(%d,k);
getchar();
for(v=0;vk;v++)
{
w=0;
gets(str);
n=strlen(str);
for(i=n-1;i=0;i--)
{
for(j=0;j+in;j++)//enumarate all the n*(n+1)/2 substrings
chk wheather a[j] to a[i+j] is palindrome or not
{
w=chkpalin(str,j,i+j);
/*for(int x=j;x=i+j;x++)
printf(%c,str[x]);
printf(\n);*/
if(w==1)
break;
}
if(w==1)
break;
}
printf(%d\n,i+1);
/*for(int x=j;x=i+j;x++)
printf(%c,str[x]);
printf(\n);*/
}
}
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] dynamic programming ..
hi everybody ..i am stuck on a problem ..i need ur help.. problem is that i have k coins(v1,v2,v3..vk) and money S . and i have to find out that whether it is possible or not to make the money S using the given coins...firstly i was using greedy but it failed on some inputs ..like we have 2 coins of (3 and 5) and i have to exchange 11 . so using greedy fiirstly i take 5 since it is less than 11 so i have to again take 5 and sum becomes 10 . So using greedy it gives it not possible but if use onr coin of 5 and two coin of 3 then it is possible .. so plz help me dynamic programming experts.. limits are k100 and S5 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] need help of physics
hi everybody i m trying to solve this problem but i can't sovle it ...plz suggest me algorithm to solve it . link http://students.iitk.ac.in/programmingclub/iopc/problems/ or problem itself is Two electron are confined in a 1D infinite potential well. Each start from opposite ends with different velocities towards each other. Whenever they meet they pass through each other and lets say a mesons is transferred from the electron we have marked A to electron B. Following classical mechanics and assuming that intersections does not changes the electron velocities ( velocities get reversed on reaching the wall of the potential well ) you have to find the no. of mesons that get accumulated in B after a certain time t. You are given the length of the potential well and speeds of each electron. *Input:* First line of input will consist of a single integer T = no. of test cases; Each test case will consist of 4 32-bit integers u,v,l,t in a single line. Where u= velocity of electron A v= velocity of electron B l=length of the 1D potential well t=time to consider *Output:* For each test case you have to print a single integer giving the number of intersections face to face or overtakes in a single line. *Sample Input:* 2 10 10 20 2 2 2 4 2 *Sample Output:* 1 1 ** --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: need help regarding problem..
Hi Minhaz thnkx for help and pointing me to my mistake but now one thing i know ... is the number of points in the input will be distinct or there may be some duplicate point . like suppose the input is like this... 9 0 1 0 2 1 2 1 3 2 3 3 3 3 0 1 0 1 1 now the output of this program will (0 1)(0 2)(1 1)(1 3) (3 3)(3 0)(1 0)(1 1) ... that is we have to remove the point (2 3) from input ..so plz tell me may their be duplicate points ... On Jan 23, 5:53 pm, Minhaz Ul-Alam [EMAIL PROTECTED] wrote: Hey mukesh, I think the problem is with your assumption that no 3 or more points will be collinear.Yore code does not yield correct output in the following case. 8 0 1 0 2 1 0 1 1 1 2 1 3 2 0 2 3 it should make a rectilinear polygon like (0,1)(0,2)(1,2)(1,3)(2,3)(2,0)(1,0)(1,1)(0,1) as i didnot solved this problem i can't suggest you a process to get acc. but wish you get it quickly. again,can we try backtracking to choose points??? -Minhaz. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: need help regarding problem..
Hi Minhaz thnkx for help and pointing me to my mistake but now one thing i know ... is the number of points in the input will be distinct or there may be some duplicate point . like suppose the input is like this... 9 0 1 0 2 1 2 1 3 2 3 3 3 3 0 1 0 1 1 now the output of this program will (0 1)(0 2)(1 1)(1 3) (3 3)(3 0)(1 0)(1 1) ... that is we have to remove the point (2 3) from input ..so plz tell me may their be duplicate points ... On Jan 23, 5:53 pm, Minhaz Ul-Alam [EMAIL PROTECTED] wrote: Hey mukesh, I think the problem is with your assumption that no 3 or more points will be collinear.Yore code does not yield correct output in the following case. 8 0 1 0 2 1 0 1 1 1 2 1 3 2 0 2 3 it should make a rectilinear polygon like (0,1)(0,2)(1,2)(1,3)(2,3)(2,0)(1,0)(1,1)(0,1) as i didnot solved this problem i can't suggest you a process to get acc. but wish you get it quickly. again,can we try backtracking to choose points??? -Minhaz. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: problem regarding lexicographic path
hi Lego Haryanto
i tried ur metoh but still not working ...here is my code and i m
tired with this program . i am not getting even a single method to find
lexicographic shortest path.
#includestdio.h
int min1(int k,int m,int n)
{
int min;
min=k;
if(minm)
min=m;
if(minn)
min=n;
return(min);
}
main()
{
int
m1[100][100],a[100][100],i,j,m,n,min,k,arr[100],t,min2,t1,t2,t3,v1;
while(scanf(%d%d,m,n)==2)
{
for(i=0;im;i++)
for(j=0;jn;j++)
scanf(%d,a[i][j]);
for(i=0;im;i++)
m1[i][0]=a[i][0];
for(j=1;jn;j++)
for(i=0;im;i++)
m1[i][j]=a[i][j]+min1(m1[(i+m-1)%m][j-1],m1[i][j-1],m1[(i+1)%m][j-1]);
/*for(i=0;im;i++)
{
for(j=0;jn;j++)
printf(%d,m1[i][j]);
printf(\n);
}
printf(\n);*/
min2=m1[0][n-1];
k=0;
for(i=1;im;i++)
if(m1[i][n-1]min2)
{
min2=m1[i][n-1];
k=i;
}
//printf(k=%d min=%d\n,k+1,min2);
arr[n-1]=k;
//printf(min=%d arr[%d]=%d\n,min2,n-1,arr[n-1]);
for(j=n-2;j=0;j--)
{
//printf(j=%d ,j);
min=m1[(arr[j+1]+m-1)%m][j];
t1=(arr[j+1]+m-1)%m;
t=t1;
if(minm1[arr[j+1]][j])
{
min=m1[arr[j+1]][j];
t2=arr[j+1];
t=t2;
}
else if(min==m1[arr[j+1]][j])
{
t2=arr[j+1];
if(t1t2)
t=t2;
else
t=t1;
}
if(minm1[(arr[j+1]+1)%m][j])
{
min=m1[(arr[j+1]+1)%m][j];
t3=(arr[j+1]+1)%m;
t=t3;
}
else if(min==m1[(arr[j+1]+1)%m][j])
{
t3=(arr[j+1]+1)%m;
if(tt3)
t=t3;
}
arr[j]=t;
//printf(min=%d arr[%d]=%d\n,min,j,t);
}
for(i=0;i=n-1;i++)
printf(%d ,arr[i]+1);
printf(\n%d\n,min2);
}
}
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] problem regarding lexicographic path
hi friends i am try to solving this question
http://online-judge.uva.es/p/v1/116.html
for this problem i use left to right dynamic programming so i m getting the
total minimum cost but i m not getting how to find out lexicographically
shortest path .here is my code .if u can change it fine but plz suggest
me algorithm to find lexicographically shortest path.
my program works fine if one path exist but if more than one path exist then
it's not giving lexicographically smallest path.what i m doing is
i m finding last column(n-1) minimum value and note down the row number (let
it be i).now in second last column(n-2) i searched out minmium value in row
i-1,i and i+1 becoz of problem property. and i keep doing this until i reach
the 0th column.doing this i m not getting what i suppose to find out
...lexicographically smallest path.plz help...
#includestdio.h
int min1(int k,int m,int n)
{
int min;
min=k;
if(minm)
min=m;
if(minn)
min=n;
return(min);
}
main()
{
int m1[100][100],a[100][100],i,j,m,n,min,k,arr[100],t,min2,t1,t2,t3;
while(scanf(%d%d,m,n)==2)
{
for(i=0;im;i++)
for(j=0;jn;j++)
scanf(%d,a[i][j]);
for(i=0;im;i++)
m1[i][0]=a[i][0];
for(j=1;jn;j++)
for(i=0;im;i++)
m1[i][j]=a[i][j]+min1(m1[(i+m-1)%m][j-1],m1[i][j-1],m1[(i+1)%m][j-1]);
/*for(i=0;im;i++)
{
for(j=0;jn;j++)
printf(%d ,m1[i][j]);
printf(\n);
}*/
//printf(\n);
min2=m1[0][n-1];
k=0;
for(i=1;im;i++)
if(m1[i][n-1]min2)
{
min2=m1[i][n-1];
k=i;
}
//printf(k=%d min=%d\n,k+1,min2);
arr[n-1]=k;
for(j=n-2;j=0;j--)
{
min=m1[(arr[j+1]+m-1)%m][j];
t=(arr[j+1]+m-1)%m;
if(minm1[arr[j+1]][j])
{
min=m1[arr[j+1]][j];
t=arr[j+1];
}
if(minm1[(arr[j+1]+1)%m][j])
{
min=m1[(arr[j+1]+1)%m][j];
t=(arr[j+1]+1)%m;
}
arr[j]=t;
//printf(min=%d arr[%d]=%d\n,min,j,t);
}
for(i=0;i=n-1;i++)
printf(%d ,arr[i]+1);
printf(\n%d\n,min2);
}
}
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
