443A - Anton and Letters
Simple and easy, solved by two lines of python code.
ls = filter(lambda y: y, map(lambda x: x.strip(), raw_input()[1:-1].split(",")))
print len(set(ls))
443B - Kolya and Tandem Repeat
Brute force. Just enumerate the beginning and the end of the substring, and check if that substring is tandem repeat.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define print(x) cout << x << endl
#define input(x) cin >> x
string str;
int k;
int main()
{
freopen("input.txt", "r", stdin);
input(str >> k);
for (int i = 0; i < k; i++) {
str += '?';
}
int len = str.length();
int ans = 0;
for (int i = 0; i < len; i++) {
if (str[i] == '?') {
break;
}
for (int j = 1; i + j < len; j += 2) {
int slip = (j + 1) / 2;
for (int k = 0; k < slip; k++) {
if (str[i + k] == str[i + k + slip] || str[i + k + slip] == '?') {
/* pass */;
}
else {
goto fail;
}
}
ans = max(ans, j + 1);
fail: /*pass*/;
}
}
print(ans);
return 0;
}
442A - Borya and Hanabig
Because Borya knows about the color and value of all his cards, he just need to distinguish each card from the others.
Distinguish one card from all others seems difficult, but distinguish one card from ONE other card is simple enough. So if we can tell the difference between one card and any other, it can be determined from all pairs which contain this card. At last, if all pairs of cards can be distinguished, we can claim that we can distinguish all cards.
It's easy to find out that we have 10 different kind of hints in total(5 colors and 5 values) and 1024 different combination of all that hints(1 << 10). As a result, we can enumerate all combinations, and try to indicate whether this batch of hints can distinguish all these cards.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <map>
#include <set>
using namespace std;
#define print(x) cout << x << endl
#define input(x) cin >> x
const int SIZE = 5;
const int INF = 1 << 29;
int n;
char instr[10];
int mp[256];
void init()
{
const char _str[] = "12345RGBYW";
for (int i = 0; _str[i]; i++) {
mp[int(_str[i])] = i;
}
}
int conv(char x)
{
return mp[int(x)];
}
int main()
{
freopen("input.txt", "r", stdin);
init();
while (input(n)) {
set<int> st;
vector<int> vec;
for (int i = 0; i < n; i++) {
scanf("%s", instr);
int a = conv(instr[0]);
int b = conv(instr[1]);
int v = (1 << a) | (1 << b);
// print(a << ' ' << b << ' ' << v);
if (st.find(v) != st.end()) {
continue;
}
st.insert(v);
vec.push_back(v);
}
int ans = INF;
for (int i = 0; i < (1 << 10); i++) {
for (int j = 0; j < (int)vec.size(); j++) {
for (int k = j + 1; k < (int)vec.size(); k++) {
int diff = vec[j] ^ vec[k];
if (!(i & diff)) {
goto fail;
}
}
}
ans = min(ans, __builtin_popcount(i));
fail: /*pass*/;
}
print(ans);
}
return 0;
}
442B - Andrey and Problem
Assuming that the possibility of getting exactly one problem from some of Andrey's friends is p1 and get no problem is p0. So, if we want to add one friend whose possibility of comming up a problem is pa to this very friend set, we can get next_p1 = p1 * (1 - pa) + p0 * pa and next_p0 = p0 * (1 - pa). And it easy to indicate that a greater pa will lead to a greater next_p1.
The initial value is that p0 == 1; p1 == 0. And we add the friends one by one ordered by the possibilites reversely. At last, the max p1 is the final result.
n = int(raw_input())
ps = map(float, raw_input().split())
ps.sort(reverse=True)
good = ps[0]
bad = 1 - good
ans = good
for p in ps[1:]:
good, bad = good * (1 - p) + p * bad, bad * (1 - p)
ans = max(ans, good)
print ans
Comments
comments powered by Disqus