Codeforces Round 889 (Div. 2)

简介: Codeforces Round 889 (Div. 2)

本次比赛链接:https://codeforces.com/contest/1849


A. Morning Sandwich


Monocarp always starts his morning with a good ol' sandwich. Sandwiches Monocarp makes always consist of bread, cheese and/or ham.


A sandwich always follows the formula:


  • a piece of bread
  • a slice of cheese or ham
  • a piece of bread
  • ……
  • a slice of cheese or ham
  • a piece of bread


So it always has bread on top and at the bottom, and it alternates between bread and filling, where filling is a slice of either cheese or ham. Each piece of bread and each slice of cheese or ham is called a layer.


Today Monocarp woke up and discovered that he has bb pieces of bread, cc slices of cheese and hh slices of ham. What is the maximum number of layers his morning sandwich can have?


Input


The first line contains a single integer tt (1≤t≤10001≤t≤1000) — the number of testcases.


Each testcase consists of three integers b,cb,c and hh (2≤b≤1002≤b≤100; 1≤c,h≤1001≤c,h≤100) — the number of pieces of bread, slices of cheese and slices of ham, respectively.


Output


For each testcase, print a single integer — the maximum number of layers Monocarp's morning sandwich can have.


Example


Example


input

1. 3
2. 2 1 1
3. 10 1 2
4. 3 7 8

output

1. 3
2. 7
3. 5


Note


In the first testcase, Monocarp can arrange a sandwich with three layers: either a piece of bread, a slice of cheese and another piece of bread, or a piece of bread, a slice of ham and another piece of bread.


In the second testcase, Monocarp has a lot of bread, but not too much filling. He can arrange a sandwich with four pieces of bread, one slice of cheese and two slices of ham.


In the third testcase, it's the opposite — Monocarp has a lot of filling, but not too much bread. He can arrange a sandwich with three pieces of bread and two slices of cheese, for example.


思路:除去第一片面包,剩下的面包片数量等于料的数量,直接找到最小值乘二加上第一片面包


AC代码:


#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
void solve()
{
  int m,a,b,maxx=0,aa=0;
  cin>>m>>a>>b;
  aa=m-1;
  maxx=min(aa,a+b);
  cout<<maxx*2+1<<endl;
    return ;
}
signed main()
{
  int t=1;
  cin>>t;
  while(t--) solve();
  return 0;
}


B. Monsters


Monocarp is playing yet another computer game. And yet again, his character is killing some monsters. There are nn monsters, numbered from 11 to nn, and the ii-th of them has aiai health points initially.


Monocarp's character has an ability that deals kk damage to the monster with the highest current health. If there are several of them, the one with the smaller index is chosen. If a monster's health becomes less than or equal to 00 after Monocarp uses his ability, then it dies.


Monocarp uses his ability until all monsters die. Your task is to determine the order in which monsters will die.


Input


The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.


The first line of each test case contains two integers nn and kk (1≤n≤3⋅1051≤n≤3⋅105; 1≤k≤1091≤k≤109) — the number of monsters and the damage which Monocarp's ability deals.


The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the initial health points of monsters.


The sum of nn over all test cases doesn't exceed 3⋅1053⋅105.


Output


For each test case, print nn integers — the indices of monsters in the order they die.


Example


input

1. 3
2. 3 2
3. 1 2 3
4. 2 3
5. 1 1
6. 4 3
7. 2 8 3 5

output

1. 2 1 3
2. 1 2
3. 3 1 2 4


Note


In the first example, the health points change as follows: [1,2,3–]→[1,2–,1]→[1–,0,1]→[−1,0,1–]→[−1,0,−1][1,2,3_]→[1,2_,1]→[1_,0,1]→[−1,0,1_]→[−1,0,−1]. The monster that is going to take damage the next time Monocarp uses his ability is underlined.


In the second example, the health points change as follows: [1–,1]→[−2,1–]→[−2,−2][1_,1]→[−2,1_]→[−2,−2].


In the third example, the health points change as follows: [2,8–,3,5]→[2,5–,3,5]→[2,2,3,5–]→[2,2,3–,2]→[2–,2,0,2]→[−1,2–,0,2]→[−1,−1,0,2–]→[−1,−1,0,−1][2,8_,3,5]→[2,5_,3,5]→[2,2,3,5_]→[2,2,3_,2]→[2_,2,0,2]→[−1,2_,0,2]→[−1,−1,0,2_]→[−1,−1,0,−1].


思路:将每个血量模上伤害值后放进结构体数组,对于能整除伤害值的不做操作,然后按从大到小排一下序,输出对应下标即可


AC代码:


#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
struct s{
  int x,y;
}a[310000];
bool cmp(s aa,s bb)
{
  if(aa.x==bb.x)
  return aa.y<bb.y;
  else
  return aa.x>bb.x;
}
void solve()
{
  int n,k;
  scanf("%lld%lld",&n,&k);
  for(int i=1;i<=n;i++)
  {
  scanf("%lld",&a[i].x);
  if(a[i].x%k!=0)
  a[i].x=a[i].x%k;
  else
  a[i].x=k;
  a[i].y=i;
  }
  sort(a+1,a+1+n,cmp);
  for(int i=1;i<=n;i++)
  printf("%lld ",a[i].y);
  printf("\n");
    return ;
}
signed main()
{
  int t;
  scanf("%lld",&t);
  while(t--) solve();
  return 0;
}


C. Binary String Copying

You are given a string ss consisting of nn characters 0 and/or 1.


You make mm copies of this string, let the ii-th copy be the string titi. Then you perform exactly one operation on each of the copies: for the ii-th copy, you sort its substring [li;ri][li;ri] (the substring from the lili-th character to the riri-th character, both endpoints inclusive). Note that each operation affects only one copy, and each copy is affected by only one operation.


Your task is to calculate the number of different strings among t1,t2,…,tmt1,t2,…,tm. Note that the initial string ss should be counted only if at least one of the copies stays the same after the operation.


Input


The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.


The first line of each test case contains two integers nn and mm (1≤n,m≤2⋅1051≤n,m≤2⋅105) — the length of ss and the number of copies, respectively.


The second line contains nn characters 0 and/or 1 — the string ss.


Then mm lines follow. The ii-th of them contains two integers lili and riri (1≤li≤ri≤n1≤li≤ri≤n) — the description of the operation applied to the ii-th copy.


The sum of nn over all test cases doesn't exceed 2⋅1052⋅105. The sum of mm over all test cases doesn't exceed 2⋅1052⋅105.


Output


Print one integer — the number of different strings among t1,t2,…,tmt1,t2,…,tm.


Example


input

1. 3
2. 6 5
3. 101100
4. 1 2
5. 1 3
6. 2 4
7. 5 5
8. 1 6
9. 6 4
10. 100111
11. 2 2
12. 1 4
13. 1 3
14. 1 2
15. 1 1
16. 0
17. 1 1

output

1. 3
2. 3
3. 1


Note


Consider the first example. Copies below are given in order of the input operations. Underlined substrings are substrings that are sorted:


101100 →→ 011100;

101100 →→ 011100;

101100 →→ 101100;

101100 →→ 101100;

101100 →→ 000111.

There are three different strings among t1,t2,t3,t4,t5t1,t2,t3,t4,t5: 000111, 011100 and 101100.


Consider the second example:


100111 →→ 100111;

100111 →→ 001111;

100111 →→ 001111;

100111 →→ 010111.

There are three different strings among t1,t2,t3,t4t1,t2,t3,t4: 001111, 010111 and 100111.


AC代码:


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll l[N],r[N];
void work(){
  int n,m;
  string s;
  cin>>n>>m;
  cin>>s;
  s=' '+s;
  l[0]=0;r[n+1]=n+1;
  for(int i=1;i<=n;i++)
  if(s[i]=='1') l[i]=l[i-1];
  else l[i]=i;
  for(int i=n;i>=1;i--)
  if(s[i]=='1') r[i]=i;
  else r[i]=r[i+1];
  set<pair<ll,ll>> se;
  int x,y;
  while(m--){
  cin>>x>>y;
  x=r[x];
  y=l[y];
  if(x>=y) x=y=-1;
  se.insert({x,y});
  }
  printf("%d\n",se.size());
}
int main(){
  int t;
  cin>>t;
  while(t--)
  work();
  return 0;
}

目录
相关文章
|
5月前
Codeforces Round #729 (Div. 2)
【6月更文挑战第4天】在这两个编程问题中,B. Plus and Multiply 要求判断通过加法和乘法操作数组是否能形成目标数 `n`。思路是形如 `x^a + yb = n` 的表达式,如果满足则能构造。C. Strange Function 关注的是找到最小正整数 `x` 使得 `x` 不是 `i` 的因子,计算这些值的和模 `10^9+7`。对于每个 `i`,偶数时 `f(i)` 是 3,奇数时是 2,利用因子与最大公约数计算周期性求和。
30 1
|
机器学习/深度学习 人工智能 移动开发
.Codeforces Round 883 (Div. 3)
Codeforces Round 883 (Div. 3)
|
人工智能
Codeforces Round #786 (Div. 3)(A-D)
Codeforces Round #786 (Div. 3)(A-D)
70 0
|
索引
Codeforces Round 817 (Div. 4)
Codeforces Round 817 (Div. 4)A~G题解
106 0
Codeforces Round #675 (Div. 2) A~D
Codeforces Round #675 (Div. 2) A~D
152 0
Codeforces Round #644 (Div. 3)(A~G)
Codeforces Round #644 (Div. 3)(A~G)
121 0