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

Решения на Здравко и Петър

A. Пароли

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

bool isPasswordValid(string pass, int len, int cap, int dig, int spec) {
    if(len>pass.size()) {
        return false;
    }
    int currLow=0;
    int currCap=0;
    int currDig=0;
    int currSpec=0;
   
    for(int i=0; i<pass.size(); i++) {
        char currEl = pass[i];
        //workaround for test compatibility
        if(' '==currEl) {
            return false;
        }
    }
   
    for(int i=0; i<pass.size(); i++) {
        char currEl = pass[i];
        bool isCap = ((currEl>='A')&&(currEl<='Z'));
        bool isDig = ((currEl>='0')&&(currEl<='9'));
        bool isLow = ((currEl>='a')&&(currEl<='z'));
         
        if(isCap) {
            currCap++;
        }
        else if(isDig) {
            currDig++;
        }
        else if((!isLow)&&(currEl!=' ')) {
            currSpec++;
        }
        if((currCap>=cap)&&(currDig>=dig)&&(currSpec>=spec)) {
            return true;
        }
    }
    return false;
}

int main() {  
    int len, cap, dig, spec, count;
    string pass="";
    while(cin >> len >> cap >> dig >> spec) {
        cin >> count;
        cin.ignore();
        for(int i=0; i<count; i++) {
            getline(cin, pass);
            if(isPasswordValid(pass, len, cap, dig, spec)) {
                cout << "yes" << endl;
            }
            else {
                cout << "no" << endl;
            }
        }
    }
    return 0;
}
B. Осем бита

#include <iostream>
using namespace std;

long long dp[66][9];

int main()
{

    for (int k = 1; k <= 8; k++) {
        dp[k][k] = 1;
        for (int n = k+1; n <= 65; n++) {
            dp[n][k] = dp[n-1][k]*n/(n-k);
        }
    }

    int t; cin >> t;
    while (t--) {
        int x; cin >> x;

        long long ans = 0;
        int sz = 65;

        for (int i = 8; i >= 1; i--) {
            while (sz--) {
                if (dp[sz][i] < x) {
                    x -= dp[sz][i];
                    sz++;
                    ans += (1 << (sz-1));
                    break;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

int main()
{
    cin.sync_with_stdio(false);
    cin.tie(0);

    int rows, cols, k;
    while(cin >> rows >> cols >> k) {
        vector<string> myStrings;

        for(int i=0;i<rows;i++) {
            string cur;
            cin >> cur;
            myStrings.push_back(cur);
        }

        for(int i=0;i<cols;i++) {
            string cur;
            for(int j=0;j<rows;j++) {
                cur += myStrings[j][i];
            }
            myStrings.push_back(cur);
        }

        vector< vector<bool> > used(rows, vector<bool>(cols, false));
        for(int i=0;i<k;i++) {
            string curWord;
            cin >> curWord;
            int cntMatch=0;

            for(int j=0;j<myStrings.size();j++) {
                string s  = myStrings[j];
                int curIdx=0;
                while((curIdx=s.find(curWord, curIdx)) != string::npos) {
                    cntMatch++;
                    curIdx+=curWord.size();
                }
            }
            cout << cntMatch << endl;
        }
    }
    return 0;
}

D. Монети

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

int main()
{
    cin.sync_with_stdio(false);
    cin.tie(0);

    int k;
    while(cin >> k) {
        const int MAX_SIZE = 100001;
        vector<int> myVec(MAX_SIZE);


        vector<int> moneti(k);
        for(int i=0;i<k;i++) {
            cin >> moneti[i];

            if (moneti[i] < MAX_SIZE) myVec[moneti[i]]=1;
            for(int j=moneti[i]+1;j<MAX_SIZE;j++) {
                if (myVec[j-moneti[i]] != 0 && myVec[j] == 0) myVec[j]= 1 + myVec[j-moneti[i]];
                else if (myVec[j-moneti[i]] != 0 && myVec[j] != 0) myVec[j]= min(myVec[j], 1 + myVec[j-moneti[i]]);
            }
        }

        int m;
        cin >> m;
        for(int i=0;i<m;i++) {
            int x; cin >> x;
            cout << myVec[x] << " ";
        }
        cout << endl;
    }
    return 0;
}

E. Прозорец

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

int main()
{
    cin.sync_with_stdio(false);
    cin.tie(0);

    int m, n;
    while(cin >> m >> n) {
        vector<int> numbers(m);
        for(int i=0;i<m;i++) {
            cin >> numbers[i];
        }

        set<int> ans;
        multiset<int> curWindow;
        for(int i=0;i<n;i++) {
            curWindow.insert(numbers[i]);
        }

        ans.insert(*curWindow.begin());
        for(int i=0;i<m-n;i++) {
            curWindow.erase( curWindow.find(numbers[i]));
            curWindow.insert(numbers[i+n]);

            ans.insert(*curWindow.begin());
        }
        cout << ans.size() << endl;
    }
    return 0;
}


F. Два цвята

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

vector< vector<int> > graph;
vector<int> colors;

bool dfs(int node)
{
    int curColor = colors[node];
    int nextColor = (curColor==1 ? 2 : 1);

    for(int i=0;i<graph[node].size();i++) {
        if(colors[ graph[node][i] ] == 0) {
           colors[ graph[node][i] ] = nextColor;
           if(dfs(graph[node][i]) == false) {
                return false;
           }
        } else if(colors[ graph[node][i] ] == curColor) {
            return false;
        }
    }

    return true;
}

int main()
{
    cin.sync_with_stdio(false);
    cin.tie(0);

    int m;
    while(cin >> m) {
        graph.clear();
        graph.resize(1001);
        colors.clear();
        colors.resize(1001, 0);

        for(int i=0;i<m;i++) {
            int u, v;
            cin >> u >> v;
            //u--; v--;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        colors[1]=1;
        if(dfs(1) == true) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

G. Пътища

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

int n;
int wrongI, wrongJ;
vector< vector<bool> > visited;
int cntDuno;
int cntVisited=1;

void dfs(int i, int j)
{
    if(i<0 || j<0 || i>=n || j>=n) {
        return;
    }
    if(i==wrongI && j==wrongJ) {
        return;
    }
    if(visited[i][j]) {
        return;
    }
    cntVisited++;
    if(cntVisited == n*n) {
        cntDuno++;

        cntVisited--;
        return;
    }
    visited[i][j]=true;

    dfs(i-1,j  );
    dfs(i  ,j-1);
    dfs(i+1,j  );
    dfs(i  ,j+1);

    visited[i][j]=false;
    cntVisited--;
}

int main()
{
    while(cin >> n) {
        cin >> wrongI >> wrongJ;
        wrongI--;
        wrongJ--;

        visited.clear();
        visited.resize(n, vector<bool>(n,false));

        cntDuno=0;
        cntVisited=1;
        dfs(0,0);

        cout << cntDuno << endl;
    }


    return 0;
}

H. Робот

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

int arr[110][110];
int dp[110][110];

int main()
{
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                cin >> arr[i][j];

                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + arr[i][j];
            }
        }
        cout << dp[n][n] << endl;
    }
    return 0;
}

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

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

int main()
{
    string line;

    while(getline(cin,line)) {
        stringstream ss(line);

        int cnt;
        ss >> cnt;
        vector<int> vec;
        int cur;
        while(ss >> cur) {
            vec.push_back(cur);
        }

        sort(vec.rbegin(),vec.rend());

        int ans =0;
        for(int i=0;i<cnt;i++) {
            ans += vec[i];
        }

        cout << ans << endl;
    }
    return 0;
}

J. Автобус

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

typedef unsigned long long ull;

int main()
{
    ull k;
    while(cin >> k) {
        ull ans = ((ull)1) << k;
        ans --;
        cout << ans << endl;
    }
    return 0;
}