沈阳成为焦点：首个万能杯ICPC亚洲赛拉开帷幕

D. DRX vs. T1

time limit per test

1 second

memory limit per test

512 megabytes

  

The League of Legends Worlds Championship, Worlds for short, is the culminating event in the LoL Esports season and decides the ultimate global League of Legends Champion.

Worlds 2022 has been a great tournament thus far. We have seen the legend, Faker, rise once more and the surprise of the DRX run. There have also been massive collapses from other teams like Gen.G and JDG. Regardless, we are in for a compelling Worlds 2022 Finals, which kicks off on November 6 at 08:00 (UTC+8) in San Francisco as DRX and T1 face off.

Being the clear favorite for winning the Finals, T1 has performed dominantly in most games and has found its stride coming into the tournament. They have taken down RNG and JDG, two LPL heavyweights, and are now poised to add another trophy to their cabinet.

On the other side, DRX has practically come out of nowhere. From almost not making Worlds 2022, fighting their way through the Regionals and Play-ins to the Finals. It is a Cinderella run that DRX is on, and they have been doubted at every step of the tournament. With a lot to prove and Deft reaching the Finals in his swan song, winning the trophy might be the best send-off any player can wish for.

As we countdown to a battle for the all-new trophy, you will be given the predicted result of the Finals and required to find which team wins the championship under the prediction. A team must win three out of five games to win the championship, so the predicted result of the Finals is a string of length 55 containing only DDs, TTs, and ??s. The ii-th character in the string points out who wins the ii-th game, where DD means DRX wins the game, TT means T1 wins the game, and ?? means no more games are needed since some team has already won 33 games and become the champion.

  

Input

The only line contains a single string of length 55 containing only DDs, TTs, and ??s, indicating the predicted result of the Worlds 2022 Finals.

It is guaranteed that the predicted result is a valid BO5 result, that is, no ??s are before any DDs and TTs, and there exists a team who wins exactly three games.

  

Output

Output a line containing a single string, indicating the team that wins the champion under the prediction. That is, if DRX wins the champion, output “DRX” (without quotes), and if T1 wins, output “T1” (without quotes).

Examples

Input

Copy

TDTT?

Output

Copy

T1

Input

Copy

DTDD?

Output

Copy

DRX

  

Note

In the first sample case, T1 wins the first game, DRX wins the second game, T1 wins the third and the fourth game and wins the champion, so the fifth game is not needed anymore.

• 题目描述

  英雄联盟世界赛决赛采用 BO5 （五局三胜制）。给出预测比赛结果的字符串 sss，长度为 555，每个字符表示该局比赛的胜利者或未进行比赛：

  • D 表示 DRX 胜出。
  • T 表示 T1 胜出。
  • ? 表示该局比赛未进行（因为已有队伍达到三胜）。

  要求判断哪支队伍赢得了总冠军。

  输入

  一个长度为 555 的字符串 sss，包含字符 D , T , ? 。

  输出

  若 DRX 赢得冠军，输出 "DRX" ；若 T1 赢得冠军，输出 "T1" 。

  ---

  解题思路

  1. 遍历字符串 sss，分别统计 D 和 T 的数量。
  2. 一旦某队达到三胜即结束比赛。
  3. 因为保证输入为有效 BO5 预测，逻辑中无需额外处理 ? 。

C++代码实现：

#include<bits/stdc++.h>usingnamespace std;#defineintlonglongint#definePaddiios::sync_with_stdio(false),cin.tie(0),cout.tie(0)signedmain(){
    map<char,int> mp;
    string s;
    cin >> s;for(auto it:s){
        mp[it]++;}if(mp['D']<mp['T']){
        cout <<"T1";}if(mp['D']> mp['T']){
        cout <<"DRX";}return0;}

C. Clamped Sequence

time limit per test

1 second

memory limit per test

512 megabytes

  

Given an integer sequence a1,a2,…,ana1,a2,…,an and a positive integer dd, you need to clamp the sequence to a range [l,r][l,r] satisfying 0≤r−l≤d0≤r−l≤d that maximize ∑n−1i=1|ai−ai+1|∑i=1n−1|ai−ai+1|, where |x||x| is the absolute value of xx.

More specifically, clamping the sequence to the range [l,r][l,r] makes each element

ai:=⎧⎩⎨⎪⎪l,ai,r,ai<l;l≤ai≤r;ai>r.ai:={l,ai<l;ai,l≤ai≤r;r,ai>r.

Both ll and rr are arbitrary real numbers decided by you under the given constraints. It can be shown that the maximum sum is always an integer.

  

Input

The first line contains two integers nn (2≤n≤50002≤n≤5000) and dd (1≤d≤109)1≤d≤109), denoting the length of the given sequence and the given parameter respectively.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109−109≤ai≤109), denoting the given sequence.

  

Output

Output a line containing a single integer, denoting the maximum sum.

Example

Input

Copy

8 3
3 1 4 1 5 9 2 6

Output

Copy

15

  

Note

In the sample case, you can clamp the given sequence to the range [1,4][1,4] to make it [3,1,4,1,4,4,2,4][3,1,4,1,4,4,2,4], and the resulting sum is the maximum 1515.

题目描述

给定一个长度为 nnn 的整数序列 aaa，和一个正整数 ddd。需要选择两个整数 lll 和 rrr，使得以下条件成立：

1. 所有元素被限制在范围

   [l,r][l, r][l,r]

   内：

   • 若 a[i]<la[i] < la[i]<l，则 a[i]=la[i] = la[i]=l。
   • 若 a[i]>ra[i] > ra[i]>r，则 a[i]=ra[i] = ra[i]=r。

2. r−l≤dr - l \leq dr−l≤d。

3. 最大化经过约束后的新序列的相邻差值绝对值之和。

输入

• 第一行两个整数 nnn 和 ddd。
• 第二行 nnn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_na1,a2,…,an。

输出

输出一个整数，表示经过约束后序列的最大相邻差值和。

解题思路

1. 枚举可能的 lll 值。
2. 对应的 rrr 为 l+dl + dl+d。
3. 对于每一组 lll 和 rrr，计算序列的新值和差值和。
4. 选择最大值。

C++代码实现：

#include<bits/stdc++.h>usingnamespace std;#defineintlonglong#defineendl'\n'#definecloseios::sync_with_stdio(false),cin.tie(0),cout.tie(0)voidsolved(){int n,d;
	cin>>n>>d;
	vector<int>arr(n+1,0);
	vector<int>index;for(int i=1;i<=n;i++){
		cin>>arr[i];
		index.push_back(arr[i]);
		index.push_back(arr[i]-1);
		index.push_back(arr[i]+1);
		index.push_back(arr[i]-d);
		index.push_back(arr[i]-d+1);
		index.push_back(arr[i]-d-1);}int ans =0;sort(index.begin(),index.end());
	index.erase(unique(index.begin(),index.end()),index.end());for(int i=0;i<index.size();i++){
		vector<int>cnt(n+1,0);for(int j=1;j<=n;j++){if(arr[j]<index[i]){
				cnt[j]= index[i];}elseif(arr[j]>index[i]+d){
				cnt[j]= index[i]+ d;}else{
				cnt[j]= arr[j];}}int result =0;for(int j=1;j<=n-1;j++){
			result +=abs(cnt[j]-cnt[j+1]);}
		ans =max(ans,result);}
	cout<<ans<<endl;}signedmain(){
	close;solved();return0;}

L. Tavern Chess

time limit per test

4 seconds

memory limit per test

512 megabytes

  

One day, Alice and Bob are playing an online chess game named “Tavern Chess”, where each player can choose at most 77 minions to build a team.

Each minion has its Hit Points (HP) and Attack (ATK), and the HP is the same as the ATK initially . A minion with positive HP is alive and can take attacks, and it dies immediately if its HP becomes zero or lower after an attack.

The battle begins after both Alice and Bob finish building their team and lasts until all the minions from one team are dead and the other team wins. In case the last alive minions from the two teams die simultaneously, the battle ends in a tie.

Alice and Bob’s teams take turns to attack, and the team that has more minions takes the first attack. In case of a tie, it will be decided by a coin toss — 50%50% probability for Alice taking the first attack and the remaining 50%50% probability for Bob taking the first attack.

When a team takes the attack, the leftmost minion taking the minimum number of attacks from the team attacks one of the alive minions from the other team uniformly at random, and then the other team takes the attack.

If a minion with the HP h1h1 and the ATK a1a1 attacks another minion with the HP h2h2 and the ATK a2a2, each minion deals damages equal to its ATK to the other one, so the attacker minion will have the HP h1−a2h1−a2 and the attacked minion will have the HP h2−a1h2−a1 after the attack.

Given Alice’s team and Bob’s team, you need to calculate the probabilities that Alice’s team wins the battle, Bob’s team wins the battle, or the battle ends in a tie, respectively.

  

Input

The first line contains two integers nn and mm (1≤n,m≤71≤n,m≤7), indicating the number of minions in Alice’s team and Bob’s team respectively.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109), the ii-th of which is the HP as well as the ATK of the ii-th minions from the left from Alice’s team.

The third line contains mm integers b1,b2,…,bmb1,b2,…,bm (1≤bi≤1091≤bi≤109), the ii-th of which is the HP as well as the ATK of the ii-th minions from the left from Bob’s team.

  

Output

Output three lines, each containing a single real number, indicating the probabilities that Alice’s team wins the battle, Bob’s team wins the battle, or the battle ends in a tie, respectively.

Your answer is acceptable if its absolute error does not exceed 10−910−9. Formally speaking, suppose that your output is aa and the jury’s answer is bb, your output is accepted if and only if |a−b|≤10−9|a−b|≤10−9.

Examples

Input

Copy

2 3
2 5
3 4 1

Output

Copy

0.125000000000 0.750000000000 0.125000000000

Input

Copy

6 6
1 1 4 5 1 4
1 1 4 5 1 4

Output

Copy

0.241867283951 0.241867283951 0.516265432099

题目描述

Alice 和 Bob 在玩一款在线游戏“Tavern Chess”。每人有最多 777 个棋子，每个棋子的生命值（HP）和攻击力（ATK）相等。游戏规则如下：

1. 双方轮流攻击，剩余棋子较多的玩家先攻击，若数量相同则随机决定。
2. 一个棋子攻击后会降低对方棋子的 HP，同时自身也会被对方的 ATK 减少 HP。
3. 若 HP 降为 0 或更低，该棋子死亡。
4. 最终，若所有对方棋子死亡则获胜，同时死亡则平局。

要求计算 Alice 获胜、Bob 获胜和平局的概率。

输入

• 第一行两个整数 nnn 和 mmm，表示 Alice 和 Bob 的棋子数。
• 第二行 nnn 个整数，表示 Alice 棋子的 HP 和 ATK。
• 第三行 mmm 个整数，表示 Bob 棋子的 HP 和 ATK。

输出

三行，分别表示 Alice 获胜、Bob 获胜和平局的概率。

解题思路

1. 使用深度优先搜索（DFS）模拟所有可能的战斗流程。
2. 每次递归模拟攻击过程，记录当前胜负情况。
3. 根据概率规则累加不同结果的概率。
4. 注意剪枝优化，避免重复计算。

C++代码实现：

#include<bits/stdc++.h>usingnamespace std;#defineintlonglongint#defineendl"\n"int n, m;structNode{int x;int y;};
vector<Node> a, b;double ansa, ansb, ansc;voiddfs(vector<Node> a, vector<Node> b,int pd,double sum){if(a.empty()&& b.empty()){
        ansc += sum;return;}if(a.empty()){if(pd){
            ansa += sum;}else{
            ansb += sum;}return;}if(b.empty()){if(pd){
            ansb += sum;}else{
            ansa += sum;}return;}
    sum /= b.size();for(int i =0; i < b.size();++i){
        vector<Node> a2 = a;
        vector<Node> b2 = b;
        a2.erase(a2.begin());if(b[i].y < a[0].x){
            a2.push_back({a[0].x - b[i].y, a[0].y});}if(b[i].x > a[0].y){
            b2[i].x -= a[0].y;}else{
            b2.erase(b2.begin()+ i);}dfs(b2, a2,!pd, sum);}}signedmain(){
    cin >> n >> m;
    a.resize(n);
    b.resize(m);for(int i =0; i < n;++i){
        cin >> a[i].x;
        a[i].y = a[i].x;}for(int i =0; i < m;++i){
        cin >> b[i].x;
        b[i].y = b[i].x;}if(n > m){dfs(a, b,0,1);}if(n < m){dfs(b, a,1,1);}if(n == m){dfs(a, b,0,0.5);dfs(b, a,1,0.5);}
    cout << fixed <<setprecision(10)<< ansa << endl;
    cout << fixed <<setprecision(10)<< ansb << endl;
    cout << fixed <<setprecision(10)<< ansc << endl;}

F. Half Mixed

time limit per test

2 seconds

memory limit per test

512 megabytes

  

Given two integers nn and mm, you need to construct a matrix MM satisfying the following constraints:

• The number of rows and columns of MM are nn and mm respectively.
• The matrix contains only 00s and 11s, namely, Mi,j∈{0,1}Mi,j∈{0,1} for all 1≤i≤n1≤i≤n and 1≤j≤m1≤j≤m.
• The number of mixed subrectangles equals to the number of pure subrectangles. The subrectangles that contain both 00s and 11s are considered as mixed subrectangles, otherwise pure subrectangles. Note that a subrectangle is an intersection of some consecutive rows and some consecutive columns.

If multiple solutions exist, print any one of them. If there is no solution, report it.

  

Input

The first line contains an integer TT (1≤T≤1051≤T≤105), denoting the number of test cases.

For each test case, the only line contains two integers nn and mm (1≤n,m≤1061≤n,m≤106, 1≤n×m≤1061≤n×m≤106), denoting the number of rows and columns respectively.

It is guaranteed that the sum of n×mn×m over all test cases does not exceed 5×1065×106.

  

Output

For each test case, if there is no solution, print “No” (without quotes) in one line. If the solution exists, print “Yes” (without quotes) in the first line. Then print nn lines, the ii-th of which contains mm integers Mi,1,Mi,2,…,Mi,mMi,1,Mi,2,…,Mi,m, describing the ii-th row of the matrix.

Example

Input

Copy

2
2 3
1 1

Output

Copy

Yes
0 1 1
1 1 0
No

  

Note

In the first sample case, the number of mixed subrectangles and pure subrectangles are both 99.

In the second sample case, the only subrectangle is the whole matrix that must be pure, so the number of mixed subrectangles and the number of pure subrectangles must be 00 and 11 respectively, which are not equal.

题目描述

给定一个矩阵 MMM，需要满足：

1. 行数为 nnn，列数为 mmm。
2. 矩阵元素为 0 或 1。
3. 矩阵的混合子矩形数量等于纯子矩形数量。

若无法构造满足条件的矩阵，输出 No ；若可以，输出 Yes 并给出构造的矩阵。

输入

• 第一行一个整数 TTT，表示测试用例数量。
• 接下来的 TTT 行，每行两个整数 nnn 和 mmm。

输出

对每个测试用例：

• 若无法构造矩阵，输出 No 。
• 否则输出 Yes ，并给出矩阵。

解题思路

1. 检查矩阵的行列数是否满足混合与纯子矩形数量相等的条件。
2. 若满足，使用交替块构造满足条件的矩阵。
3. 若不满足，输出 No 。

C++代码实现：

#include<bits/stdc++.h>usingnamespace std;#defineintlonglongint#defineendl"\n"signedmain(){int T;
    cin >> T;while(T--){int n, m;
        cin >> n >> m;if(n *(n +1)%4!=0&& m *(m +1)%4!=0){
            cout <<"No"<< endl;continue;}int flag =0;if(n *(n +1)%4==0){swap(n, m);
            flag =1;}
        vector<int> ans;int tot = m *(m +1)/2;int len = m;while(tot >0){int l =1;int r = len +1;int x =1;while(l<r){int mid =(l + r)/2;if(mid *(mid +1)/2<= tot &&(tot - mid *(mid +1))>=(len - mid)*2){
	                x = mid;
	                l = mid +1;}else{
	                r = mid;}}
            
            ans.push_back(x);
            len -= x;
            tot -=(x *(x +1));}
        vector<vector<int>> tt;
        tt.resize(n +1);int z =0;for(auto it:ans){for(int i =1; i <= n;++i){for(int j =0; j < it;++j){
                    tt[i].push_back(z);}}
            z ^=1;}
        cout <<"Yes"<< endl;if(flag){for(int i =0; i < m;++i){for(int j =1; j <= n;++j){
                    cout << tt[j][i]<<' ';}
                cout << endl;}}else{for(int i =1; i <= n;++i){for(int j =0; j < m;++j){
                    cout << tt[i][j]<<' ';}
                cout << endl;}}}}