uva: 10066 – The Twin Towers ( LCS )

10066 – The Twin Towers

Problem analysis:

  •  Given the descriptions of two dissimilar towers you are asked only to find out the number of tiles in the highest twin towers that can be built from them.
  • For each pair of towers in the input first output the twin tower number followed by the number of tiles (in one tower) in the highest possible twin towers that can be built from them. Print a blank line after the output of each data set.

Soltion analysis:

  •  LCS – solution of this problem is standard LCS  algorithm

C++ solution:


#include<stdio.h>

#define MAX 100
#define max(a,b) ((a)<(b) ? (b):(a))

int N1, N2;
int firstT[MAX+1];
int secondT[MAX+1];
int c[MAX+1][MAX+1];
int lcsLength, nCase;

int main10066()
{
	int i,j;

	//int firstT[MAX]={0};
	//int secondT[MAX]={0};

	while(true)
	{
		scanf("%d %d", &N1, &N2);

		if(N1 ==0 && N2==0) break;

		for(i=1; i<=N1; i++)
			scanf("%d",&firstT[i]);

		for(i=1; i<=N2; i++)
			scanf("%d",&secondT[i]);

		/*for(i=0;i <=N1; i++)
			for(j=0;j<=N2; j++)
				c[i][j] = 0;*/

		for(i=1; i<= N1; i++)
			for(j=1; j<= N2; j++)
			{
				if(firstT[i] == secondT[j])
				{
					c[i][j] = c[i-1][j-1] + 1;
				}
				else
				{
					c[i][j] = max(c[i-1][j], c[i][j-1]);
				}
			}

		printf("Twin Towers #%d\n",++nCase);
		printf("Number of Tiles : %d\n\n",c[N1][N2]);
	}
return 0;
}

Sample Input
7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
0 0

Sample Output
Twin Towers #1
Number of Tiles : 4

Twin Towers #2
Number of Tiles : 6

Advertisements

About M Moniruzzaman
A passionate software engineer, have been developing applications on various platforms such as Android, iPhone, .Net (C#) technologies and web based ASP.NET, PHP, JavaScript, jQuery technologies for more than 10 years. Especially I have expertise on developing applications for Android and iPhone, as well as service oriented, client-server based applications where clients will be reside on Android/iPhone that communicate with WCF(.NET) service hosted on server. I have completed certification in Microsoft Certified Professional Developer (MCPD) on .Net 4 . I have completed my graduation in -- B.Sc. (Engineering) in Computer Science and Engineering, ShahJalal University of Science and Technology, Bangladesh. Thanks, M. Moniruzzaman (Zaman)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: