Codeforces Round #710 (Div. 3)
A.Strange Table
输入样例:
5
1 1 1
2 2 3
3 5 11
100 100 7312
1000000 1000000 1000000000000
输出样例:
1
2
9
1174
1000000000000
//找规律
//求该数在列顺序表示的 位置对应在行顺序的位置
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
ll m,n,x;
cin >> m >> n >>x;
ll t1=x/m+(x%m!=0);//注意体会x%m的巧妙
ll t2=x%m;//行
if(t2==0) t2=m;
cout<<(t2-1)*n+t1<<endl;
}
int main()
{ int t;
cin >> t;
while(t--){
solve();
}
}
B. Partial Replacement
输入样例:
5
7 3
.**.***
5 1
..*..
5 2
*.*.*
3 2
*.*
1 1
*
输出样例:
3
1
3
2
1
/*
题意:
第一个'*'要改成'X'
最后一个'*'要改成'X'
但是两个'X'之间的距离不能超过 k
思路:
贪心的思想(在满足条件的情况下使得两个'*'尽可能远)
固定左边的 '*', 挪动右边的 '*'
记得把该区间改成'.'
*/
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n,k,m;
cin >> n >> k;
getchar();
string s;
cin >> s;
for(int i=0;i<s.size();i++){
if(s[i]=='*'){
int cnt=k;
int x=i;
while(1+x<s.size() && cnt--){
if(s[++x]=='*') m=x;
}
for(int j=i+1;j<m;j++) s[j]='.';
}
}
int cnt = 0;
for(char i:s) if(i == '*') cnt++;
cout<<cnt<<endl;
}
int main(){
int t;
cin >> t;
while(t--)
solve();
}
C. Double-ended Strings
输入样例:
5
a
a
abcd
bc
hello
codeforces
hello
helo
dhjakjsnasjhfksafasd
adjsnasjhfksvdafdser
输出样例:
0
2
13
3
20
#include<bits/stdc++.h>
using namespace std;
/*
题意:
给定两个字符串a,b(有四种操作)
1)删去 a 的第一个字符
2)删去 a 的最后一个字符
3)删去 b 的第一个字符
4)删去 b 的最后一个字符
思路:
求两个字符串的最长子串
*/
void solve(){
string a,b;
cin >> a >> b;
int k=0;
for(int i=0;i<a.size();i++){
for(int j=0;j<b.size();j++){
if(a[i] == b[j]){//注意括号的位置
int cnt=1;
while(i + cnt<a.size() && j+cnt <b.size()){
if(a[i+cnt]==b[j+cnt]) cnt++;
else break;
}
k = max(k,cnt);
}
}
}
cout<<a.size()-k+b.size()-k<<endl;
}
int main(){
int t;
cin >> t;
while(t--)
solve();
}
Codeforces Round #615 (Div. 3)
A. Collecting Coins
输入样例:
5
5 3 2 8
100 101 102 105
3 2 1 100000000
10 20 15 14
101 101 101 3
输出样例:
YES
YES
NO
NO
YES
/*
题意:使最后三个数字都相等
错解:
刚开始我的思路是把所有的 4 个数加起来
通过和除以3是否有余数的结果来判断 Yes /No
其实是不对的
5 3 2 2
正解:(补齐)
先补齐两个较小的数字和第三个数字相同
再看剩下的数字能否被 3 整除
(记得特判 n<0 的情况)
*/
#include<bits/stdc++.h>
using namespace std;
int t,n;
int a[4];
void solve(){
for(int i=0;i<3;i++) cin >>a[i];
cin >> n;
sort(a,a+3);
n-=(2*a[2]-a[1]-a[0]);
if(n<0 || n%3!=0) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
int main(){
cin>>t;
while(t--){
solve();
}
return 0;
}
B. Collecting Packages
输入样例:
3
5
1 3
1 2
3 3
5 5
4 3
2
1 0
0 1
1
4 3
输出样例:
YES
RUUURRRRUU
NO
YES
RRRRUUU
/*
题意:
只能向右或者向下走
然后给出每个包裹所在坐标
求出拿到所有包裹的最短路径
*/
https://www.acwing.com/blog/content/1745/
https://www.acwing.com/blog/content/6762/
二分 + 前缀和
1227. 分巧克力
#include<bits/stdc++.h>
using namespace std;
/*
为什么考虑二分呢,
因为如果边长从 1 开始列举,可能太繁琐会超时
使边长尽量大
*/
const int N=1e5+10;
typedef long long ll;
int b[N],a[N];
int n,k;
int check(int x){
ll sum=0;
for(int i=0;i<n;i++){
sum+=(a[i]/x)*(b[i]/x);
} if(sum>=k) return 1;
else return 0;
}
int main()
{
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++) cin>>a[i]>>b[i];
int l=0,r=1e5;
while(l<r){//l,r表示的是边长
int mid=(r+l+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<r<<endl;
return 0;
}
AcWing 796. 子矩阵的和
#include <bits/stdc++.h>
using namespace std;
//二维矩阵前缀和
//注意下标 从 1 开始
const int N = 1010;
int sum[N][N], n, m, k;
int main(){
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
cin >>sum[i][j];
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
for(int i = 1; i <= k; i++){
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", sum[x2][y2] + sum[x1 - 1][y1 - 1] - sum[x2][y1 - 1] - sum[x1 - 1][y2]);
}
return 0;
}
//两个数组
#include<bits/stdc++.h>
const int N = 1010;
int n,m,q;
int a[N][N], s[N][N];
int main()
{
scanf("%d%d%d",&n,&m,&q);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
while (q--)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);
}
return 0;
}
AcWing 795. 前缀和
#include<bits/stdc++.h>
using namespace std;
/*
输入一个长度为n的整数序列。
接下来再输入m个询问,每个询问输入一对l, r。
对于每个询问,
输出原序列中从第l个数到第r个数的和
*/
const int N = 1e5+10;
int sum[N];
int a[N];
int main(){
int n,m;
cin >> n >>m;
for(int i=1;i<=n;i++) {
cin >> a[i];
sum[i]=sum[i-1]+a[i];//求前缀和
}
while(m--){
int x,y;
cin >> x >> y;
cout<<sum[y]-sum[x-1]<<endl;
}
return 0;
}
790. 数的三次方根
#include<bits/stdc++.h>
using namespace std;
double n,l,r,mid;
double q(double a){return a*a*a;}
int main(){
cin>>n;
l=-10000,r=10000;
while(r-l>=1e-7){
mid=(l+r)/2;
if(q(mid)>=n) r=mid;
else l=mid;
}
printf("%.6f",l);
return 0;
}
#include<cstdio>
#include<cmath>
int main(){
double a;
scanf("%lf",&a);
printf("%.6lf",cbrt(a));//直接调用函数求立方根
return 0;
}
789. 数的范围
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, q, k, a[N];
int main(){
scanf("%d%d", &n, &q);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
while(q--){
int x;
scanf("%d", &x);
int l = 0, r = n - 1;
while(l < r){
int mid = (l + r >> 1);
if(a[mid] >= x) r = mid;
else l = mid + 1;
}
if(a[l] != x){
puts("-1 -1");
continue;
}
printf("%d ", l);
l = 0, r = n - 1;
while(l < r){
int mid = (l + r + 1 >> 1);
if(a[mid] <= x) l = mid;
else r = mid - 1;
}
printf("%d\n", r);
}
return 0;
}
Codeforces Round #598 (Div. 3)
A. Payment Without Change
#include<bits/stdc++.h>
using namespace std;
/*
4
1 2 3 4
1 2 3 6
5 2 6 27
3 3 5 18
YES
NO
NO
YES
*/
/*
题意:
是否能凑成总价值为 S;
x*n + y = s;
可以用 s % n 得到的值与 y 来比较
*/
int main()
{
int q;
long long a, b, n, s;
scanf("%d", &q);
while (q--)
{
scanf("%lld%lld%lld%lld", &a, &b, &n, &s);
if (a*n + b >= s)
{
s = s % n;
if (s <= b)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
else
{
printf("NO\n");
}
}
return 0;
}
B. Minimize the Permutation
思路:记录下每个数字的初始位置,然后尽量让每个数都回到和该数字相同的位置上,比如让数字1回到下标1的位置
#include<bits/stdc++.h>
using namespace std;
const int N=105;
bool st[N];
int pos[N];
int a[N];
int main(){
int T;cin>>T;
while(T--){
memset(st,false,sizeof st);
memset(pos,0,sizeof pos);
memset(a,0,sizeof a);
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
pos[a[i]]=i;
}
int t=n-1;
int idx=1;
for(int i=1;i<=n;i++){
int flag=1;
while(flag){
if(pos[i]!=i&&!st[pos[i]-1]){
st[pos[i]-1]=true;
swap(a[pos[i]],a[pos[i]-1]);
swap(pos[a[pos[i]]],pos[a[pos[i]-1]]);
}else{
flag=0;
}
}
st[pos[i]]=true;
}
for(int i=1;i<=n;i++) cout<<a[i]<<' ';
cout<<endl;
}
return 0;
}
D. Binary String Minimizing
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
int q;
cin >> q;
while (q--) {
int n;
long long k;
cin >> n >> k;
string s;
cin >> s;
int j = 0;
for (int i = 0; i < n; i++) {
if (j < i) j = i;
while (j < n && s[j] != '0') j++; //判断前面某个0前面有几个1
if (j < n && j - i <= k) {//判断能否直接换过去
swap(s[i], s[j]);
k -= j - i;
}
}
cout << s << endl;
}
return 0;
}
/*
in:
3
8 5
11011010
7 9
1111100
7 11
1111100
ans:
01011110
0101111
0011111
*/
Codeforces Round #713 (Div. 3)
B. Almost Rectangle
input
6
4
..*.
....
*...
....
2
*.
.*
2
.*
.*
3
*.*
...
...
5
.....
..*..
.....
.*...
.....
4
....
....
*...
*...
output
*.*.
....
*.*.
....
**
**
**
**
*.*
*.*
...
.....
.**..
.....
.**..
.....
....
....
**..
**..
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 405;
char a[maxn][maxn];
int main()
{
int t;
cin >> t;
while(t--)
{
vector<int> r;
vector<int> c;
int n;
cin >> n;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
cin >> a[i][j];
if(a[i][j] == '*'){
r.push_back(i), c.push_back(j);
}
}
}
int r1, c1, r2, c2;
if(r[0] == r[1]){
if(r[0] + 1 < n){
r1 = r2 = r[0] + 1;
c1 = c[0], c2 = c[1];
}
else {
r1 = r2 = r[0] - 1;
c1 = c[0], c2 = c[1];
}
}
else if(c[0] == c[1]){
if(c[0] + 1 < n){
c1 = c2 = c[0] + 1;
}
else{
c1 = c2 = c[0] - 1;
}
r1 = r[0], r2 = r[1];
}
else{
r1 = r[0], c1 = c[1];
r2 = r[1], c2 = c[0];
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if((i == r1 && j == c1) || (i == r2 && j == c2)){
cout << '*';
}
else cout << a[i][j];
}
cout << endl;
}
}
return 0;
}
Codeforces Round #719 (Div. 3)
A. Do Not Be Distracted!
in
5
3
ABA
11
DDBBCCCBBEZ
7
FFGZZZY
1
Z
2
AB
out
NO
NO
YES
YES
YES
#include <bits/stdc++.h>
using namespace std;
/*
不能重复出现过
前后比较
标记flag 用来标记已经出现过且还是前后不一样
*/
int t,n;
string s;
int main()
{
cin >> t;
while(t--){
map<char,int> mp;
mp.clear();//清空
cin>> n;
getchar();
cin >> s;
mp[s[0]]++;
int flag=1;
for(int i=1;i<s.size();i++){
if(mp[s[i]] && s[i]!= s[i-1]){
flag=0;
break;
}
mp[s[i]]++;
}
if(flag==0) cout<<"NO"<<endl;
else cout<<"Yes"<<endl;
}
}
B. Ordinary Numbers
in
6
1
2
3
4
5
100
out
1
2
3
4
5
18
#include <bits/stdc++.h>
using namespace std;
/*
求从1到n中有多少个数字,
满足它的每一位上的数字都相等
*/
int t,n;
string s;
int a[15] = {0,9,18,27,36,45,54,63,72,81,90,99};
int main()
{
cin >> t;
getchar();
while(t--){
cin >> s;
int len = s.size();
int cnt = a[len-1];//基础
for(char i = '1' ; i <= '9' ; i ++)
{
string s1 = "" ;
for(int j = 0 ; j < len ; j ++)
{
s1 += i ;
}
if(s >= s1) cnt++ ;
}
cout<<cnt<<endl;
}
return 0;
}
D. Same Differences
解题思路:题意求$aj-ai = j-i$有多少对相等的
可以把原式变形 $aj-j = ai -i$
利用$map$容器存储 $ai-i$的次数
需要注意的就是统计用long long类型,会爆int
#include <bits/stdc++.h>
using namespace std;
/*
aj-ai=j-i
算一个数组有多少对
把式子变形 aj-j = ai-i;
*/
int t,n;
string s;
const int N =2e5+10;
int a[N];
typedef long long ll;
int main()
{
cin >> t;
// getchar();
while(t--){
map<int,int>mp;
mp.clear();
cin >> n;
for(int i=1;i<=n;i++) cin >>a[i];
ll sum=0;//统计要开longlong!
for(int i=1;i<=n;i++){
sum+=mp[a[i]-i];
mp[a[i]-i]++;
}
cout<<sum<<endl;
}
return 0;
}
C. Not Adjacent Matrix
解题思路:
构造问题,我们是要让相邻单元格的差值不为$1$,所以我们自然能想到用奇数和奇数相邻,偶数和偶数相邻,所以我们可以先从小到大填充所有的奇数,填完奇数之后再从小到大填充完所有的偶数。
除了$ n=2 $ 不满足情况,其他都可以
n = 3的时候可以这样排列
3
1 3 5
7 9 2
4 6 8
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
奇数和奇数相邻,偶数和偶数相邻
先排奇数后偶数
9 = 1 3 5 7 9
2 4 6 8
*/
int t,n;
const int maxn = 110;
int a[maxn][maxn];
int main(){
cin>>t;
while(t--){
cin>>n;
if(n==2)cout<<-1<<endl;
else{
int odd=1,even=2;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(odd>n*n){
a[i][j]=even;
even+=2;
}
else{
a[i][j]=odd;
odd+=2;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
}
return 0;
}
https://blog.csdn.net/hzf0701/article/details/116432695
https://blog.csdn.net/yueshehanjiang/article/details/116433400
Codeforces Round #481 (Div. 3)
A. Remove Duplicates
本题特别的点:它最后要的数列是删去重复的保留最后剩下的那个书数
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1005;
int a[N];
int b[N];
map<int,int> mp;
/*
in
6
1 5 5 1 6 1
out
3
5 6 1
*/
int main(){
int n,x;
cin >> n;
for(int i=0;i<n;i++){
cin >> x;
a[i] = x;
}
int t =0;
for(int i=n-1;i>=0;i--){
if(!mp[a[i]]) {
mp[a[i]]=1;
b[t++] = a[i];
}
}
cout<<t<<endl;
for(int i=t-1;i>=0;i--){
cout<<b[i]<<" ";
}
cout<<endl;
return 0;
}
B. File Name
/*
保证就只有两个连续的'x',
要执行的操作
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1005;
int a[N];
int b[N];
map<int,int> mp;
/*
in
10
xxxxxxxxxx
out
8
注意这个样例,如果你的循环只是读到s.size()
那么就不会执行else 那么sum的值就不会被计算
故在循环的时候记得+1
*/
//int main(){
// int n,cnt=0,ans=3,sum=0;
// cin >> n;
// string s;
// getchar();
// cin >> s;
// int k =s.size();
// for(int i=0;i<=k;i++){
//
// if(s[i]=='x') cnt++;
// else{
// if(cnt>=ans) {
// sum=sum+cnt-2;
// // cout<<sum<<endl;
// // cnt = 0;
// }
// cnt = 0;
// }
// }
//
// cout<<sum<<endl;
// return 0;
//}
//改进后
#include <bits/stdc++.h>
using namespace std;
int n,cnt=0;
string s;
int main(){
cin >> n;
getchar();
cin >> s;
for(int i=0;i<n-2;i++){
if(s[i]=='x'&& s[i+1]=='x'&&s[i+2]=='x') cnt++;
}
cout<<cnt<<endl;
return 0;
}
C. Letters
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
有很多个宿舍,每个宿舍有很多的房间
最后输出的结果是哪个宿舍的哪个房间
先求美个房间的前缀和
用lower_bound大于等于该房间的位置
*/
const int N =2e5+10;
ll sum[N];
int main(){
ll n,m,x,y;
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> x;
sum[i] = sum[i-1]+x;//求前缀和
}
for(int i=1;i<=m;i++){
cin >> y;
ll pos = lower_bound(sum+1,sum+1+n,y) - sum;
cout<<pos<<" "<<y-sum[pos-1]<<endl;
}
}
D. Almost Arithmetic Progression
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
ll a[100010],b[100010];
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
}
ll ans=0,minn=INF,d;
int flag;
for(int i=-1;i<=1;i++)
{
for(int j=-1;j<=1;j++)
{
ans=0;
flag=1;
ans+=abs(i)+abs(j);//累加修改元素的个数
b[0]=a[0]+i;//对第一个元素遍历操作
b[1]=a[1]+j;//对第二个元素遍历操作
d=b[1]-b[0];//确定了前两个元素即可确定公差
for(int k=2;k<n;k++)//对后n-2个元素判断
{
if(abs((b[k-1]+d)-a[k])<=1)//如果该元素能够修改成为等差数列里的元素
{
b[k]=b[k-1]+d;//则确定这个元素
ans+=abs(b[k]-a[k]);//累加修改元素的步数
}
else
{
flag=0;
break;
}
}
if(flag)
{
if(ans<minn) minn=ans;
}
}
}
if(minn<INF) printf("%lld\n",minn);
else printf("-1\n");
}
return 0;
}
E. Bus Video System
#include <bits/stdc++.h>
using namespace std;
/*
in
3 5
2 1 -3
out
3
*/
const int MAXN=200010;
const int INF=0x3f3f3f3f;
int sum[MAXN];
int main()
{
int n,w,a;
scanf("%d%d",&n,&w);
int MAX=0,MIN=INF;
for (int i = 1; i <=n ; ++i) {
scanf("%d",&a);
sum[i]=sum[i-1]+a;
MAX=max(MAX,sum[i]);
MIN=min(MIN,sum[i]);
}
MAX=w-MAX;
MIN=MIN>0?0:-MIN;
if(MAX-MIN+1<0) printf("0\n");
else printf("%d\n",MAX-MIN+1);
return 0;
}
Codeforces Round #702 (Div. 3)
C. Sum of Cubes
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
先固定一个值,
二分判断相减得到的另一个数是否为立方数即可
*/
ll T;
ll cnt = 0,n;
const int N = 10010;
ll a[N];
void init(){//记得开longlong
for(ll i=1;i<=10000;i++) a[++cnt]=i*i*i;
}
int main()
{
init();
cin >> T;
while(T--){
cin >> n;
int flag=0;
for(ll i=1;i<=cnt;i++){
ll x = a[i];
ll y = n - x;
ll pos = lower_bound(a+1,a+1+cnt,y)-a;
if(a[pos]== y){
flag = 1;
break;
}
}
if(flag==1) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
A. Dense Array
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
贪心的策略
选择minn 两倍的值
*/
int T;
const int N =1100;
int a[N];
void solve(){
int n;
int sum =0;
cin >> n;
for(int i=0;i<n;i++) cin >> a[i];
for(int i=1;i<n;i++){
int minn = min(a[i],a[i-1]);
int maxx = max(a[i],a[i-1]);
while(minn*2<maxx){
sum++;
minn*=2;
}
}
cout<<sum<<endl;
}
int main()
{
cin >> T;
while(T--){
solve();
}
return 0;
}
B. Balanced Remainders
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
1 1 4
c0 c1 c2
*/
int T;
const int N =1100;
int a[N];
void solve(){
int n,x,sum=0;
cin >> n;
for(int i=0;i<n;i++){
cin >> x;
a[x%3]++;
}
// for(int i=0;i<=2;i++) cout<<a[i]<<endl;
n/=3;//平均数
if(a[0]<n){
if(a[1]>n) sum+=2*(a[1]-n);
if(a[2]>n) sum+=a[2]-n;
}
else if(a[1]<n){
if(a[0]>n) sum+=a[0]-n;
if(a[2]>n) sum+=2*(a[2]-n);
}
else if(a[2]<n){
if(a[0]>n) sum+=2*(a[0]-n);
if(a[1]>n) sum+=a[1]-n;
}
cout<<sum<<endl;
}
int main()
{
cin >> T;
while(T--){
memset(a,0,sizeof(a));
solve();
}
return 0;
}
Codeforces Round #735 (Div. 2)
B. Cobb
/*
题意:给定一个数组 a和 一个正整数 k
求f(i,j)max =i*j-k*(a[i]|a[j])
思路:i*j<n*n,k(a[i]|a[j])<2nk (所以i*j二次方对式子影响较大)
i和j最大可以取n-1/n,故问题转换为求最小的 i 的最大值应该是多少
f(n-1,n) = n*(n-1)-2kn=n^2-2kn-n;
使得f(i,n) = i*n > n^2-2kn-n;
即最小的 i = n-2k;
*/
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int a[N];
void solve(){
ll n,k,ans=-1e12;
cin >> n >>k;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=max(1ll,n-200);i<n;i++){
for(int j =i+1;j<=n;j++){
ans = max(ans,i*1ll*j-k*(a[i]|a[j]));
}
}
cout<<ans<<endl;
}
int main(){
int t;cin >> t;
while(t--){
solve();
}
return 0;
}