[UVa] 524 - Prime Ring Problem

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 524 - Prime Ring Problem
Source            : UVa Online Judge
Category          : Backtrack
Algorithm         : Backtrack
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
bool vis[20];
vector <int> List;
bool primeList[50];
 
bool isPrime(int n)
{
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n%2 == 0) return false;
    for (int i = 3; i*i <= n; i++)
        if (n%i == 0) return false;
    return true;
}
 
void SEIVE()
{
    for (int i = 0; i < 50; i++)
        primeList[i] = isPrime(i);
}
 
void backTrack(int last, int n)
{
    if (List.size() == n)
    {
        int sum= List[n-1] + 1;
        if (primeList[sum] == 0) return;
        for (int i = 0; i < n; i++)
        {
            printf("%d", List[i]);
            printf(i == n-1 ? "\n" : " ");
        }
        return;
    }
 
    for (int i = 2; i <= n; i++)
    {
        int sum = i + last;
        if (vis[i] || !primeList[sum]) continue;
 
        vis[i] = 1;
        List.push_back(i);
 
        backTrack(i, n);
 
        vis[i] = 0;
        List.pop_back();
    }
}
 
int main()
{
    SEIVE();
 
    int n;
    int tcase = 1;
    while (scanf("%d", &n) == 1)
    {
        fill(begin(vis), end(vis), 0);
        List.clear();
        List.push_back(1);
        if (tcase > 1) puts("");
        printf("Case %d:\n", tcase++);
        backTrack(1, n);
    }
}
 

[UVa] 195 Anagram

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 195 Anagram
Source            : UVa Online Judge
Category          : Backtrack
Algorithm         : Backtrack
Verdict           : Accepted 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace:: std;
using namespace:: __gnu_pbds;
 
#define READ                                 freopen("in.txt", "r", stdin)
#define WRITE                                freopen("out.txt", "w", stdout)
 
#define FAST                                 ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
 
 
#define All(v)                               v.begin(), v.end()
#define SZ(a)                                a.size()
#define Sort(v)                              sort(All(v))
#define ED(v)                                Sort(v), v.erase(unique(All(v), v.end())
#define Common(a, b)                         Sort(v), Sort(b), a.erase(set_intesection(All(a), All(b), a.begin(), a.end()))
#define UnCommon(a, b)                       Sort(v), Sort(b), a.erase(set_symmetric_difference(All(a), All(b), All(a)))
 
 
#define max3(a, b, c)                        max(a, max(b, c))
#define min3(a, b, c)                        min(a, min(b, c))
#define maxAll(v)                            *max_element(All(v))
#define minAll(v)                            *min_element(All(v))
 
 
#define AllUpper(a)                          transform(All(a), a.begin(), :: toupper)
#define AllLower(a)                          transform(All(a), a.begin(), :: tolower)
#define Rev(a)                               reverse(All(a))
 
 
 
#define memo(a, b)                           memset(a, b, sizeof(a))
 
#define ff                                   first
#define ss                                   second
#define PII                                  pair <int, int>
 
#define inf                                  1 << 28
 
template <typename T>string toString (T Number)    { stringstream st; st << Number; return st.str(); }
int toInteger (string s)                           { int p; istringstream st(s); st>>p ; return p; }
int Set(int N, int pos)                            { return N = N | (1 << pos); }
int Reset(int N, int pos)                          { return N = N & ~(1 << pos); }
bool Check(int N, int pos)                         { return (bool)(N & (1 << pos)); }
 
 
//int dr[] = {1, -1, 0, 0};                // 4 Direction
//int dc[] = {0, 0, 1, -1};
 
//int dr[] = {0, 0, 1, -1, 1, 1, -1, -1};  // 8 Direction
//int dc[] = {1, -1, 0, 0, 1, -1, 1, -1};
 
//int dr[] = {-1, 1, -2, -2, -1, 1, 2, 2}; // knight Moves
//int dc[] = {-2, -2, -1, 1, 2, 2, 1, -1};
 
 
#define Exp                                  exp(1.0)
#define PIE                                  2*acos(0.0)
#define Sin(a)                               sin(((a)*PI)/180.0)
#define mod                                  1000000007
#define EPS                                  1e-9
 
#define sqr(a)                               ((a)*(a))
#define gcd(a,b)                              __gcd(a,b)
#define lcm(a,b)                             (a*(b/gcd(a,b)))
 
 
#define trace1(x)                           cerr << #x << ": " << x << endl;
#define trace2(x, y)                        cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)                     cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)                  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)               cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f)            cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
 
 
typedef long long                            ll;
typedef vector <int>                         VII;
typedef vector <ll>                          VLL;
 
#define PB                                   push_back
#define MK                                   make_pair
 
 
inline int nxtINT()                            { int a; scanf("%d", &a); return a; }
inline int nxtLL()                             { ll a; scanf("%lld", &a); return a; }
inline int nxtDD()                             { double a; scanf("%lf", &a); return a; }
 
#define PF                                   printf
#define PFTC1(t)                             printf("Case %d: ", t)
#define PFTC2(t)                             printf("Case #%d: ", t)
#define PFII(n)                              printf("%d", n)
#define PFLL(n)                              printf("%lld", n)
 
#define NEWLINE                              puts("")
 
static const int mx = 100000 + 5;
static const int MAXN = 1e6 + 5;
static const int MAXLG = 15;
 
bool vis[200];
vector <char> vec;
string str;
int len;
 
void PERMUTATION(string &str, int pos, int n)
{
    if (vec.size() == n)
    {
        for (char ch : vec) cout << ch;
        cout << endl;
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (vis[i]) continue;
 
        vec.push_back(str[i]);
        vis[i] = 1;
 
        PERMUTATION(str, pos+1, n);
 
        vec.pop_back();
        vis[i] = 0;

        while (i + 1 < n && str[i] == str[i+1]) i++;
    }
}
 
 
 
int main()
{
    #ifdef dip_BRUR
        freopen("in.txt", "r", stdin);
        //WRITE;
    #endif // dip_BRUR
 
    FAST;
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        cin >> str;
        sort(str.begin(), str.end());
        string newStr = "";
        for (char ch = 'A', ch2 = 'a'; ch <= 'Z'; ch++, ch2++)
        {
            int capitalLetter = count(str.begin(), str.end(), ch);
            int smallLetter = count(str.begin(), str.end(), ch2);
            while (capitalLetter--) newStr += ch;
            while (smallLetter--) newStr += ch2;
        }
        memset(vis, 0, sizeof(vis));
        PERMUTATION(newStr, 0, newStr.size());
        vec.clear();
    }
}
 

[UVa] 574 - Sum It Up

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 574 - Sum It Up
Source            : UVa Online Judge
Category          : Backtrack
Algorithm         : Backtrack
Verdict           : Accepted 

#include <bits/stdc++.h>
 
using namespace std;
 
#define VI        vector<int>
#define pb        push_back
 
VI ans;
int sum, arr[15];
int amount, n;
string str;
 
bool isSol;
 
map <VI, bool> m;
map <int, int> vis;
 
void combination(int pos, int n)
{
    if (sum == amount)
    {
        if (!m[ans])
        {
            int len = ans.size();
            for (int i=0; i<len; i++)
            {
                cout << ans[i];
                if (i == len-1) cout << endl;
                else cout << "+";
            }
        }
        m[ans] = true;
        isSol = true;
        return;
    }
    for (int i=pos; i<n; i++)
    {
        if (vis[i]) continue;
        vis[i] = 1;
        sum += arr[i];
        ans.push_back(arr[i]);
 
        combination(i+1, n);
 
        vis[i] = 0;
        sum -= arr[i];
        ans.pop_back();
    }
}
 
int main()
{
//   freopen("in.txt", "r", stdin);
//   freopen("out.txt", "w", stdout);
 
   ios::sync_with_stdio(0);
   cin.tie(0);
   while (cin >> amount >> n)
   {
        if (amount+n == 0) return 0;
        for (int i = 0; i < n; i++) cin >> arr[i];
        isSol = false;
        cout << "Sums of " << amount << ":\n";
        combination(0, n);
        if (!isSol) cout << "NONE" << endl;
        m.clear();
   }
   return 0;
}