Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:25600000")
- #define _CRT_NO_WARNINGS
- #include <iostream>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <string>
- #include <vector>
- #include <list>
- #include <algorithm>
- #include <cstring>
- #include <map>
- #include <queue>
- #include <set>
- #include <cassert>
- #include <complex>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef vector<int> VI;
- typedef vector< vector<int> > VVI;
- typedef pair<int, int> PII;
- typedef vector<PII> VPII;
- #define REP(i, n) for(int i = 0; i < n; ++i)
- #define RREP(i, n) for(int i = n - 1; i >= 0; --i)
- #define FOR(i, x, y) for(int i = x; i <= y; ++i)
- #define RFOR(i, x, y) for(int i = x; i >= y; --i)
- #define SZ(a) (int)(a).size()
- #define ALL(a) (a).begin(),(a).end()
- #define SORT(a) sort(ALL(a))
- #define CLEAR(x) memset(x,0,sizeof x);
- #define UNIQUE(c) SORT(c),(c).resize(unique(ALL(c))-(c).begin())
- #define pb push_back
- #define sqr(x) (x)*(x)
- const double pi=acos(-1.0);
- const double eps = 1e-9;
- const int MAXN = 510000;
- set<int> bad;
- int n, N1, N2, NP, hs;
- char s[MAXN];
- int seq[MAXN];
- int a[MAXN];
- PII pairs[MAXN];
- int main()
- {
- scanf("%d\n", &n);
- REP(i, n)
- {
- gets(s);
- REP(i, strlen(s))
- {
- if (s[i] >= 'A' && s[i] <= 'Z')
- s[i] = s[i] - 'A' + 'a';
- }
- REP(i, strlen(s))
- if (isalpha(s[i]))
- {
- hs = 0;
- while(true)
- {
- hs = hs * 30 + s[i] - 'a';
- ++i;
- if (i >= strlen(s) || !isalpha(s[i])) break;
- }
- seq[N1++] = hs;
- }
- }
- scanf("%d\n", &n);
- REP(i, n)
- {
- gets(s);
- hs = 0;
- REP(i, strlen(s))
- hs = hs * 30 + s[i] - 'a';
- bad.insert(hs);
- }
- REP(i, N1)
- if (bad.find(seq[i]) == bad.end())
- {
- a[N2++] = seq[i];
- }
- NP = N2 - 1;
- REP(i, NP)
- {
- int t1 = a[i];
- int t2 = a[i + 1];
- if (t1 > t2) swap(t1, t2);
- pairs[i] = PII(t1, t2);
- }
- sort(a, a + N2);
- sort(pairs, pairs + NP);
- int q;
- scanf("%d\n", &q);
- REP(query, q)
- {
- gets(s);
- bool f = false;
- int h1 = 0;
- int h2 = 0;
- REP(i, strlen(s))
- {
- if (isalpha(s[i]))
- {
- if (!f) h1 = h1 * 30 + s[i] - 'a';
- if (f) h2 = h2 * 30 + s[i] - 'a';
- }
- else
- {
- f = true;
- }
- }
- if (h1 > h2) swap(h1, h2);
- PII t = make_pair(h1, h2);
- double p0 = upper_bound(pairs, pairs + NP, t) - lower_bound(pairs, pairs + NP, t); p0 /= NP;
- double res = 0;
- if (p0 > 0.0)
- {
- double p1 = upper_bound(a, a + N2, h1) - lower_bound(a, a + N2, h1); p1 /= N2;
- double p2 = upper_bound(a, a + N2, h2) - lower_bound(a, a + N2, h2); p1 /= N2;
- res = p0 / p1 / p2;
- }
- printf("%.7lf\n", res);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement