10192 - Vacation

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

rafaelsilva
New poster
Posts: 1
Joined: Sun Sep 18, 2005 8:40 pm

10192 Vacation Problem - Wrong Answer

Post by rafaelsilva » Sun Sep 18, 2005 8:43 pm

I

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

10192......OLE!!!!

Post by Wei-Ming Chen » Sun Nov 13, 2005 3:32 pm

thank you
Last edited by Wei-Ming Chen on Mon Nov 14, 2005 2:38 pm, edited 1 time in total.

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Sun Nov 13, 2005 6:06 pm

I think that you should change your input reading method. You can read one line using gets(). I have changed your code using gets() and it was not OLE anymore.

Hope it helps :D

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Mon Nov 14, 2005 7:06 am

Yes...you are right
I think I should change my method

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Wed May 10, 2006 7:28 am

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 :roll: :P
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...

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Fri Jun 30, 2006 7:52 pm

hello, your algo seems to be right...
so try to solve it in C instead Java
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

Anybody Help PLZ about 10192

Post by Mushfiqur Rahman » Fri Jul 28, 2006 9:23 pm

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:

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.

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

Post by Mushfiqur Rahman » Sat Jul 29, 2006 7:06 pm

Yes Lastly I got AC. The wrong was that in my while loop . I should use gets() rather than scanf() in while and then check the first string which will contain "#" string

Thanks for every body.
Mushfiqur Rahman

nicky
New poster
Posts: 1
Joined: Fri Aug 18, 2006 10:27 am

10192 WA help!

Post by nicky » Fri Aug 18, 2006 10:33 am

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;
}

Bluefin
New poster
Posts: 20
Joined: Sat Jul 08, 2006 3:39 pm
Contact:

Post by Bluefin » Fri Aug 18, 2006 1:43 pm

I think you can simply solve Q10192 bu using LCS algorithm ~~
There's no trick in this problem. :lol:

Check your code one more time ~~
If you still can't find the error, send PM to me and I'll send my ACC code to you !!

But I think there isn't much difference between our codes ~~

Hope it will help !! :D
"It's nice to be important, but it's more important to be nice"

http://bluefintuna.wordpress.com/

justjoy
New poster
Posts: 2
Joined: Mon Aug 28, 2006 9:05 am
Location: South Korea
Contact:

Post by justjoy » Mon Aug 28, 2006 1:46 pm

My source code.
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++;
	}
}

Thank you.

Bluefin
New poster
Posts: 20
Joined: Sat Jul 08, 2006 3:39 pm
Contact:

Post by Bluefin » Tue Aug 29, 2006 8:04 am

I think it's better not to post your code ~~
Because that way anyone can get ACC immediately by posting your code.
That's not fair !!
So please delete it ~~ :D
"It's nice to be important, but it's more important to be nice"

http://bluefintuna.wordpress.com/

farhan
New poster
Posts: 2
Joined: Fri Dec 07, 2007 7:59 pm
Location: Bangladesh

10192 - CE

Post by farhan » Sun Dec 16, 2007 1:50 pm

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;
}

Samiul
New poster
Posts: 36
Joined: Thu Dec 13, 2007 3:01 pm

Post by Samiul » Tue Dec 25, 2007 8:47 am

In int main() you have two returns, among which one is not returning anything. This gave compile error in my compiler VS 2005.

Farnak
New poster
Posts: 4
Joined: Wed May 24, 2006 9:15 pm
Location: Windsor, Canada

10192 - Vacation

Post by Farnak » Wed Feb 06, 2008 5:29 am

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?

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;
}
Thanks in advance.

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest