Декемврийско
състезание на 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;
}