10192 - Vacation
Moderator: Board moderators
-
- New poster
- Posts: 1
- Joined: Sun Sep 18, 2005 8:40 pm
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
10192......OLE!!!!
thank you
Last edited by Wei-Ming Chen on Mon Nov 14, 2005 2:38 pm, edited 1 time in total.
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
-
- New poster
- Posts: 23
- Joined: Sat Oct 04, 2003 12:12 pm
- Location: in Your Heart ^^
- Contact:
I have the same problem here...
can any body give me another sample I/O ?
just feeling depressed from getting 6 WAs in a row , after 2 years idle from UVA

can any body give me another sample I/O ?
just feeling depressed from getting 6 WAs in a row , after 2 years idle from UVA


Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...
May every person helps each other and creates a world full of joy...
-
- Learning poster
- Posts: 56
- Joined: Tue Jun 13, 2006 5:18 pm
- Location: (CSE, SUST) Sylhet, Bangladesh
- Contact:
Anybody Help PLZ about 10192
I am also getting WA for this problem, but i think my algo and code is OK.
I also checked my code for some I/O. It gives me correct output.
Then wheres the worng.
Here my code:
I also checked my code for some I/O. It gives me correct output.
Then wheres the worng.
Here my code:
Code: Select all
Removed after got AC
Last edited by Mushfiqur Rahman on Sat Mar 03, 2007 3:09 pm, edited 1 time in total.
-
- Learning poster
- Posts: 56
- Joined: Tue Jun 13, 2006 5:18 pm
- Location: (CSE, SUST) Sylhet, Bangladesh
- Contact:
10192 WA help!
I think my algorithm is correct but get WA! I check many times but cant find where the problem is. I will be very grateful if any suggestion.
Code: Select all
#include <cstdlib>
#include <stdio.h>
#include <iostream>
#include <string>
#define MAXCITY 102
using namespace std;
int c[MAXCITY][MAXCITY];
char s1[MAXCITY], s2[MAXCITY];
void LCS(int time){
int m = strlen(s1);
int n = strlen(s2);
int i, j;
for(i=0; i<MAXCITY; i++)
for(j=0; j<MAXCITY; j++)
c[i][j] = 0;
for(i=0; i<m; i++){
for(j=0; j<n; j++){
if(s1[i] == s2[j]) c[i][j] = c[i-1][j-1]+1;
else c[i][j] = (c[i][j-1]>c[i-1][j])? c[i][j-1] : c[i-1][j];
}
}
cout << "Case #" << time << " : you can visit at most " << c[m-1][n-1] << " cities." << endl;
}
int main(int argc, char *argv[])
{
int time;
for(time=1; ; time++){
gets(s1);
if(!(strcmp(s1, "#"))) return 0;
gets(s2);
LCS(time);
}
return EXIT_SUCCESS;
}
My source code.
I was solve this problem with Dynamic Algorithm
Thank you.
I was solve this problem with Dynamic Algorithm
Code: Select all
#include<stdio.h>
#include<string.h>
void main(){
char a[1001];
char b[1001];
int tb[1001][1001]={0,};
int alen, blen;
int i, j;
char dap[101]={0,};
int cnt;
int t=1;
while(1){
gets(a);
if(a[0] == '#')
break;
gets(b);
alen = strlen(a);
blen = strlen(b);
for(i=alen;i>=0;i--)
a[i] = a[i-1];
for(i=blen;i>=0;i--)
b[i] = b[i-1];
for(i=1;i<=alen;i++){
for(j=1;j<=blen;j++){
if(a[i] == b[j]){
tb[i][j] = tb[i-1][j-1]+1;
}
else{
tb[i][j] = tb[i-1][j-1];
if(tb[i][j] < tb[i][j-1])
tb[i][j] = tb[i][j-1];
if(tb[i][j] < tb[i-1][j])
tb[i][j] = tb[i-1][j];
}
}
}
cnt = tb[alen][blen];
printf("Case #%d: you can visit at most %d cities.\n",t,cnt);
t++;
}
}
10192 - CE
Can anyone tell why CE in this prog?
#include<stdio.h>
#include<string.h>
char str1[100], str2[100];
int test_case = 1;
int m, n;
int i, j;
int c[110][110];
void LCScount()
{
m = strlen(str1);
n = strlen(str2);
for(i=0; i<=m; ++i)
c[i][0] = 0;
for(i=0; i<=n; ++i)
c[0][i] = 0;
for(i=1; i<=m; ++i)
{
for(j=1; j<=n; ++j)
{
if( str1[i-1] == str2[j-1] )
{
c[i][j] = c[i-1][j-1] + 1;
}
else if( c[i-1][j] >= c[i][j-1] )
{
c[i][j] = c[i-1][j];
}
else
{
c[i][j] = c[i][j-1];
}
}
}
printf("Case #%d: you can visit at most %d cities.\n", test_case++, c[m][n]);
}
int main()
{
//freopen("in.txt", "r" ,stdin);
while(1)
{
scanf("%s %s", str1, str2);
if( !( strcmp (str1,"#") ) )
return;
LCScount();
//printf("%s\n",str1);
}
return 0;
}
#include<stdio.h>
#include<string.h>
char str1[100], str2[100];
int test_case = 1;
int m, n;
int i, j;
int c[110][110];
void LCScount()
{
m = strlen(str1);
n = strlen(str2);
for(i=0; i<=m; ++i)
c[i][0] = 0;
for(i=0; i<=n; ++i)
c[0][i] = 0;
for(i=1; i<=m; ++i)
{
for(j=1; j<=n; ++j)
{
if( str1[i-1] == str2[j-1] )
{
c[i][j] = c[i-1][j-1] + 1;
}
else if( c[i-1][j] >= c[i][j-1] )
{
c[i][j] = c[i-1][j];
}
else
{
c[i][j] = c[i][j-1];
}
}
}
printf("Case #%d: you can visit at most %d cities.\n", test_case++, c[m][n]);
}
int main()
{
//freopen("in.txt", "r" ,stdin);
while(1)
{
scanf("%s %s", str1, str2);
if( !( strcmp (str1,"#") ) )
return;
LCScount();
//printf("%s\n",str1);
}
return 0;
}
10192 - Vacation
Sorry, I've looked at the old topics for this problem and read the code in those topics but I still don't understand why my code repeatedly gets me WA. I'm just using the standard LCS algorithm. Could someone please help me?
Thanks in advance.
Code: Select all
#include <stdio.h>
#include <string.h>
#define SIZE 110
#define MAX(a, b) (a > b ? a : b)
static long best[SIZE][SIZE];
static char line1[SIZE], line2[SIZE];
static int len1, len2;
static int i, j;
static int num;
int main (){
gets (line1);
num = 0;
while (strcmp (line1, "#") != 0){
gets (line2);
num++;
len1 = strlen (line1);
len2 = strlen (line2);
for (i = 0; i < len1 + 1; i++)
best[i][0] = 0;
for (j = 0; j < len2 + 1; j++)
best[0][j] = 0;
for (i = 1; i < len1 + 1; i++)
for (j = 1; j < len2 + 1; j++)
if (line1[i] == line2[j])
best[i][j] = best[i - 1][j - 1] + 1;
else
best[i][j] = MAX(best[i - 1][j], best[i][j - 1]);
printf ("Case #%d: you can visit at most %ld cities.\n", num, best[len1][len2]);
gets (line1);
}
return 0;
}