195 - Anagram

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

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 195 - Anagram(WA)

Post by brianfry713 » Fri Aug 30, 2013 9:59 pm

Input:

Code: Select all

1
AaBb
AC output:

Code: Select all

AaBb
AabB
ABab
ABba
AbaB
AbBa
aABb
aAbB
aBAb
aBbA
abAB
abBA
BAab
BAba
BaAb
BabA
BbAa
BbaA
bAaB
bABa
baAB
baBA
bBAa
bBaA
Check input and AC output for thousands of problems on uDebug!

shikhorroy
New poster
Posts: 27
Joined: Sat Jul 27, 2013 3:52 am

Re: 195 - Anagram(WA)

Post by shikhorroy » Sat Aug 31, 2013 7:51 am

O...thanks.

raihan_sust05
New poster
Posts: 5
Joined: Fri Nov 22, 2013 6:34 pm

WA in 195 - Anagram

Post by raihan_sust05 » Sun Feb 16, 2014 2:02 pm

i am already fed up with this :evil: anyone help me please

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>


#define pi acos(0)
#define inf 1<<30
#define max 60
#define sz 60
#define true 1
#define false 0
#define pb(a) push_back(a)
#define size(e) (int)e.size()
#define clr(a,b) memset(a,b,sizeof(a))


typedef long long int ll;

using namespace std;
char  in[sz];
/* lch = lower case character, uch = uppercase character */

bool got[sz];

/* glch = is the lower character visited before, guch = is the uppercase character visited before */

int strln, n;
char out[sz];

void recur(int depth, int taken);
void order();

// FILE *fpt;
// fpt = fopen("tst.dat", "w");



int main()
{
//    freopen("195_in.txt", "r", stdin);
//    freopen("195_out.txt", "w", stdout);
    int i, j, tst;

    scanf("%d", &tst);

    while(tst > 0)
    {
        scanf(" %s", in);

        strln = strlen(in);

        order();
        clr(got, 0);
        recur(0, 0);

        --tst;
  //        puts("");
    }
    return 0;
}

void recur(int depth, int taken)
{
    int i = 0;

    if(depth == strln)
    {
        out[strln] = '\0';
        puts(out);
    }

    bool guch[sz], glch[sz];
    clr(glch, 0);
    clr(guch, 0);

    /* glch  && guch is here to ensure that no repeatation is happened */

    while(in[i] != '\0')
    {
        if(!got[i])
        {
            if(in[i] >= 'A' && in[i] <= 'Z')
            {
                if(!guch[in[i] - 'A'])
                {
                    out[taken] = in[i];
                    guch[in[i] - 'A'] = true;
                    got[i] = true;
                    recur(depth + 1, taken + 1);
                    got[i] = false;
                }

            }

            else if(in[i] >= 'a' && in[i] <= 'z')
            {
                if(!glch[in[i] - 'a'])
                {
                    out[taken] = in[i];
                    glch[in[i] - 'a'] = true;
                    got[i] = true;
                    recur(depth + 1, taken + 1);
                    got[i] = false;
                }
            }
        }

        ++i;
    }

    return;
}

void order()
{
    int i, j;


    for(i = 0; i < strln - 1; ++i)
    {
        for(j = i + 1; j < strln; ++j)
        {
            if((toupper(in[i]) == toupper(in[j])) &&(in[i] > in[j]))
                swap(in[i], in[j]);
            else if(toupper(in[i]) > toupper(in[j]))
                swap(in[i], in[j]);
        }
    }
//    puts("");
//    puts("");
//    puts("");
    return;
}
thanks in advance

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 195 - Anagram

Post by brianfry713 » Tue Feb 18, 2014 8:15 pm

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

Angry Bird
New poster
Posts: 21
Joined: Mon Apr 08, 2013 8:38 am

Re: 195 - WA again and again

Post by Angry Bird » Mon Mar 10, 2014 10:59 pm

Why giving Output Limit????? :roll:

Code: Select all

#include <bits/stdc++.h>
using namespace std;


#define lop(i,n) for(__typeof(n) i=0; i<(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
#define mem(t) memset((t), 0, sizeof(t))
typedef long long int64;
typedef long double d64;
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define PI 3.1415926535897932384626433832
#define INF (1<<30)
#define eps 1e-8
#define pb push_back
#define ppb pop_back
#define bg begin
#define pf printf
#define sf scanf
#define inpc(ch) scanf("%c",&ch)
#define inp(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d%d",&x,&y)
#define Get(s) getline(cin,s)
#define Sort(v) sort(v.begin(),v.end());
#define out(x) printf("%d\n",x);
#define TC printf("Case %d: ",++cas);
#define TC1 printf("CASE# %d:\n",++cas);

template< class T > T _abs(T n) { return (n < 0 ? -n : n); }
template< class T > T sq(T n) { return n*n; }
template< class T > T _max(T a, T b) { return (!(a < b) ? a : b); }
template< class T > T _min(T a, T b) { return (a < b ? a : b); }
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > bool inside(T a, T b, T c) { return a<=b && b<=c; }
template< class T > void setmax(T &a, T b) { if(a < b) a = b; }
template< class T > void setmin(T &a, T b) { if(b < a) a = b; }
template< class T > T power(T N,T P){ if(P==0) return 1; return (P==1)? N: N*power(N,P-1); }

char arr[100];
vector<char>result;
int taken[100],i;


void call(int n)
{
    if(result.size()==n)
    {
        lop(i,n)
        {
            pf("%c",result[i]);
        }
        pf("\n");
        return;
    }

    lop(i,n)
    {
        if(taken[i]==0)
        {
            taken[i]=1;
            result.push_back(arr[i]);
            call(n);
            taken[i]=0;
            result.pop_back();
        }
    }
}

int main()
{
    mem(taken);
    char ch;
    int n;
    inp(n);
    string str;

    lop(i,n)
    {
       cin>>str;
       sort(str.begin(),str.end());

       lop(j,str.size())
       {
           arr[j]=str[j];
       }
       call(str.size());
    }

    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 195 - WA again and again

Post by brianfry713 » Tue Mar 11, 2014 9:37 pm

Try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!

rloursua
New poster
Posts: 4
Joined: Tue Feb 11, 2014 5:52 pm

Re: 195 - Anagram

Post by rloursua » Sun Mar 16, 2014 8:14 am

Please help me.
I really have no idea why I'm getting WA.
I tried removing and placing back the blank link at the end of the output but both returned as WA

Code: Select all

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

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

int main()
{
    char letters[1024];
    int wordSize = 0;
    int cases = 0;
    int i = 0;

    scanf("%d",&cases);

    for(i=0;i<cases;i++)
    {
        char orig[1024];
        scanf("%s",letters);
        int wordSize = strlen(letters);
        qsort(letters,wordSize,sizeof(char),compare);
        strcpy(orig,letters);
        do
        {
            printf("%s\n",letters);
            std::next_permutation(letters,letters+wordSize);
        }
        while(strcmp(letters,orig));

    }

    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 195 - Anagram

Post by brianfry713 » Mon Mar 17, 2014 9:47 pm

Try the I/O in this thread.
Check input and AC output for thousands of problems on uDebug!

Aurango
New poster
Posts: 4
Joined: Sun Mar 23, 2014 2:07 pm

195 - Anagram?? why wrong answer???

Post by Aurango » Fri Mar 28, 2014 1:26 pm

my code for UVA 195 problem run well but showing wrong answer in uva online judge..plz help???

Code: Select all

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

class Main {

    public static void main(String[] args)throws IOException {

        Scanner sc=new Scanner(System.in);
        int test=sc.nextInt();
        sc.nextLine();
        String str;
        char[] c;
        while(test!=0)
        {
            str=sc.nextLine();
            c=str.toCharArray();
            Arrays.sort(c);
            do{
                System.out.println(c);
            }while(nextPermutation(c));
            test--;
        }
    }
    
    static boolean nextPermutation(char[] array) {
        int i = array.length - 1;
        while (i > 0 && array[i - 1] >= array[i]) {
            i--;
        }
        if (i == 0) {
            return false;
        }

        int j = array.length - 1;
        while (array[j] <= array[i - 1]) {
            j--;
        }
        char temp = array[i - 1];
        array[i - 1] = array[j];
        array[j] = temp;

        j = array.length - 1;
        while (i < j) {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
        return true;
    }
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 195 - Anagram?? why wrong answer???

Post by brianfry713 » Fri Mar 28, 2014 10:29 pm

Check input and AC output for thousands of problems on uDebug!

Aurango
New poster
Posts: 4
Joined: Sun Mar 23, 2014 2:07 pm

Re: 195 - Anagram?? why wrong answer???

Post by Aurango » Fri Mar 28, 2014 11:28 pm

Sry,i dnt get anything.. :(

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 195 - Anagram?? why wrong answer???

Post by brianfry713 » Mon Mar 31, 2014 11:13 pm

Try running your code on the input I posted in that thread.
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 195 - Anagram

Post by uDebug » Tue Jun 03, 2014 12:16 pm

Replying to follow the thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

fresher96
New poster
Posts: 25
Joined: Wed Sep 03, 2014 8:50 am

Re: 195 - Anagram

Post by fresher96 » Sun Sep 28, 2014 1:17 am

hey guys
how about this trick it may help :D

Code: Select all

int alph_ord(char c)
{
	if(isupper(c))
	{
		return (c-'A')*2;
	}
	else
	{
		return (c-'a')*2+1;
	}
}
bool cmp(const char &a,const char &b)
{
	return alph_ord(a) < alph_ord(b);
}

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

Re: 195 - Anagram!!!! WA

Post by LazyTym » Sun Nov 09, 2014 10:33 pm

please help me......what is the problem in my code???? Every time getting Wrong Ans!!!!!!!

Code: Select all

#include<iostream>
#include<cstring>
#include<map>


using namespace std;

map <char,int>M;

void Swap (char* a, char* b) {
    char t = *a;
    *a = *b;
    *b = t;
}


void lexicographical_Permutations(char str[],int n)
{
    for(int i=0;i<n;i++) {

        for(int j=i+1;j<n;j++) {

           if(M[str[i]]>M[str[j]]) {
              Swap(&str[i],&str[j]);
           }
        }
    }
    bool isFinished=false;
    char temp;

    while(!isFinished) {
        cout<<str<<endl;

        int i;
        for (i=n-2;i>=0;--i ) {
            if (M[str[i]]<M[str[i+1]]) break;
        }

        if(i==-1) isFinished=true;

        else {

            int j=n-1;
            while(M[str[j]]<=M[str[i]]) j--;

            Swap(&str[j],&str[i]);

            j=n-1;
            i=i+1;
            while(i<j) {
                Swap(&str[i],&str[j]);
                i++;
                j--;
            }
        }
    }
}

int main()
{
    char str[100];
    int test;
M['A']=1;
M['a']=2;
M['B']=3;
M['b']=4;
M['C']=5;
M['c']=6;
M['D']=7;
M['d']=8;
M['E']=9;
M['e']=10;
M['F']=11;
M['f']=12;
M['G']=13;
M['g']=14;
M['H']=15;
M['h']=16;
M['I']=17;
M['i']=18;
M['J']=19;
M['j']=20;
M['K']=21;
M['k']=22;
M['L']=23;
M['l']=24;
M['m']=25;
M['m']=26;
M['N']=27;
M['n']=28;
M['O']=29;
M['o']=30;
M['P']=31;
M['p']=32;
M['Q']=33;
M['q']=34;
M['R']=35;
M['r']=36;
M['S']=37;
M['s']=38;
M['T']=39;
M['t']=40;
M['U']=41;
M['u']=42;
M['V']=43;
M['v']=44;
M['W']=45;
M['w']=46;
M['X']=47;
M['x']=48;
M['Y']=49;
M['y']=50;
M['Z']=51;
M['z']=52;

    cin>>test;
    while(test--) {
       cin>>str;
       int len=strlen(str);
       lexicographical_Permutations(str,len);
    }
    return 0;
}


Post Reply

Return to “Volume 1 (100-199)”