codeforces Round #957(Div 2)(ABCD题)

题目链接：https://codeforces.com/contest/1245

A. Good ol' Numbers Coloring

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Consider the set of all nonnegative integers: 0,1,2,…0,1,2,…. Given two integers 𝑎a and 𝑏b (1≤𝑎,𝑏≤1041≤a,b≤104). We paint all the numbers in increasing number first we paint 00, then we paint 11, then 22 and so on.

Each number is painted white or black. We paint a number 𝑖i according to the following rules:

• if 𝑖=0i=0, it is colored white;
• if 𝑖≥𝑎i≥a and 𝑖−𝑎i−a is colored white, 𝑖i is also colored white;
• if 𝑖≥𝑏i≥b and 𝑖−𝑏i−b is colored white, 𝑖i is also colored white;
• if 𝑖i is still not colored white, it is colored black.

In this way, each nonnegative integer gets one of two colors.

For example, if 𝑎=3a=3, 𝑏=5b=5, then the colors of the numbers (in the order from 00) are: white (00), black (11), black (22), white (33), black (44), white (55), white (66), black (77), white (88), white (99), ...

Note that:

• It is possible that there are infinitely many nonnegative integers colored black. For example, if 𝑎=10a=10 and 𝑏=10b=10, then only 0,10,20,300,10,20,30 and any other nonnegative integers that end in 00 when written in base 10 are white. The other integers are colored black.
• It is also possible that there are only finitely many nonnegative integers colored black. For example, when 𝑎=1a=1 and 𝑏=10b=10, then there is no nonnegative integer colored black at all.

Your task is to determine whether or not the number of nonnegative integers colored black is infinite.

If there are infinitely many nonnegative integers colored black, simply print a line containing "Infinite" (without the quotes). Otherwise, print "Finite" (without the quotes).

Input

The first line of input contains a single integer 𝑡t (1≤𝑡≤1001≤t≤100) — the number of test cases in the input. Then 𝑡t lines follow, each line contains two space-separated integers 𝑎a and 𝑏b (1≤𝑎,𝑏≤1041≤a,b≤104).

Output

For each test case, print one line containing either "Infinite" or "Finite" (without the quotes). Output is case-insensitive (i.e. "infinite", "inFiNite" or "finiTE" are all valid answers).

Example

input

Copy

4
10 10
1 10
6 9
7 3

output

Copy

Infinite
Finite
Infinite
Finite

 

#include "iostream"
#include "string.h"
#include "stdio.h"
using namespace std;//题目给出a，b
//0处白色，i>=a && i-a==白色 || i>=b && i-b==白色 ,则i处白色，否则黑色
//问黑色是否是无限的（i可以无限延伸）//这里写了几组数发现，若a和b有大于1的gcd，则白色格子永远不会连续起来；
//若a和b的gcd为1，即a和b互质，则白色格子终会连续到一定数量，这时候黑色格子便是有限的//标准辗转相除法求gcd
long long gcd(long long a,long long b) {while(b^=a^=b^=a%=b);return a;}int main()
{int n ; cin >> n;long long a , b;for(int i = 1 ; i <= n ; i ++){cin >> a >> b;if(gcd(a,b) == 1)printf("Finite\n");elseprintf("Infinite\n");}
}

B. Restricted RPS

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Let 𝑛n be a positive integer. Let 𝑎,𝑏,𝑐a,b,c be nonnegative integers such that 𝑎+𝑏+𝑐=𝑛a+b+c=n.

Alice and Bob are gonna play rock-paper-scissors 𝑛n times. Alice knows the sequences of hands that Bob will play. However, Alice has to play rock 𝑎a times, paper 𝑏b times, and scissors 𝑐c times.

Alice wins if she beats Bob in at least ⌈𝑛2⌉⌈n2⌉ (𝑛2n2 rounded up to the nearest integer) hands, otherwise Alice loses.

Note that in rock-paper-scissors:

• rock beats scissors;
• paper beats rock;
• scissors beat paper.

The task is, given the sequence of hands that Bob will play, and the numbers 𝑎,𝑏,𝑐a,b,c, determine whether or not Alice can win. And if so, find any possible sequence of hands that Alice can use to win.

If there are multiple answers, print any of them.

Input

The first line contains a single integer 𝑡t (1≤𝑡≤1001≤t≤100) — the number of test cases.

Then, 𝑡t testcases follow, each consisting of three lines:

• The first line contains a single integer 𝑛n (1≤𝑛≤1001≤n≤100).
• The second line contains three integers, 𝑎,𝑏,𝑐a,b,c (0≤𝑎,𝑏,𝑐≤𝑛0≤a,b,c≤n). It is guaranteed that 𝑎+𝑏+𝑐=𝑛a+b+c=n.
• The third line contains a string 𝑠s of length 𝑛n. 𝑠s is made up of only 'R', 'P', and 'S'. The 𝑖i-th character is 'R' if for his 𝑖i-th Bob plays rock, 'P' if paper, and 'S' if scissors.

Output

For each testcase:

• If Alice cannot win, print "NO" (without the quotes).
• Otherwise, print "YES" (without the quotes). Also, print a string 𝑡t of length 𝑛n made up of only 'R', 'P', and 'S' — a sequence of hands that Alice can use to win. 𝑡t must contain exactly 𝑎a 'R's, 𝑏b 'P's, and 𝑐c 'S's.
• If there are multiple answers, print any of them.

The "YES" / "NO" part of the output is case-insensitive (i.e. "yEs", "no" or "YEs" are all valid answers). Note that 'R', 'P' and 'S' are case-sensitive.

Example

input

Copy

2
3
1 1 1
RPS
3
3 0 0
RPS

output

Copy

YES
PSR
NO

Note

In the first testcase, in the first hand, Alice plays paper and Bob plays rock, so Alice beats Bob. In the second hand, Alice plays scissors and Bob plays paper, so Alice beats Bob. In the third hand, Alice plays rock and Bob plays scissors, so Alice beats Bob. Alice beat Bob 3 times, and 3≥⌈32⌉=23≥⌈32⌉=2, so Alice wins.

In the second testcase, the only sequence of hands that Alice can play is "RRR". Alice beats Bob only in the last hand, so Alice can't win. 1<⌈32⌉=21<⌈32⌉=2.

 

#include "iostream"
#include "string.h"
#include "math.h"
#include "stdio.h"
using namespace std;//认真读题，暴力模拟
int main()
{int t , n ;int a , b , c;string str;string tmp = "";cin >> t ;for(int i = 1 ; i <= t ; i ++){tmp = "";cin >> n;//R石头 P布 S剪刀cin >> a >> b >> c;cin >> str;//赢的次数int cnt = 0 ;int len = str.length();for(int j = 0 ; j < len ; j ++){if(str[j] == 'R'){if(b >= 1) {tmp += 'P';b--;cnt ++;}else{//先拿'W'填充，日后再补tmp += 'W';}}else if(str[j] == 'P'){if(c >= 1){tmp += 'S';c --;cnt ++;}else{tmp += 'W';}}else if(str[j] == 'S'){if(a >= 1){tmp += 'R';a --;cnt ++;}else{tmp += 'W';}}}//填tmp的坑for(int j = 0 ; j < len ; j ++){if(tmp[j] == 'W'){if(a >= 1){a --;tmp[j] = 'R';continue;}if(b >= 1){b --;tmp[j] = 'P';continue;}if(c >= 1){c --;tmp[j] = 'S';continue;}}}//若cnt >= Round(n * 1.0 / 2.0)double qwq = n * 1.0 / 2.0;int num = round(qwq);if(cnt >= num){cout << "YES" << endl;cout << tmp << endl;}else{cout << "NO" << endl;}}return 0 ;
}

C. Constanze's Machine

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Constanze is the smartest girl in her village but she has bad eyesight.

One day, she was able to invent an incredible machine! When you pronounce letters, the machine will inscribe them onto a piece of paper. For example, if you pronounce 'c', 'o', 'd', and 'e' in that order, then the machine will inscribe "code" onto the paper. Thanks to this machine, she can finally write messages without using her glasses.

However, her dumb friend Akko decided to play a prank on her. Akko tinkered with the machine so that if you pronounce 'w', it will inscribe "uu" instead of "w", and if you pronounce 'm', it will inscribe "nn" instead of "m"! Since Constanze had bad eyesight, she was not able to realize what Akko did.

The rest of the letters behave the same as before: if you pronounce any letter besides 'w' and 'm', the machine will just inscribe it onto a piece of paper.

The next day, I received a letter in my mailbox. I can't understand it so I think it's either just some gibberish from Akko, or Constanze made it using her machine. But since I know what Akko did, I can just list down all possible strings that Constanze's machine would have turned into the message I got and see if anything makes sense.

But I need to know how much paper I will need, and that's why I'm asking you for help. Tell me the number of strings that Constanze's machine would've turned into the message I got.

But since this number can be quite large, tell me instead its remainder when divided by 109+7109+7.

If there are no strings that Constanze's machine would've turned into the message I got, then print 00.

Input

Input consists of a single line containing a string 𝑠s (1≤|𝑠|≤1051≤|s|≤105) — the received message. 𝑠s contains only lowercase Latin letters.

Output

Print a single integer — the number of strings that Constanze's machine would've turned into the message 𝑠s, modulo 109+7109+7.

Examples

input

Copy

ouuokarinn

output

Copy

4

input

Copy

banana

output

Copy

1

input

Copy

nnn

output

Copy

3

input

Copy

amanda

output

Copy

0

Note

For the first example, the candidate strings are the following: "ouuokarinn", "ouuokarim", "owokarim", and "owokarinn".

For the second example, there is only one: "banana".

For the third example, the candidate strings are the following: "nm", "mn" and "nnn".

For the last example, there are no candidate strings that the machine can turn into "amanda", since the machine won't inscribe 'm'.

#include "iostream"
#include "string.h"
#include "math.h"
#include "stdio.h"
using namespace std;//本题在O(n)内找出连续的u和n块的块数和每块连续的个数，套斐波那契表/同余定理可解
const long long MOD = 1e9+7;int main()
{long long arr[100005];//先打一个斐波那契的表arr[1] = 1;arr[2] = 2;for(int i = 3 ; i <= 100002; i++){arr[i] = (arr[i-1] + arr[i-2]) % MOD;}//len <= 1e5string str;cin >> str;int len = str.length();//包含m或者w直接0if(str[0] == 'w' || str[0] == 'm'){cout << "0" ;return 0;}//记录有几个一样的int cnt = 1;int cntu = 1;long long sum = 1 ;int f = 0 ;int f2 = 0;for(int i = 1 ; i < len ; i ++){//包含m或者w直接0if(str[i] == 'w' || str[i] == 'm'){cout << "0" ;return 0;}//分别找出连续的u有几个，乘上//f=1时进入发现状态if(str[i] == 'u' && str[i-1] == 'u'){cnt ++;f = 1;}if((str[i] != str[i-1] && f == 1) || i == len - 1){sum = (sum * arr[cnt]) % MOD;cnt = 1;//退出发现状态f = 0;}//分别找出连续的n有几个，乘上if(str[i] == 'n' && str[i-1] == 'n'){cntu ++;f2 = 1;}if((str[i] != str[i-1] && f2 == 1) || i == len - 1){sum = (sum * arr[cntu]) % MOD;cntu = 1;f2 = 0;}}cout << sum%MOD;return 0;
}

D. Shichikuji and Power Grid

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Shichikuji is the new resident deity of the South Black Snail Temple. Her first job is as follows:

There are 𝑛n new cities located in Prefecture X. Cities are numbered from 11 to 𝑛n. City 𝑖i is located 𝑥𝑖xi km North of the shrine and 𝑦𝑖yi km East of the shrine. It is possible that (𝑥𝑖,𝑦𝑖)=(𝑥𝑗,𝑦𝑗)(xi,yi)=(xj,yj) even when 𝑖≠𝑗i≠j.

Shichikuji must provide electricity to each city either by building a power station in that city, or by making a connection between that city and another one that already has electricity. So the City has electricity if it has a power station in it or it is connected to a City which has electricity by a direct connection or via a chain of connections.

• Building a power station in City 𝑖i will cost 𝑐𝑖ci yen;
• Making a connection between City 𝑖i and City 𝑗j will cost 𝑘𝑖+𝑘𝑗ki+kj yen per km of wire used for the connection. However, wires can only go the cardinal directions (North, South, East, West). Wires can cross each other. Each wire must have both of its endpoints in some cities. If City 𝑖i and City 𝑗j are connected by a wire, the wire will go through any shortest path from City 𝑖i to City 𝑗j. Thus, the length of the wire if City 𝑖i and City 𝑗j are connected is |𝑥𝑖−𝑥𝑗|+|𝑦𝑖−𝑦𝑗||xi−xj|+|yi−yj| km.

Shichikuji wants to do this job spending as little money as possible, since according to her, there isn't really anything else in the world other than money. However, she died when she was only in fifth grade so she is not smart enough for this. And thus, the new resident deity asks for your help.

And so, you have to provide Shichikuji with the following information: minimum amount of yen needed to provide electricity to all cities, the cities in which power stations will be built, and the connections to be made.

If there are multiple ways to choose the cities and the connections to obtain the construction of minimum price, then print any of them.

Input

First line of input contains a single integer 𝑛n (1≤𝑛≤20001≤n≤2000) — the number of cities.

Then, 𝑛n lines follow. The 𝑖i-th line contains two space-separated integers 𝑥𝑖xi (1≤𝑥𝑖≤1061≤xi≤106) and 𝑦𝑖yi (1≤𝑦𝑖≤1061≤yi≤106) — the coordinates of the 𝑖i-th city.

The next line contains 𝑛n space-separated integers 𝑐1,𝑐2,…,𝑐𝑛c1,c2,…,cn (1≤𝑐𝑖≤1091≤ci≤109) — the cost of building a power station in the 𝑖i-th city.

The last line contains 𝑛n space-separated integers 𝑘1,𝑘2,…,𝑘𝑛k1,k2,…,kn (1≤𝑘𝑖≤1091≤ki≤109).

Output

In the first line print a single integer, denoting the minimum amount of yen needed.

Then, print an integer 𝑣v — the number of power stations to be built.

Next, print 𝑣v space-separated integers, denoting the indices of cities in which a power station will be built. Each number should be from 11 to 𝑛n and all numbers should be pairwise distinct. You can print the numbers in arbitrary order.

After that, print an integer 𝑒e — the number of connections to be made.

Finally, print 𝑒e pairs of integers 𝑎a and 𝑏b (1≤𝑎,𝑏≤𝑛1≤a,b≤n, 𝑎≠𝑏a≠b), denoting that a connection between City 𝑎a and City 𝑏b will be made. Each unordered pair of cities should be included at most once (for each (𝑎,𝑏)(a,b) there should be no more (𝑎,𝑏)(a,b) or (𝑏,𝑎)(b,a) pairs). You can print the pairs in arbitrary order.

If there are multiple ways to choose the cities and the connections to obtain the construction of minimum price, then print any of them.

Examples

input

Copy

3
2 3
1 1
3 2
3 2 3
3 2 3

output

Copy

8
3
1 2 3 
0

input

Copy

3
2 1
1 2
3 3
23 2 23
3 2 3

output

Copy

27
1
2 
2
1 2
2 3

Note

For the answers given in the samples, refer to the following diagrams (cities with power stations are colored green, other cities are colored blue, and wires are colored red):

For the first example, the cost of building power stations in all cities is 3+2+3=83+2+3=8. It can be shown that no configuration costs less than 8 yen.

For the second example, the cost of building a power station in City 2 is 2. The cost of connecting City 1 and City 2 is 2⋅(3+2)=102⋅(3+2)=10. The cost of connecting City 2 and City 3 is 3⋅(2+3)=153⋅(2+3)=15. Thus the total cost is 2+10+15=272+10+15=27. It can be shown that no configuration costs less than 27 yen.

#include "iostream"
#include "string.h"
#include "math.h"
#include "stdio.h"
#include "vector"
using namespace std;
#define INF 0x3f3f3f3fint map[2005][2005],dis[2005],book[2005];
//本题思路比较清奇，虚构一个0节点，0节点到各个城市程c[i]即为建造电厂的花费
//再将每两个城市之间连通的花费求出来，作大图的最小生成树即可
//挖坑）此次仅求出最小花费，有空再补 逃掉（int main()
{int n ;scanf("%d" , &n);//输入n个城市的坐标int x[2005] , y[2005];for(int i = 1; i <= n ; i ++)scanf("%d %d" , &x[i] , &y[i]);//初始化图for(int i = 0 ; i <= n ; i ++)for(int j = 0 ; j <= n ; j ++)if(i == j)map[i][j] = 0 ;elsemap[i][j] = INF;//建立虚拟0点，0到城市1-n的边分别为c[1]-c[n]int tmp;map[0][0] = 0;for(int i = 1 ; i <= n ; i ++){scanf("%d" , &tmp);map[0][i] = tmp;map[i][0] = tmp;}//输入n个城市对应的k[i]int k[2005];for(int i = 1 ; i <= n ; i ++)scanf("%d" , &k[i]);//计算每两个城市之间的距离for(int i = 1 ; i <= n ; i ++){for(int j = 1 ; j <= n ; j ++){if(i == j)map[i][j] = 0;else{map[i][j] = map[j][i] =  (abs(x[i] - x[j]) + abs(y[i] - y[j])) * (k[i]+k[j]);}}}//    for(int i = 0 ; i <= n ; i ++)
//    {
//        for(int j = 0 ;  j <= n ; j ++)
//            cout << map[i][j] << " ";
//        cout << endl;
//    }//两个vector记录最小树连线int tmpx, tmpy;vector<int>vx;vector<int>vy;int sum = 0;memset(book , 0 , sizeof(book));memset(dis , INF , sizeof(dis));for(int i = 0; i <= n; i++)dis[i] = map[0][i];book[0] = 1;int min ; int j;for(int k = 0 ; k < n ; k ++){min = INF;for(int i = 0 ; i <= n ; i++){if(book[i] == 0 && dis[i] < min){min = dis[i];j = i;}}book[j] = 1;sum += dis[j];for(int i = 0 ; i <= n ;i++){if(book[i] == 0 && dis[i] > map[j][i]){dis[i] = map[j][i];}}}//输出最小花费printf("%d\n",sum);//输出建发电站的城市个数和城市//未完，留坑}

#include "iostream"
#include "string.h"
#include "math.h"
#include "stdio.h"
#include "vector"
#include "algorithm"
using namespace std;
#define INF 0x3f3f3f3flong long map[2005][2005];
//填坑，这里边爆了一下。。克鲁斯卡尔过了
//2*1e6条边 670ms 这还真能排
//本题思路比较清奇，虚构一个0节点，0节点到各个城市程c[i]即为建造电厂的花费
//再将每两个城市之间连通的花费求出来，作大图的最小生成树即可struct r
{long long x , y , v;
}road[2100005];bool cmp(r a , r b)
{return a.v < b.v;
}
long long f[2005];
//初始化
void init()
{//每个人的祖宗是自己for(long long i = 0 ; i <= 2005 ; i++)f[i] = i ;
}
//查(路径压缩)
long long search1(long long x)
{if(f[x] == x)return x;else{f[x] = search1(f[x]);return f[x];}
}
//并
void marge(long long x, long long y)
{long long fx = search1(x), fy = search1(y);if(fx != fy)f[fx] = fy;
}int main()
{long long n ;scanf("%d" , &n);//输入n个城市的坐标long long x[2005] ;long long y[2005];for(long long i = 1; i <= n ; i ++)cin >> x[i] >> y[i];//初始化图for(long long i = 0 ; i <= n ; i ++)for(long long j = 0 ; j <= n ; j ++)if(i == j)map[i][j] = 0 ;elsemap[i][j] = INF;//建立虚拟0点，0到城市1-n的边分别为c[1]-c[n]long long tmp;map[0][0] = 0;for(long long i = 1 ; i <= n ; i ++){scanf("%d" , &tmp);map[0][i] = tmp;map[i][0] = tmp;}//输入n个城市对应的k[i]long long k[2005];for(long long i = 1 ; i <= n ; i ++)cin >> k[i];//计算每两个城市之间的距离for(long long i = 1 ; i <= n ; i ++){for(long long j = 1 ; j <= n ; j ++){if(i == j)map[i][j] = 0;else{map[i][j] = map[j][i] =  (abs(x[i] - x[j]) + abs(y[i] - y[j])) * (k[i]+k[j]);}}}//把所有的边存入结构体long long edge_cnt = 1;for(long long i = 0 ; i <= n-1 ; i ++){for(long long j = i+1 ; j <= n; j ++){road[edge_cnt].x = i;road[edge_cnt].y = j;road[edge_cnt].v = map[i][j];
//            cout << i << " " << j << " " << map[i][j] << endl;edge_cnt++;}}//存储建电站的城市vector<long long>q;//存储相连的城市vector<long long>w1 , w2;init();sort(road + 1 ,road + 1 + edge_cnt , cmp);//从最小的路开始，不成环则纳入最小生成树long long sum = 0;for(long long i = 1 ; i <= edge_cnt ; i++){if(search1(road[i].x) != search1(road[i].y)){sum += road[i].v;marge(road[i].x , road[i].y);if(road[i].x == 0)q.push_back(road[i].y);else{w1.push_back(road[i].x);w2.push_back(road[i].y);}}}cout << sum << endl;long long len1 = q.size();long long len2 = w1.size();cout << len1 << endl;for(long long i = 0 ; i < len1 -1 ; i ++)cout << q[i] << " ";cout << q[len1-1] << endl;cout << len2 << endl;for(long long i = 0 ; i < len2  ; i ++)cout << w1[i] << " " << w2[i] << endl;return 0;
}