OJ Board

The Online Judge board
https://onlinejudge.org/board/

10252 - Common Permutation

https://onlinejudge.org/board/viewtopic.php?t=1899

Page 6 of 11

Posted: Thu May 13, 2004 4:10 am
by midra
thank you so much!!
I finally understand! :D :D :D

Byee!

Hi

Posted: Thu May 13, 2004 10:28 am
by sumankar
Midra,

Good, now can you remove the code :wink:

10252

Posted: Fri Jul 02, 2004 8:40 pm
by mooseelkdog
Can't seem to figure out why I get a wrong answer to this problem, I find the common letters to the words, and output the multiples of each letter occuring in both words, I output blank lines for neither word having common letters and for a blank input of the second word, IS IT POSSIBLE TO HAVE AN INITIAL BLANK LINE INPUT?

Thank you

Posted: Fri Jul 02, 2004 9:29 pm
by mooseelkdog
for clarity I am posting my sample input:

<blank line>
icky
pretty
women
walking
down
the
street
meningitis
frontal
yelp
<blank line>
verbatim
greater
prettywoman
walkingdown
inging
singing
ab
ba
ab
cd
cat
bat

and my output generated:

<blank line>
e
nw
et
nt
<blank line>
aert
anow
ggiinn
ab
<blank line>
at

for extra clarity, <blank line> signifies carriage return

thanks again

Posted: Wed Aug 11, 2004 2:19 pm
by tetuya
Hi mooseelkdog.
Your output is same with mine.
you may have other wrong code.

Posted: Sat Sep 25, 2004 2:24 am
by noren
I'd say that case matters. After I added tolower() I got accepted. There must be something wrong either in the spec, or in the testdata. However you can print the letters in lowercase. Just convert the indata to lowercase.
/johan

Posted: Wed Oct 06, 2004 2:31 pm
by Arm.Turbo
My outputs for all tests from this board the same with AC solutions. I try to use tolower() but it's WA anyway. What's the problem?

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

int main ()
{
	char tmp1[1024];
	char tmp2[1024];
	char ttmp1['z'-'a'+1];
	char ttmp2['z'-'a'+1];
	int j, sl1, sl2, k;

	#ifndef ONLINE_JUDGE 
	freopen("Debug/input.txt", "r", stdin); 
	//freopen("Debug/output.txt", "w", stdout); 
	#endif 

	while(1)
	{
		if (gets(tmp1) == NULL)
			break;
		if (gets(tmp2) == NULL)
			break;
		sl1 = strlen(tmp1);
		sl2 = strlen(tmp2);
		for (j = 0; j < 'z'-'a'+1; j++)
		{
			ttmp1[j] = 0;
			ttmp2[j] = 0;
		}
		for (j = 0; j <sl1; j++)
		{
			ttmp1[tolower(tmp1[j])-'a']++;
		}
		for (j = 0; j <sl2; j++)
		{
			ttmp2[tolower(tmp2[j])-'a']++;
		}
		for (j = 0; j < 'z'-'a'+1; j++)
		{
			if (ttmp2[j] < ttmp1[j])
				ttmp1[j] = ttmp2[j];
		}
		for (j = 0; j < 'z'-'a'+1; j++)
		{
			for (k =0; k < ttmp1[j]; k++)
			{
				printf("%c", j+'a');
			}
		}

		printf("\n");
	}
	return 0;
}

Posted: Wed Oct 13, 2004 4:49 pm
by burgerman
I try to use tolower() but it's WA anyway.
Your problem is not upper-case input. The following code should cause a floating point exception should any uppercase letters occur:

[cpp]char c
if (c >= 'A' || c <= 'Z'){
int x = 6 / 0; //will cause fpe should a character from A to Z be encountered
}[/cpp]
and none occurred when I tried it.

Your problem would probably be found in the statement,
The input file contains several cases, each case consisting of two consecutive lines.
(tolower may even cause further problems, depending on the judge's implementation)

10252

Posted: Fri Jan 28, 2005 4:24 am
by midra
Why this qsort function doesn't work

Posted: Sun Feb 13, 2005 2:27 pm
by mohiul alam prince
hi
i have changed ur code and got AC
but u have to understand what were the problems in your code

MAP

Code: Select all

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

int funcion(const void *a,const void *b){ 
return *(char*)a-*(char*)b; 
} 

int main() 
{ 
  char a[1002],b[1002],x[1002]; 
  int i,j,len1,len2,ind; 
  while(gets(a)){
	  gets(b);
	  if ( strlen(a) == 0 || strlen(b) == 0 ){printf("\n");continue;}
      for (i=0;i<=ind;i++)  x[i]=0; 
      len1=strlen(a);len2=strlen(b); 
      ind=0; 
      for(i=0;i<len1;i++) 
          for(j=0;j<len2;j++){ 
              if(a[i]==b[j]){ 
                  x[ind]=b[j];              
                  b[j]=0; 
                  ind++; 
                  break; 
              } 
          } 
		  x[ind] = NULL;
		  qsort(x,ind,sizeof(x[0]),funcion); 
		  printf("%s\n",x); 
  }    
  return 0; 
}

Something wrong with judge?

Posted: Wed Apr 13, 2005 6:20 am
by Kentaro
Important Edit: A straight LCS-based solution worked like a charm and I've finally gotten AC for this problem. But I wonder what was wrong with this program?

The Programming Challenges judge accepts my program just fine, which seems to work exactly according to the problem specification (it assumes it is working with 0-1000 lowercase letters in each string and is correct for every single test case I could throw at it) but the UVa judge won't accept it.

I think the UVa judge is playing a terrible trick on all of us and I'm trying to get to the bottom of it... :-?

Code: Select all

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;

const bool DEBUG = false;

int main() {
	string word1, word2;
	while (getline(cin, word1) && getline(cin, word2)) {
		
		if (DEBUG) {
			cout << "First line is: " << word1 << endl;
			cout << "Second line is: " << word2 << endl;
		}
		
		// Sort the letters in each word
		sort(word1.begin(), word1.end());
		sort(word2.begin(), word2.end());
		
		// Make sure that the shortest word is word1
		if (word1.size() > word2.size()) {
			string temp = word1;
			word1 = word2;
			word2 = temp;
		}
		
		if (DEBUG) {
			cout << word1 << endl;
			cout << word2 << endl;
		}
		
		int w1_place = 0;
		int w2_place = 0;
		int w2_last = 0;
		while (w1_place < word1.size() && w2_last < word2.size()) {
			if (word1[w1_place] == word2[w2_place]) {
				cout << word1[w1_place];
				w1_place++;
				w2_place++;
				w2_last = w2_place;
			}
			else {
				if (w2_place < word2.size()) w2_place++;
				else {
					w1_place++;
					w2_place = w2_last;
				}
			}
		}
		cout << endl;
	}
}
Edited to remove some extra emoticons that appeared in the post.
Another fixes a minor issue in the code. I didn't submit the code with any syntax errors, but I have been changing it a lot trying to get AC, so in revising the code and reverting it back again I've made some small mistakes.

10252 compiler error

Posted: Wed Mar 22, 2006 9:10 pm
by AhlyM
hi programmers.
This code take compiler error i need someone to tell me where is the error?

Code: Select all

program str (input,output);
uses strings;
type
   arr=array of char;
var
   x,y,r,z:arr;
   s1,s2:string;
   i,l1,l2,b,g,c,v,s:integer;
function bubble (r:arr;s:integer):arr;
var
   i,j:integer;
   t:char;
begin
     for i:= 1 to length(r) do
     begin
          for j:= 1 to length(r)-1 do
          begin
               if r[j] > r[j+1] then
               begin
               t:=r[j];
               r[j]:=r[j+1];
               r[j+1]:=t;
               end;
          end;
     end;
     bubble:=r;
end;
begin
     while not eof(input) do
     begin
     c:=1;
     s:=1;
     readln(s1);
     readln(s2);
     l1:=length(s1);
     l2:=length(s2);
     setlength(x, l1);
     setlength(y, l2);
     setlength(r, 0);
     setlength(z, 100);
     for i:=1 to l1 do
     begin
          x[i]:=s1[i];
     end;
     for i:=1 to l2 do
     begin
          y[i]:=s2[i];
     end;

     if l1>l2 then
     begin
          for g:=1 to l1 do
          begin
               for v:=1 to l1 do
               begin
                    if y[c]=x[v] then
                    begin
                         z[s]:=x[v];
                         s:=s+1;
                         break;
                    end;
               end;
               c:=c+1
          end;
     end
     else
     begin
     for g:=1 to l2 do
          begin
               for v:=1 to l2 do
               begin
                    if x[c]=y[v] then
                    begin
                         z[s]:=y[v];
                         s:=s+1;
                         break;
                    end;
               end;
               c:=c+1
          end;
     end;
     setlength(r, s);
     for b:=1 to s do
     begin
         r[b]:=z[b];
     end;
     r:=bubble(r,s);
     for b:=2 to s do
     begin
          write(r[b]);
     end;
     setlength(z, 0);
     setlength(r, 0);
     setlength(x, 0);
     setlength(y, 0);
     writeln;
     writeln;
     end;
end.

10252 - I got TLE..

Posted: Tue Mar 28, 2006 7:03 am
by mosaick2
Actually, I can't understand what's wrong in my method.
Who can give advice to me?

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int CHARSIZE = 26;

void checkMap(char *lCase, int *map);

int main()
{
	char lCase1[1000] = {0,};
	char lCase2[1000] = {0,};
	int map1[CHARSIZE] = {0,};		// for masking flags.
	int map2[CHARSIZE] = {0,};		// for masking flags.

	do {
		/* Clear */
		memset(map1, 0x00, CHARSIZE*4);
		memset(map2, 0x00, CHARSIZE*4);
		memset(lCase1, 0x00, 1000);
		memset(lCase2, 0x00, 1000);

		/* Input */
		cin.getline(lCase1, 1000);
		cin.getline(lCase2, 1000);

		/* Processing */
		checkMap(lCase1, map1);
		checkMap(lCase2, map2);

		/* Output */
		for(int i=0; i < CHARSIZE; i++) 
		{
			if((map1[i] >= 1) && (map2[i] >= 1)) {
				int small = (map1[i] > map2[i]) ? map2[i] : map1[i];
				for(int j=0; j < small; j++) 
					printf("%c", i+97);
			}
		}
		cout << endl;

	} while(!cin.eof());

	return 0;
}

void checkMap(char *lCase, int *map)
{
	int ix=0;
	while(lCase[ix] != 0)
	{
		switch (lCase[ix])
		{
			case 'a': map[0] += 1; break; case 'b': map[1] += 1; break;
			case 'c': map[2] += 1; break; case 'd': map[3] += 1; break;
			case 'e': map[4] += 1; break; case 'f': map[5] += 1; break;
			case 'g': map[6] += 1; break; case 'h': map[7] += 1; break;
			case 'i': map[8] += 1; break; case 'j': map[9] += 1; break;
			case 'k': map[10] += 1; break;case 'l': map[11] += 1; break;
			case 'm': map[12] += 1; break;case 'n': map[13] += 1; break;
			case 'o': map[14] += 1; break;case 'p': map[15] += 1; break;
			case 'q': map[16] += 1; break;case 'r': map[17] += 1; break;
			case 's': map[18] += 1; break;case 't': map[19] += 1; break;
			case 'u': map[20] += 1; break;case 'v': map[21] += 1; break;
			case 'w': map[22] += 1; break;case 'x': map[23] += 1; break;
			case 'y': map[24] += 1; break;case 'z': map[25] += 1; break;
		}
		ix++;
	}
}

Posted: Thu Mar 30, 2006 9:58 am
by Amir Aavani
try to change
char lCase1[1001] = {0,};
char lCase2[1001] = {0,};
In checkMap, you go till a 0 is meeted, what if the inputs string's length are exactly 1000. you missed the trailing 0.

Thx, But it's not the reason.

Posted: Fri Mar 31, 2006 6:08 am
by mosaick2
Amir Aavani wrote:try to change
char lCase1[1001] = {0,};
char lCase2[1001] = {0,};
In checkMap, you go till a 0 is meeted, what if the inputs string's length are exactly 1000. you missed the trailing 0.
I've got your advice.
I think It's also my mistake.
But, I got TLE until now.
I think I have the other problem in my code.
All times are UTC+02:00
Page 6 of 11

Powered by phpBB® Forum Software © phpBB Limited