Декемврийско състезание  на 15.12.2018, събота, 10:00, 702-2.

Задача A. Пароли

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

int main()
{
    int n, len, cap, dig, spec;
     int len0 = 0, cap0 = 0, dig0 = 0, spec0 = 0;
    while(cin >> len >> cap >> dig >> spec >> n)
    {
        string ch;
        getline(cin, ch);
   
        for(int i=0; i<n; i++)
        {
            string s;
            getline(cin, s); // cout << s << endl;
            bool spac = false;
            int len0 = 0, cap0 = 0, dig0 = 0, spec0 = 0;
            for(int j = 0; j < s.length(); j++)
            {
                if (s[j] == ' ') spac = true;
                else if(s[j] >= 'A' and s[j] <= 'Z') cap0++;
                else if(s[j] >= '0' and s[j] <= '9') dig0++;
                else if(!(s[j] >= 'a' and s[j] <= 'z'))
                    spec0++;
            }
            if (s.length() >= len && cap0 >= cap && dig0 >= dig && spec0 >= spec && !spac)
            cout << "yes" << endl;
            else cout << "no" << endl;
        }
    }
    return 0;
}

---

Задача B. Осем бита

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

typedef unsigned long long ull;
ull n;
bool a[64] = {false};

int main()
{
    int k;
    cin >> k;
    for(int kk = 0; kk < k; ++kk)
    {
        cin >> n;
        for (int i=0; i<64; ++i) a[i] = (i>=56)?true:false;
       
        for(ull i = 1; i < n; i++)
            next_permutation(a, a+64);
        ull res = 0;
        for (int i=0; i<64; ++i)
            if (a[i]) res += (1L << (63-i));
        cout << res << endl;
    }
    return 0;
}

---

Задача C. Намерете думата

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

string mat[20], matt[20];
int n, m, k, nums;

int main()
{
    while(cin >> n >> m >> k)
    {
        for(int i = 0; i < n; i++) cin >> mat[i];
       
        for(int j = 0; j < m ; j++)
        {
            matt[j] = "";
            for(int i = 0; i < n ; i++)
            {
                matt[j] = matt[j] + mat[i][j];
            }
        }
      
//      for(int j = 0; j < m ; j++) cout << matt[j] << endl;
 //    cout << endl;
       
        string s;
        for(int kk = 0; kk < k; kk++)
        {
            cin >> s; // cout << s << " ---" << endl;
            nums = 0;
            for(int i = 0; i < n ; i++)
                for(int j = 0; j < m ; j++)
                    if (mat[i].substr(j, s.length()) == s)
                {
                    nums++; j += s.length() - 1;
                }
            for(int j = 0; j < m ; j++)
                for(int i = 0; i < n ; i++)
                    if (matt[j].substr(i, s.length()) == s)
                {
                    nums++; i += s.length() - 1;
                }
           
            cout << nums << endl;
        }
    }
    return 0;
}

---

Задача D. Монети

#include <iostream>
#include <vector>
using namespace std;

int n, m, k;
vector<int> coins;
const int INF = 100000;

int value[100000];

void solve()
{
value[0] = 0;
for (int x = 1; x <= m; x++)
{
    value[x] = INF;
    for (int c = 0; c < coins.size(); c++)
    {
//               cout << x << " " << c << " " << x-coins[c] << " "
//               << value[x] << " " << value[x-coins[c]]+1 << endl;
       
        if (x-coins[c] >= 0 && value[x] > value[x-coins[c]]+1)
            value[x] = value[x-coins[c]] + 1;
            }
    }
//     for (int i = 0; i < m; i++) cout << value[i] << " ";
    cout << ((value[m]==INF) ? 0 : value[m]) << " ";
}

int main()
{
    while(cin >> n)
    {
        coins.clear();
        while(n--)
        {
            cin >> k; coins.push_back(k);
        }
        cin >> k;
        while(k--)
        {
            cin >> m;
            solve();
        }
        cout << endl;
    }
    return 0;
}

---

Задача E. Прозорец

#include <iostream>
#include <queue>
#include <utility>
#include <set>
using namespace std;

deque<pair<int, int> > q;
int k, m, n, i;

set<int> sett;

void print()
{
    cout << "print: ";
    for(deque<pair<int, int> >::iterator it = q.begin(); it != q.end(); ++it)
        cout << it->second << " ";
    cout << endl;
}

int main()
{
    while(cin >> n >> m)
    {
        i = 0;
        q.clear(); sett.clear();
        cin >> k;
        q.push_back(pair<int, int>(i,k));
        i++;
        while(i < n)
        {
            cin >> k; // cout << "next " << k << endl;
            if (q.front().first == i - m) q.pop_front();
            if (k < q.front().second)
            {
                q.clear(); q.push_back(pair<int, int>(i,k));
            }
            else
            {
                while(k < q.back().second) q.pop_back();
                q.push_back(pair<int, int>(i,k));
            }
      //      print();
            i++;
            if (i >= m)
            {
    //            cout << q.front().second << " ";
                sett.insert(q.front().second);
            }
        }
    //    cout << endl
        cout << sett.size() << endl;
       
    }
    return 0;
}

---

Задача F. Два цвята

#include <iostream>
#include <cstring>
#include <cstdlib>
#define MAXN 101
using namespace std;

int mat[MAXN][MAXN] = {},edges;
int used[MAXN] = {0};
int n = 0;
bool flag = true;

void solve_dfs(int x, int oldx){
    if (used[x])
    {
        if (used[x] == used[oldx]) flag = false;
        return;
    }
    used[x] = (x == 1)?1:(-used[oldx]);
//    cout << x << " ";
    for(int i = 1; i <= mat[x][0]; i++){
        solve_dfs(mat[x][i], x);
    }
}

void input(){
    int v1,v2;
    for(int i = 0; i < edges; i++){
        cin >> v1 >> v2;
        if (v1 > n) n = v1;
        if (v2 > n) n = v2;
        mat[v1][++mat[v1][0]] = v2;
        mat[v2][++mat[v2][0]] = v1;
    }
}

void print()
{
    for(int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << mat[i][j] << " ";
        cout << endl;
    }
}

void print_used()
{
    cout << "n="<< n << " used: ";
    for(int i = 1; i < n; i++) cout << used[i] << " ";
    cout << endl;
}

int main()
{
    while(cin>>edges){
        n = 0;
        input();
//    print();
        flag = true;
        solve_dfs(1, 1);
//    print_used();
        cout << (flag?"YES":"NO") << endl;
       
        memset(used,0,sizeof(used));
        memset(mat,0,sizeof(mat));
    }
//    cout << endl;
    return 0;
}

---

Задача G. Пътища

#include <iostream>
#include <iomanip>
#define MAXN 10
using namespace std;

int a[MAXN][MAXN];
int n, num;

void print()
{

    for (int i = 0; i <= n+1; i++)
    {
        for (int j = 0; j <= n+1; j++) cout << setw(2) << a[i][j] << " ";
        cout << endl;
    }
    cout << endl;
}

void step(int i, int j, int k)
{
    a[i][j] = k;
    if (k == n*n - 1)
    {
        num++; // print();
    }
    if (!a[i+1][j]) step(i+1, j, k+1);
    if (!a[i-1][j]) step(i-1, j, k+1);
    if (!a[i][j+1]) step(i, j+1, k+1);
    if (!a[i][j-1]) step(i, j-1, k+1);
    a[i][j] = 0; return;
}

int main()
{
    while(cin >> n)
    {
        for (int i = 0; i <= n; i++)
        {
            a[i][0] = a[0][i] = a[n+1][i] = a[i][n+1] = 1;
            for (int j = 1; j <= n; j++) a[i][j] = 0;
        }
        a[n+1][n+1] = 1;
        int x, y;
        cin >> x >> y;
        a[x][y] = -1;
        num = 0;
 // print();
        step(1,1,1);
        cout << num << endl;
    }
    return 0;
}

---

Задача H. Робот

---

Задача I. Задача за друга раница

---

Задача J. Автобус

#include <iostream>
#include <iomanip>
#define MAXN 10
using namespace std;

int k;

int main()
{
    while(cin >> k)
    {
        long long res = 0;
        for (int i = 0; i < k; i++)
            res = 2*res + 1;
        cout << res << endl;
    }
    return 0;
}

---