A - oval-and-rectangle
数学题，积分+换元即可。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
const int MAXN = 1e3 + 5, MAXM = 5e6 + 5, BOUND = 2e5, MOD = 998244353, INF = 0x3f3f3f3f, base = 10000;
const int inv2 = (MOD + 1) >> 1;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0), eps = 1e-9;
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
#define lc(x) ch[x][0]
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>
#define rc(x) ch[x][1]
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define all(a) (a).begin(), (a).end()
#define sz(a) int(a.size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fi first
#define se second
#define MP std::make_pair
#define ri register int
//#define sz(a) int((a).size())
const int N = 2e5,M = (1<<20);
inline int add(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b;}
inline int dec(int a, int b) {return a < b ? a - b + MOD : a - b;}
inline int mul(int a, int b) {return 1ll * a * b % MOD;}
template <typename T>
inline void cmin(T &a,T b){a = min(a,b);}
template <typename T>
inline void cmax(T &a,T b){a = max(a,b);}
ll qpow(ll a,ll b){
ll ans=1;
for(;b;b>>=1,a=a*a%MOD)if(b&1)ans=ans*a%MOD;
return ans;
}
mt19937 mrand(random_device{}());
void run(){
db a,b;cin>>a>>b;
printf("%.6f\n",2*b+PI*a-0.0000005);
}
int main() {
//ios::sync_with_stdio(false); cin.tie(0);
int _; scanf("%d",&_);
while(_--)run();
return 0;
}
B - bookshelf
题意：
给\(n\)个小球放入\(k\)个盒子中，\(n,k\leq 10^6\)。
假设第\(i\)个盒子有\(cnt_i\)个小球，那么\(val_i=2^{fib[cnt_i]}-1\)。
最终总的贡献为\(\displaystyle gcd(val_1,val_2,...,val_k)\)。
求最终总贡献的期望值。
思路：
介绍两个等式，其中一个为：
\[gcd(2^x-1,2^y-1)=2^{gcd(x,y)}-1 \]
证明如下：
不妨\(x<y\)，那么\(\displaystyle gcd(2^x-1,2^y-1)=gcd(2^x-1,2^y-2^x)=gcd(2^x-1,2^x\cdot (2^{y-x}-1))\)。
设\(d=gcd(2^x-1,2^y-1)\)，显然\(d\)为奇数，也就是说\(d\not {|}2^x\)，那么就有\(\displaystyle gcd(2^x-1,2^x\cdot (2^{y-x}-1))=gcd(2^x-1,2^{y-x}-1)\)。
也就是说我们可以对指数运用欧几里得算法，那么就有\(\displaystyle gcd(2^x-1,2^y-1)=gcd(2^0-1,2^{gcd(x,y)}-1)=2^{gcd(x,y)}-1\)。
故得证。
然后还有第二个式子：
\[gcd(fib[a],fib[b])=fib[gcd(a,b)] \]
证明如下：
首先有个引理：
\[f_{m+n}=f_{m}f_{n+1}+f_{m-1}f_{n} \]
证明就是构造个矩阵：
\[A^n=\left( \begin{array}{cc} f_{n-1}&f_n\\ f_n &f_{n-1} \end{array} \right) \]
然后通过\(\displaystyle A^{m+n}=A^m\times A^n\)可得。
还有一个引理:
- 若\(m,n\geq 1\)，那么\(f_m|f_{nm}\)
证明的话我们可以对\(n\)做归纳来证明，证明的话要用到我们刚刚提到的引理。
然后就开始推式子：
令\(n=mk+r\)，有：
\[\begin{aligned} gcd(f_m,f_n)=&gcd(f_n,f_{mk+1}f_r+f_{mk}f_{r-1})\\ =&gcd(f_m,f_{mk+1}f_r)\\ =&gcd(f_m,f_r) \end{aligned} \]
我们可以发现下标也可以运用欧几里得算法，所以\(\displaystyle gcd(f_m,f_n)=f_{gcd(m,n)}\)。
还有个推论：
- 若\(f_m|f_n\)，则\(m|n\)。
证明的话就运用\(f_m=gcd(f_m,f_n)=f_{gcd(m,n)}=f_m\)。
以上相关证明详见传送门。
好了，回到这个题，我们最后就是要求：
\[2^{f_{gcd(cnt_1,cnt_2,...,cnt_k)}}-1 \]
因为我们最终是求期望，那么我们只需要对每一个\(\displaystyle d=gcd(cnt_1,cnt_2,...,cnt_k)\)，求出这个的方案数即可。
这就是老套路了：
\[\begin{aligned} &\sum_{c_1=0}^n\sum_{c_2=0}^n\cdots\sum_{c_k=0}^n[gcd(c_1,c_2,\cdots,c_k)=d]\\ =&\sum_{c_1=0}^{\frac{n}{d}}\sum_{c_2=0}^{\frac{n}{d}}\cdots\sum_{c_k=0}^{\frac{n}{d}}[gcd(c_1,c_2,\cdots,c_k)=1]\\ =&\sum_{c_1=0}^{\frac{n}{d}}\sum_{c_2=0}^{\frac{n}{d}}\cdots\sum_{c_k=0}^{\frac{n}{d}}\sum_{t|c_1,\cdots,t|c_k}\mu(t)\\ =&\sum_{t=1}^n\mu(t)\sum_{c_1=0}^{\frac{n}{dt}}\sum_{c_2=0}^{\frac{n}{dt}}\cdots\sum_{c_k=0}^{\frac{n}{dt}} \end{aligned} \]
一顿推导猛如虎，后来发现忽视了\(cnt_1+cnt_2+\cdots+cnt_k=n\)这个条件。
我们发现，若\(gcd(cnt_1,cnt_2,\cdots,cnt_k)=d\)，那么必然有\(d|n\)，那么就是\(\displaystyle dt_1+dt_2+\cdots+dt_k=n\)即\(\displaystyle t_1+t_2+\cdots+t_k=\frac{n}{d},t_i\geq 0\)。
其实这就是隔板法的一个经典应用，假设我们算出了方案数\(F(d)\)，发现这其实是\(gcd\)为\(d\)的倍数的方案数。
那么我们要算\(f(d)\)的话，只需要减去\(f(2d)+f(3d)+\cdots+f(td)\)就行。就是个简单容斥。
当然，我们也可以借助莫比乌斯函数：\(F(d)=F(d)-F(2d)-F(3d)-F(5d)+F(6d)...\)这样来算。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2020/5/15 20:46:04
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e6 + 5, MOD = 1e9 + 7;
int qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
int fib[N], fac[N], inv[N];
void init() {
fib[0] = 0, fib[1] = 1;
for (int i = 2; i < N; i++) {
fib[i] = (fib[i - 1] + fib[i - 2]) % (MOD - 1);
}
fac[0] = 1;
for (int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
inv[N - 1] = qpow(fac[N - 1], MOD - 2);
for (int i = N - 2; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
}
int C(int n, int m) {
return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int n, k;
int f[N];
void run() {
cin >> n >> k;
int tot = C(n + k - 1, k - 1);
int ans = 0;
vector <int> d;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
d.push_back(i);
f[i] = C(n / i + k - 1, k - 1);
}
}
for (int i = sz(d) - 1; i >= 0; i--) {
for (int j = i + 1; j < sz(d); j++) {
if (d[j] % d[i] == 0) {
f[d[i]] = (f[d[i]] - f[d[j]] + MOD) % MOD;
}
}
}
for (auto it : d) {
ans = (ans + 1ll * f[it] * (qpow(2, fib[it] % (MOD - 1)) - 1 + MOD) % MOD) % MOD;
}
ans = 1ll * ans * qpow(tot, MOD - 2) % MOD;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
init();
int T; cin >> T; while(T--)
run();
return 0;
}
C - Ringland
题意：
给定一个长度为\(L\)，现有\(2n\)个位置，有\(n\)个新郎，\(n\)个新娘。
现在每个新郎要找到一个新娘，会花费一定的代价，代价为到新娘位置最短的距离。
问配对最小的代价之和为多少。
思路：
题意可以抽象为给出一个括号序列，现在要将\(n\)个左括号和\(n\)个右括号进行匹配，匹配代价为距离。问最终匹配代价的和最小为多少。
注意到有这样一个事实：
- 假设最优方案中，\(i,j\)相匹配，那么\(i\)之后的左括号必然和\(j\)之后的右括号匹配(注意这是个循环序列，我们可以拼接一份在后面)。
因为如果不是这样，我们必然可以通过交换匹配使得答案更优。
简单来说，我们确定一对匹配之后，后面的依次也就确定了，比如\((1,3),(2,4),(3,5),\cdots\)。
之后考虑枚举断点将环拆开，考虑一个括号序列的最优答案。一个序列中的最优答案即是\((1,1),(2,2),\cdots,(n,n)\)这样来匹配，其中\((i,j)\)表示第\(i\)个左括号，第\(j\)个右括号。如果不是这样的话比如是\((1,2),(2,3)...\)来匹配的话我们在另外一个序列中能够枚举到。最后所有这样的最优答案取\(min\)就是最终的最优答案。
接下来我们通过考虑每个位置的贡献来计算答案。我们将\((\)看作\(1\)，将\()\)看作\(-1\)，序列前缀和为\(s_i\)。那么：
- 对于\((\)而言，\(s_i>0\)贡献为负，\(s_i\leq 0\)贡献为正；
- 对于\()\)而言，\(s_i\geq 0\)贡献为正，\(s_i<0\)贡献为负。
可以根据这一点对每个位置单独计算，能够很方便地统计信息。
序列每移动一位，所有的前缀和值都会变化不超过\(1\)，这里可以用一个偏移量来统计。
用树状数组来写的话会方便很多。
细节见代码吧，思路真是挺巧妙的，主要在于匹配方式这一点，然后通过这一点我们可以枚举断点来统计。
Code
/*
* Author: heyuhhh
* Created Time: 2020/5/21 11:20:52
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e6 + 5;
namespace IO{
#define BUF_SIZE 100000
#define OUT_SIZE 100000
bool IOerror=0;
inline char nc(){
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if (p1==pend){
p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
if (pend==p1){IOerror=1;return -1;}
}
return *p1++;
}
inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
inline void read(int &x){
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (sign)x=-x;
}
struct Ostream_fwrite{
char *buf,*p1,*pend;
Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
void out(char ch){
if (p1==pend){
fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
}
*p1++=ch;
}
void println(ll x){
static char s[25],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1); out('\n');
}
void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
~Ostream_fwrite(){flush();}
}Ostream;
inline void println(ll x){Ostream.println(x);}
inline void println(){Ostream.out('\n');}
inline void flush(){Ostream.flush();}
};
int n, L;
int sum[N];
pii a[N];
struct BIT {
ll c[N];
void init() {
memset(c, 0, sizeof(ll) * (2 * n + 4));
}
int lowbit(int x) {
return x & -x;
}
void add(int x, int v) {
x += n + 1;
for (; x < 2 * n + 4; x += lowbit(x)) {
c[x] += v;
}
}
ll query(int x) {
x += n + 1;
ll res = 0;
for (; x; x -= lowbit(x)) {
res += c[x];
}
return res;
}
}bit;
void run() {
IO::read(n), IO::read(L);
for (int i = 1; i <= 2 * n; i++) {
IO::read(a[i].fi);
a[i].se = (i <= n ? 1 : -1);
}
sort(a + 1, a + 2 * n + 1);
ll tot = 0;
for (int i = 1; i <= 2 * n; i++) {
sum[i] = sum[i - 1] + a[i].se;
}
bit.init();
for (int i = 1; i <= 2 * n; i++) {
if (a[i].se == 1) {
bit.add(sum[i], 2 * a[i].fi), tot -= a[i].fi;
} else {
bit.add(sum[i] + 1, -2 * a[i].fi), tot += a[i].fi;
}
}
ll ans = tot + bit.query(0);
for (int i = 1; i < 2 * n; i++) {
if (a[i].se == 1) {
bit.add(sum[i], 2 * L), tot -= L;
} else {
bit.add(sum[i] + 1, -2 * L), tot += L;
}
ans = min(ans, tot + bit.query(sum[i]));
}
printf("%lld\n", ans);
}
int main() {
int T; scanf("%d", &T); while(T--)
run();
return 0;
}
I - Werewolf
题意：
现有狼和村民两种阵营，狼可说真话可说假话，村民只会说真话。每个人只会说一句话。
现在问有多少人能够确定是狼和村民。
思路：
显然能够被确定为村民的人为\(0\)，因为狼可以被当作村民。
接下来就考虑只能被确定为狼的有哪些，也就是一个人如果有至少一种可能为村民那他就不满足条件。
这里我们只需要推理一下即可。
首先连接所有的村民边，如果形成一个环，那么他们都可以为村民，就不可能存在铁狼。
那么就会形成一个森林，接下来考虑狼边。
- 如果狼边连向其它连通块，那么该连通块中可以所有都为村民，另外一个连通块全为狼。
- 如果连向自己连通块中的结点\(i\)，那么根节点到\(i\)都只能是铁狼，否则会出现矛盾。
- 如果有其它狼边连向该连通块，那么该连通块可能都为村民也可能都为狼。
综上我们会发现，只有第二种情况会出现铁狼，我们就找满足第二种条件的点即可。
就是简单推理推理？虽然说起来很简单，但是从头想的时候还是没那么容易的。。
Code
/*
* Author: heyuhhh
* Created Time: 2020/5/15 14:59:03
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
int n;
vector <int> rG[N];
vector <pii> edges;
int f[N];
int find(int x) {
return f[x] == x ? f[x] : f[x] = find(f[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) f[fx] = fy;
}
int rdfs(int u) {
int res = 1;
for (auto v : rG[u]) {
res += rdfs(v);
}
return res;
}
void run() {
cin >> n;
edges.clear();
for (int i = 1; i <= n; i++) rG[i].clear();
for (int i = 1; i <= n; i++) f[i] = i;
for (int i = 1; i <= n; i++) {
int x; string s;
cin >> x >> s;
if (s[0] == 'v') {
merge(i, x);
rG[x].push_back(i);
} else {
edges.push_back(MP(i, x));
}
}
int ans1 = 0, ans2 = 0;
for (auto edge : edges) {
int u = edge.fi, v = edge.se;
if (find(u) == find(v)) {
ans2 += rdfs(v);
}
}
cout << ans1 << ' ' << ans2 << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T; while(T--)
run();
return 0;
}
K - sacul
题意：
定义海绵宝宝矩阵：\(HMBB_i\)的大小为\(p^i\cdot p^i\)，其中\(p\)为一个质数。矩阵元素为\(HMBB_n=({i\choose j}mod\ p>0)?1:0\)。并且\(HMBB_n^k\)为矩阵的\(k\)次方。
定义\(\displaystyle F[n][k]=\sum HMBB_n^k\)，即矩阵的元素之和。
求
\[\sum_{i=1}^n\sum_{j=1}^kF[i][j] \]
思路：
看到这种奇奇怪怪一大堆的条件，一般就是把看似复杂、冗余的条件变得简单，就像B题一样。
我们注意到这是个\(01\)矩阵，那么每个位置上的数可以表示为“可达关系”，\(k\)次方就是走\(k\)步之后的可达关系。
大组合数取模相关的问题我们一般可以联想到lucas定理，这个题的题面反过来也是lucas定理。lucas定理其实就是将组合数的两个参数拆成\(p\)进制每位来求，如果最后大于\(0\)的话也就是对于\({n\choose m}\)来说\(n\geq m\)，不会出现\(n<m\)的情况。
如果走\(k\)步之后还为\(1\)，说明矩阵中相应\(k\)个数值都满足上述情况。也就是\(\displaystyle{i\choose j}{j\choose k}\cdots{s\choose t}\)每一个数拆分为\(p\)进制过后，都要满足上述关系，以第一位为例，就要满足\(i_1\geq j_1\geq k_1\geq\cdots\geq s_1\geq t_1\)。那么我们可以每一位单独考虑。最后每一位的结果乘起来就行。
因为矩阵大小为\(p^n\)，就相当于\(p\)进制下\(n\)位的所有情况，每个数取值范围为\([0,p-1]\)，这又是一个经典的组合数问题，我们用\(x_i\)表示值为\(i\)的数的个数有多少个，然后隔板算一算就行。
分析到这里，这个题已经明了了，最后那个求和式很简单，就是个等比数列求和。主要是将海绵宝宝矩阵的性质分析清楚，矩阵求和其实就是能够枚举组合数的所有情况。然后组合数拆分\(p\)进制单独考虑，最后再加个隔板。。。
写这个题的时候思路比较零碎，想到什么写的什么，大概就是这个意思。。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2020/5/20 10:25:31
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e6 + 5, MOD = 1e9 + 7;
int qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
int primes[N], tot;
bool vis[N];
int fac[N], inv[N];
void init() {
for (int i = 2; i < N; i++) {
if (!vis[i]) {
vis[i] = true;
primes[++tot] = i;
if (tot >= 100000) break;
for (ll j = 1ll * i * i; j < N; j += i) {
vis[j] = true;
}
}
}
fac[0] = 1;
for (int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
inv[N - 1] = qpow(fac[N - 1], MOD - 2);
for (int i = N - 2; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
}
int C(int n, int m) {
return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
void run() {
int n, c, k; cin >> c >> n >> k;
int p = primes[c];
int ans = 0;
for (int i = 1; i <= k; i++) {
int d = C(i + p, p - 1);
if (d == 1) ans = (ans + n) % MOD;
else ans = (ans + 1ll * d * (1 - qpow(d, n) + MOD) % MOD * qpow(1 - d + MOD, MOD - 2) % MOD) % MOD;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
init();
int T; cin >> T; while(T--)
run();
return 0;
}
L - Pinball
模拟/物理题。
Code
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
#define D Point
#define CD const D
#define EPS 1e-6
int dcmp(double x) {return fabs(x)<EPS?0:(x<0?-1:1);}
const double g=9.8;
struct Point { double x,y;};
bool operator==(CD&l, CD&r) {return dcmp(l.x-r.x)==0 && dcmp(l.y-r.y)==0;}
D operator+(CD&l, CD&r) {return (D){l.x+r.x,l.y+r.y};}
D operator-(CD&l, CD&r) {return (D){l.x-r.x,l.y-r.y};}
D operator*(CD&l, double a) {return (D){l.x*a, l.y*a};}
D operator/(CD&l, double a) {return (D){l.x/a, l.y/a};}
double len(CD&l) {return sqrt(l.x*l.x+l.y*l.y);}
double dot(CD&l, CD&r) {return l.x*r.x+l.y*r.y;}
D GetLineProj(CD&p, CD&a, CD&b) {
D v=b-a;
return a+v*(dot(v,p-a)/dot(v,v));
}
D mirror(CD&p, CD&a, CD&b) {
D q=GetLineProj(p,a,b);
return (D){2*q.x-p.x,2*q.y-p.y};
}
double a,b,x,y;
D bounce(CD&v) {
D p1=(D){0,0};
D p2=(D){-b,-a};
D v2=mirror(v,p1,p2);
v2.x=-(v2.x);
v2.y=-(v2.y);
return v2;
}
double run(CD&v) {
double t=2*(b*v.x+a*v.y)/g/a;
return t;
}
#undef D
#undef CD
int n,m;
int main() {
int t; scanf("%d", &t);
while(0<t--) {
scanf("%lf%lf%lf%lf",&a,&b,&x,&y);
Point v;
v.x=0; double down=y-(-x/a*b);
v.y=-sqrt(2*g*down);
Point pos; pos.x=x, pos.y=-x/a*b;
int ans=0;
while(pos.x<0) {
ans++;
v=bounce(v);
double t=run(v);
v.y-=g*t;
pos.x+=v.x*t;
pos.y=-pos.x/a*b;
}
printf("%d\n", ans);
}
}