Codeforces Round #568 (Div. 2)

A. Ropewalkers

time limit per test1 second memory limit per test256 megabytes

Polycarp decided to relax on his weekend and visited to the performance of famous ropewalkers: Agafon, Boniface and Konrad.

The rope is straight and infinite in both directions. At the beginning of the performance, Agafon, Boniface and Konrad are located in positions 𝑎a, 𝑏b and 𝑐c respectively. At the end of the performance, the distance between each pair of ropewalkers was at least 𝑑d.

Ropewalkers can walk on the rope. In one second, only one ropewalker can change his position. Every ropewalker can change his position exactly by 11 (i. e. shift by 11 to the left or right direction on the rope). Agafon, Boniface and Konrad can not move at the same time (Only one of them can move at each moment). Ropewalkers can be at the same positions at the same time and can “walk past each other”.

You should find the minimum duration (in seconds) of the performance. In other words, find the minimum number of seconds needed so that the distance between each pair of ropewalkers can be greater or equal to 𝑑d.

Ropewalkers can walk to negative coordinates, due to the rope is infinite to both sides.Input

The only line of the input contains four integers 𝑎a, 𝑏b, 𝑐c, 𝑑d (1≤𝑎,𝑏,𝑐,𝑑≤1091≤a,b,c,d≤109). It is possible that any two (or all three) ropewalkers are in the same position at the beginning of the performance.Output

Output one integer — the minimum duration (in seconds) of the performance.
Examplesinput

5 2 6 3

output

2

input

3 1 5 6

output

8

input

8 3 3 2

output

2

input

2 3 10 4

output

3

Note

In the first example: in the first two seconds Konrad moves for 2 positions to the right (to the position 88), while Agafon and Boniface stay at their positions. Thus, the distance between Agafon and Boniface will be |5−2|=3|5−2|=3, the distance between Boniface and Konrad will be |2−8|=6|2−8|=6 and the distance between Agafon and Konrad will be |5−8|=3|5−8|=3. Therefore, all three pairwise distances will be at least 𝑑=3d=3, so the performance could be finished within 2 seconds.

签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
const int maxn=(int)2e5+100;
int a[4],d;
int main(){
	cin>>a[0]>>a[1]>>a[2]>>d;
	sort(a,a+3);
	int aa=a[1]-d;int cc=a[1]+d;
	int ans=0;
	ans+=max(0,a[0]-aa);
	ans+=max(0,cc-a[2]);
	cout<<ans<<endl;
}


B. Email from Polycarp

time limit per test3 seconds memory limit per test256 megabytes

Methodius received an email from his friend Polycarp. However, Polycarp’s keyboard is broken, so pressing a key on it once may cause the corresponding symbol to appear more than once (if you press a key on a regular keyboard, it prints exactly one symbol).

For example, as a result of typing the word “hello”, the following words could be printed: “hello”, “hhhhello”, “hheeeellllooo”, but the following could not be printed: “hell”, “helo”, “hhllllooo”.

Note, that when you press a key, the corresponding symbol must appear (possibly, more than once). The keyboard is broken in a random manner, it means that pressing the same key you can get the different number of letters in the result.

For each word in the letter, Methodius has guessed what word Polycarp actually wanted to write, but he is not sure about it, so he asks you to help him.

You are given a list of pairs of words. For each pair, determine if the second word could be printed by typing the first one on Polycarp’s keyboard.Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤1051≤n≤105) — the number of pairs to check. Further input contains 𝑛n descriptions of pairs.

The first line of each description contains a single non-empty word 𝑠s consisting of lowercase Latin letters. The second line of the description contains a single non-empty word 𝑡t consisting of lowercase Latin letters. The lengths of both strings are not greater than 106106.

It is guaranteed that the total length of all words 𝑠s in the input is not greater than 106106. Also, it is guaranteed that the total length of all words 𝑡t in the input is not greater than 106106.Output

Output 𝑛n lines. In the 𝑖i-th line for the 𝑖i-th pair of words 𝑠s and 𝑡t print YES if the word 𝑡t could be printed by typing the word 𝑠s. Otherwise, print NO.
Examplesinput

4
hello
hello
hello
helloo
hello
hlllloo
hello
helo

output

YES
YES
NO
NO

input

5
aa
bb
codeforces
codeforce
polycarp
poolycarpp
aaaa
aaaab
abcdefghijklmnopqrstuvwxyz
zabcdefghijklmnopqrstuvwxyz

output

NO
NO
YES
NO
NO

两个指针跑一跑

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
const int maxn=(int)1e6+100;
char s[maxn],t[maxn];
bool work(){
	int la=strlen(s);int lb=strlen(t);
		if(lb<la) return 0;
		int pos=0;
		rep(i,0,la-1){
			if(pos>=lb) return 0;
			if(s[i]==t[pos]){pos++;continue;}
			else{
				if(pos==0) return 0;
				while(t[pos]==t[pos-1]) {
					pos++;
					if(pos>=lb) return 0;
				}
				if(s[i]!=t[pos]) return 0;
				else pos++;
			}
		}
		rep(i,pos,lb-1) if(t[i]!=t[i-1]) return 0; 
		return 1;
}
int main(){
	int T;cin>>T;
	rep(i,1,T){
		scanf("%s%s",s,t);
		puts(work()?"YES":"NO");
	}
}


C2. Exam in BerSU (hard version)

time limit per test2 seconds memory limit per test256 megabytes

The only difference between easy and hard versions is constraints.

If you write a solution in Python, then prefer to send it in PyPy to speed up execution time.

A session has begun at Beland State University. Many students are taking exams.

Polygraph Poligrafovich is going to examine a group of 𝑛n students. Students will take the exam one-by-one in order from 11-th to 𝑛n-th. Rules of the exam are following:

  • The 𝑖i-th student randomly chooses a ticket.
  • if this ticket is too hard to the student, he doesn’t answer and goes home immediately (this process is so fast that it’s considered no time elapses). This student fails the exam.
  • if the student finds the ticket easy, he spends exactly 𝑡𝑖ti minutes to pass the exam. After it, he immediately gets a mark and goes home.

Students take the exam in the fixed order, one-by-one, without any interruption. At any moment of time, Polygraph Poligrafovich takes the answer from one student.

The duration of the whole exam for all students is 𝑀M minutes (max𝑡𝑖≤𝑀maxti≤M), so students at the end of the list have a greater possibility to run out of time to pass the exam.

For each student 𝑖i, you should count the minimum possible number of students who need to fail the exam so the 𝑖i-th student has enough time to pass the exam.

For each student 𝑖i, find the answer independently. That is, if when finding the answer for the student 𝑖1i1 some student 𝑗j should leave, then while finding the answer for 𝑖2i2 (𝑖2>𝑖1i2>i1) the student 𝑗j student does not have to go home.Input

The first line of the input contains two integers 𝑛n and 𝑀M (1≤𝑛≤2⋅1051≤n≤2⋅105, 1≤𝑀≤2⋅1071≤M≤2⋅107) — the number of students and the total duration of the exam in minutes, respectively.

The second line of the input contains 𝑛n integers 𝑡𝑖ti (1≤𝑡𝑖≤1001≤ti≤100) — time in minutes that 𝑖i-th student spends to answer to a ticket.

It’s guaranteed that all values of 𝑡𝑖ti are not greater than 𝑀M.Output

Print 𝑛n numbers: the 𝑖i-th number must be equal to the minimum number of students who have to leave the exam in order to 𝑖i-th student has enough time to pass the exam.
Examplesinput

7 15
1 2 3 4 5 6 7

output

0 0 0 0 0 2 3 

input

5 100
80 40 40 40 60

output

0 1 1 2 3 

Note

The explanation for the example 1.

Please note that the sum of the first five exam times does not exceed 𝑀=15M=15 (the sum is 1+2+3+4+5=151+2+3+4+5=15). Thus, the first five students can pass the exam even if all the students before them also pass the exam. In other words, the first five numbers in the answer are 00.

In order for the 66-th student to pass the exam, it is necessary that at least 22 students must fail it before (for example, the 33-rd and 44-th, then the 66-th will finish its exam in 1+2+5+6=141+2+5+6=14 minutes, which does not exceed 𝑀M).

In order for the 77-th student to pass the exam, it is necessary that at least 33 students must fail it before (for example, the 22-nd, 55-th and 66-th, then the 77-th will finish its exam in 1+3+4+7=151+3+4+7=15 minutes, which does not exceed 𝑀M).

其实挺签到的,对于第i个学生,答案肯定就是i-1-前i-1个学生中时间和小于等于(M-a[i])的学生个数;
贪心的想,前i-1个学生肯定是选最小的几个,考虑到时间只有100,把学生离散到时间上,暴力找一下就可以了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
const int maxn=(int)2e5+100;
int n,m,a[110];
int get_sum(int pos){
	int ans=0,pre=0;
	rep(i,1,100){
		if(a[i]){
			int t=min((pos-pre)/i,a[i]);
			ans+=t; pre+=i*t;
			if(t<a[i]) break;
		}
	}
	return ans; 
}
int main(){
	cin>>n>>m;
	rep(i,1,n){
		int x;scanf("%d",&x);
		printf("%d ",i-1-get_sum(m-x));
		a[x]++;
	}
}


D. Extra Element

time limit per test2 seconds memory limit per test256 megabytes

A sequence 𝑎1,𝑎2,…,𝑎𝑘a1,a2,…,ak is called an arithmetic progression if for each 𝑖i from 11 to 𝑘k elements satisfy the condition 𝑎𝑖=𝑎1+𝑐⋅(𝑖−1)ai=a1+c⋅(i−1)for some fixed 𝑐c.

For example, these five sequences are arithmetic progressions: [5,7,9,11][5,7,9,11], [101][101], [101,100,99][101,100,99], [13,97][13,97] and [5,5,5,5,5][5,5,5,5,5]. And these four sequences aren’t arithmetic progressions: [3,1,2][3,1,2], [1,2,4,8][1,2,4,8], [1,−1,1,−1][1,−1,1,−1] and [1,2,3,3,3][1,2,3,3,3].

You are given a sequence of integers 𝑏1,𝑏2,…,𝑏𝑛b1,b2,…,bn. Find any index 𝑗j (1≤𝑗≤𝑛1≤j≤n), such that if you delete 𝑏𝑗bj from the sequence, you can reorder the remaining 𝑛−1n−1 elements, so that you will get an arithmetic progression. If there is no such index, output the number -1.Input

The first line of the input contains one integer 𝑛n (2≤𝑛≤2⋅1052≤n≤2⋅105) — length of the sequence 𝑏b. The second line contains 𝑛n integers 𝑏1,𝑏2,…,𝑏𝑛b1,b2,…,bn (−109≤𝑏𝑖≤109−109≤bi≤109) — elements of the sequence 𝑏b.Output

Print such index 𝑗j (1≤𝑗≤𝑛1≤j≤n), so that if you delete the 𝑗j-th element from the sequence, you can reorder the remaining elements, so that you will get an arithmetic progression. If there are multiple solutions, you are allowed to print any of them. If there is no such index, print -1.
Examplesinput

5
2 6 8 7 4

output

4

input

8
1 2 3 4 5 6 7 8

output

1

input

4
1 2 4 8

output

-1

Note

Note to the first example. If you delete the 44-th element, you can get the arithmetic progression [2,4,6,8][2,4,6,8].

Note to the second example. The original sequence is already arithmetic progression, so you can delete 11-st or last element and you will get an arithmetical progression again.

窒息操作,首先对于最前面和最后面的两个数单独分析,在考虑中间去掉某个数能不能符合条件,暴力找就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
const int maxn=(int)2e5+100;
int n,c[maxn],a1,a2,a3;
set<int> s;
struct node{
	int x,pos;
	bool operator<(const node &b)const{return x<b.x;}
}a[maxn];
int main(){
	cin>>n;
	rep(i,1,n){
		scanf("%d",&a[i].x);
		a[i].pos=i;
	}
	sort(a+1,a+1+n);
	rep(i,2,n) c[i]=a[i].x-a[i-1].x,s.insert(c[i]);
	if(s.size()>3) return puts("-1"),0;
	else if(s.size()==1) return printf("%d\n",a[1].pos),0;
	int flag=1,pre=a[3].x-a[2].x;
	rep(i,4,n) if(a[i].x-a[i-1].x!=pre) {flag=0;break;}
	if(flag) return printf("%d\n",a[1].pos),0;
	flag=1,pre=a[2].x-a[1].x;
	rep(i,3,n-1) if(a[i].x-a[i-1].x!=pre) {flag=0;break;}
	if(flag) return printf("%d\n",a[n].pos),0;
	flag=0;
	int m=*(--s.end());
	rep(i,2,n-1) if(c[i]<m){
		if(c[i]+c[i+1]!=m) return puts("-1"),0;
		else{
			if(!flag) flag=i;
			else return puts("-1"),0;
			i++;
		}
	}
	if(flag) return printf("%d\n",a[flag].pos),0;
	return puts("-1"),0;
}


E. Polycarp and Snakes

time limit per test4 seconds memory limit per test256 megabytes

After a hard-working week Polycarp prefers to have fun. Polycarp’s favorite entertainment is drawing snakes. He takes a rectangular checkered sheet of paper of size n×mn×m (where nn is the number of rows, mm is the number of columns) and starts to draw snakes in cells.

Polycarp draws snakes with lowercase Latin letters. He always draws the first snake with the symbol ‘a’, the second snake with the symbol ‘b’, the third snake with the symbol ‘c’ and so on. All snakes have their own unique symbol. There are only 2626 letters in the Latin alphabet, Polycarp is very tired and he doesn’t want to invent new symbols, so the total number of drawn snakes doesn’t exceed 2626.

Since by the end of the week Polycarp is very tired, he draws snakes as straight lines without bends. So each snake is positioned either vertically or horizontally. Width of any snake equals 11, i.e. each snake has size either 1×l1×l or l×1l×1, where ll is snake’s length. Note that snakes can’t bend.

When Polycarp draws a new snake, he can use already occupied cells for drawing the snake. In this situation, he draws the snake “over the top” and overwrites the previous value in the cell.

Recently when Polycarp was at work he found a checkered sheet of paper with Latin letters. He wants to know if it is possible to get this sheet of paper from an empty sheet by drawing some snakes according to the rules described above. If it is possible, he is interested in a way to draw snakes.Input

The first line of the input contains one integer tt (1≤t≤1051≤t≤105) — the number of test cases to solve. Then tt test cases follow.

The first line of the test case description contains two integers nn, mm (1≤n,m≤20001≤n,m≤2000) — length and width of the checkered sheet of paper respectively.

Next nn lines of test case description contain mm symbols, which are responsible for the content of the corresponding cell on the sheet. It can be either lowercase Latin letter or symbol dot (‘.’), which stands for an empty cell.

It is guaranteed that the total area of all sheets in one test doesn’t exceed 4⋅1064⋅106.Output

Print the answer for each test case in the input.

In the first line of the output for a test case print YES if it is possible to draw snakes, so that you can get a sheet of paper from the input. If it is impossible, print NO.

If the answer to this question is positive, then print the way to draw snakes in the following format. In the next line print one integer kk (0≤k≤260≤k≤26) — number of snakes. Then print kk lines, in each line print four integers r1,ir1,i, c1,ic1,i, r2,ir2,i and c2,ic2,i — coordinates of extreme cells for the ii-th snake (1≤r1,i,r2,i≤n1≤r1,i,r2,i≤n, 1≤c1,i,c2,i≤m1≤c1,i,c2,i≤m). Snakes should be printed in order of their drawing. If there are multiple solutions, you are allowed to print any of them.

Note that Polycarp starts drawing of snakes with an empty sheet of paper.
Examplesinput

1
5 6
...a..
..bbb.
...a..
.cccc.
...a..

output

YES
3
1 4 5 4
2 3 2 5
4 2 4 5

input

3
3 3
...
...
...
4 4
..c.
adda
bbcb
....
3 5
..b..
aaaaa
..b..

output

YES
0
YES
4
2 1 2 4
3 1 3 4
1 3 3 3
2 2 2 3
NO

input

2
3 3
...
.a.
...
2 2
bb
cc

output

YES
1
2 2 2 2
YES
3
1 1 1 2
1 1 1 2
2 1 2 2

怎么说呢,挺好想的一题,最暴力的方法就好了;

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
const int maxn=(int)2e3+100;
const int INF=0x7fffffff;
int n,m,maxx,flag;
char mp[maxn][maxn];
struct node{int l1,r1,l2,r2;};
vector<node> ans;
void init(){ans.clear(); maxx=0;flag=1;}
void check(int x){
	int u=INF,d=0,l=INF,r=0;
	char c='a'+x-1;
	rep(i,1,n) rep(j,1,m) if(mp[i][j]==c){
		l=min(l,j); r=max(r,j);
		u=min(u,i); d=max(d,i);
	}
	if(l==INF){
		bool has=0;
		rep(i,1,n) rep(j,1,m) if(!has&&mp[i][j]=='?'){
			ans.pb({i,j,i,j}); has=1;
			return;
		}
		if(!has) {flag=0;return;}
	}
	if(l==r||u==d){
		ans.pb({u,l,d,r});
		rep(i,u,d) rep(j,l,r){
			if(mp[i][j]!='?'){
				if(mp[i][j]!=c) flag=0;
				mp[i][j]='?';
			}
		}
	} else flag=0;
}
int main(){
	int T;cin>>T;
	while(T--){
		scanf("%d%d\n",&n,&m);
		init();
		rep(i,1,n){
			scanf("%s",mp[i]+1);
			rep(j,1,m) if(mp[i][j]!='.') maxx=max(maxx,mp[i][j]-'a'+1);
		}
		dep(i,maxx,1) if(flag) check(i);
		if(flag){
			rep(i,1,n) rep(j,1,m) if(mp[i][j]!='.'&&mp[i][j]!='?') flag=0;
		}
		if(flag){
			puts("YES"); int sz=(int)ans.size();
			printf("%d\n",sz);
			dep(i,sz-1,0) printf("%d %d %d %d\n",ans[i].l1,ans[i].r1,ans[i].l2,ans[i].r2);
		} else puts("NO");
	}
}


F. Two Pizzas

time limit per test4 seconds memory limit per test256 megabytes

A company of 𝑛n friends wants to order exactly two pizzas. It is known that in total there are 99 pizza ingredients in nature, which are denoted by integers from 11 to 99.

Each of the 𝑛n friends has one or more favorite ingredients: the 𝑖i-th of friends has the number of favorite ingredients equal to 𝑓𝑖fi (1≤𝑓𝑖≤91≤fi≤9) and your favorite ingredients form the sequence 𝑏𝑖1,𝑏𝑖2,…,𝑏𝑖𝑓𝑖bi1,bi2,…,bifi (1≤𝑏𝑖𝑡≤91≤bit≤9).

The website of CodePizza restaurant has exactly 𝑚m (𝑚≥2m≥2) pizzas. Each pizza is characterized by a set of 𝑟𝑗rj ingredients 𝑎𝑗1,𝑎𝑗2,…,𝑎𝑗𝑟𝑗aj1,aj2,…,ajrj(1≤𝑟𝑗≤91≤rj≤9, 1≤𝑎𝑗𝑡≤91≤ajt≤9) , which are included in it, and its price is 𝑐𝑗cj.

Help your friends choose exactly two pizzas in such a way as to please the maximum number of people in the company. It is known that a person is pleased with the choice if each of his/her favorite ingredients is in at least one ordered pizza. If there are several ways to choose two pizzas so as to please the maximum number of friends, then choose the one that minimizes the total price of two pizzas.Input

The first line of the input contains two integers 𝑛n and 𝑚m (1≤𝑛≤105,2≤𝑚≤1051≤n≤105,2≤m≤105) — the number of friends in the company and the number of pizzas, respectively.

Next, the 𝑛n lines contain descriptions of favorite ingredients of the friends: the 𝑖i-th of them contains the number of favorite ingredients 𝑓𝑖fi (1≤𝑓𝑖≤91≤fi≤9) and a sequence of distinct integers 𝑏𝑖1,𝑏𝑖2,…,𝑏𝑖𝑓𝑖bi1,bi2,…,bifi (1≤𝑏𝑖𝑡≤91≤bit≤9).

Next, the 𝑚m lines contain pizza descriptions: the 𝑗j-th of them contains the integer price of the pizza 𝑐𝑗cj (1≤𝑐𝑗≤1091≤cj≤109), the number of ingredients 𝑟𝑗rj (1≤𝑟𝑗≤91≤rj≤9) and the ingredients themselves as a sequence of distinct integers 𝑎𝑗1,𝑎𝑗2,…,𝑎𝑗𝑟𝑗aj1,aj2,…,ajrj (1≤𝑎𝑗𝑡≤91≤ajt≤9).Output

Output two integers 𝑗1j1 and 𝑗2j2 (1≤𝑗1,𝑗2≤𝑚1≤j1,j2≤m, 𝑗1≠𝑗2j1≠j2) denoting the indices of two pizzas in the required set. If there are several solutions, output any of them. Pizza indices can be printed in any order.
Examplesinput

3 4
2 6 7
4 2 3 9 5
3 2 3 9
100 1 7
400 3 3 2 5
100 2 9 2
500 3 2 9 5

output

2 3

input

4 3
1 1
1 2
1 3
1 4
10 4 1 2 3 4
20 4 1 2 3 4
30 4 1 2 3 4

output

1 2

input

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

output

2 4

状压暴力,甚至不用dp,挺好做的,记录每个mark的人数和每个mark的披萨的最小价值和次小价值,再暴力枚举两个披萨,更新一下答案,跑得飞快

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=(1<<9)+100;
int n,m;
int cnt[maxn];
vector<pii> pizz[maxn];
int main(){
	cin>>n>>m;
	rep(i,0,n-1){
		int num,mk=0;scanf("%d",&num);
		while(num--){
			int x;scanf("%d",&x);x--;
			mk|=(1<<x);
		}
		cnt[mk]++;
	}
	rep(i,0,m-1){
		int c,num,mk=0;scanf("%d%d",&c,&num);
		while(num--){
			int x;scanf("%d",&x);x--;
			mk|=(1<<x);
		}
		pizz[mk].pb({c,i}); sort(pizz[mk].begin(),pizz[mk].end());
		while(pizz[mk].size()>2) pizz[mk].pop_back();
	}
	int num=0,cost=0x7fffffff;
	pii res={-1,-1};
	rep(mk1,0,(1<<9)-1) rep(mk2,0,(1<<9)-1){
		int curcost=0,pos1,pos2;
		if(mk1==mk2){
			if(pizz[mk1].size()<2) continue;
			curcost=pizz[mk1][0].F+pizz[mk1][1].F;
			pos1=pizz[mk1][0].S;pos2=pizz[mk1][1].S;
		}
		else{
			if(pizz[mk1].size()==0||pizz[mk2].size()==0) continue;
			curcost=pizz[mk1][0].F+pizz[mk2][0].F;
			pos1=pizz[mk1][0].S;pos2=pizz[mk2][0].S;
		}
		int curnum=0,curmk=mk1|mk2;
		rep(p,0,(1<<9)-1) if((curmk&p)==p){
			curnum+=cnt[p];
		}
		if(curnum>num||(curnum==num&&curcost<cost)){
			num=curnum;
			cost=curcost;
			res={pos1+1,pos2+1};
		}
	}
	printf("%d %d\n",res.F,res.S);
}


G1. Playlist for Polycarp (easy version)

time limit per test5 seconds memory limit per test256 megabytes

The only difference between easy and hard versions is constraints.

Polycarp loves to listen to music, so he never leaves the player, even on the way home from the university. Polycarp overcomes the distance from the university to the house in exactly 𝑇T minutes.

In the player, Polycarp stores 𝑛n songs, each of which is characterized by two parameters: 𝑡𝑖ti and 𝑔𝑖gi, where 𝑡𝑖ti is the length of the song in minutes (1≤𝑡𝑖≤151≤ti≤15), 𝑔𝑖gi is its genre (1≤𝑔𝑖≤31≤gi≤3).

Polycarp wants to create such a playlist so that he can listen to music all the time on the way from the university to his home, and at the time of his arrival home, the playlist is over. Polycarp never interrupts songs and always listens to them from beginning to end. Thus, if he started listening to the 𝑖i-th song, he would spend exactly 𝑡𝑖ti minutes on its listening. Polycarp also does not like when two songs of the same genre play in a row (i.e. successively/adjacently) or when the songs in his playlist are repeated.

Help Polycarpus count the number of different sequences of songs (their order matters), the total duration is exactly 𝑇T, such that there are no two consecutive songs of the same genre in them and all the songs in the playlist are different.Input

The first line of the input contains two integers 𝑛n and 𝑇T (1≤𝑛≤15,1≤𝑇≤2251≤n≤15,1≤T≤225) — the number of songs in the player and the required total duration, respectively.

Next, the 𝑛n lines contain descriptions of songs: the 𝑖i-th line contains two integers 𝑡𝑖ti and 𝑔𝑖gi (1≤𝑡𝑖≤15,1≤𝑔𝑖≤31≤ti≤15,1≤gi≤3) — the duration of the 𝑖i-th song and its genre, respectively.Output

Output one integer — the number of different sequences of songs, the total length of exactly 𝑇T, such that there are no two consecutive songs of the same genre in them and all the songs in the playlist are different. Since the answer may be huge, output it modulo 109+7109+7(that is, the remainder when dividing the quantity by 109+7109+7).
Examplesinput

3 3
1 1
1 2
1 3

output

6

input

3 3
1 1
1 1
1 3

output

2

input

4 10
5 3
2 1
3 2
5 1

output

10

Note

In the first example, Polycarp can make any of the 66 possible playlist by rearranging the available songs: [1,2,3][1,2,3], [1,3,2][1,3,2], [2,1,3][2,1,3], [2,3,1][2,3,1], [3,1,2][3,1,2] and [3,2,1][3,2,1] (indices of the songs are given).

In the second example, the first and second songs cannot go in succession (since they have the same genre). Thus, Polycarp can create a playlist in one of 22 possible ways: [1,3,2][1,3,2] and [2,3,1][2,3,1] (indices of the songs are given).

In the third example, Polycarp can make the following playlists: [1,2,3][1,2,3], [1,3,2][1,3,2], [2,1,3][2,1,3], [2,3,1][2,3,1], [3,1,2][3,1,2], [3,2,1][3,2,1], [1,4][1,4], [4,1][4,1], [2,3,4][2,3,4] and [4,3,2][4,3,2] (indices of the songs are given).

n只有15,状压DP裸题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,m;
ll ans,dp[(1<<15)+100][4];
struct node{
	int t,g;
}a[20];
int main(){
	cin>>n>>m;
	rep(i,0,n-1) scanf("%d%d",&a[i].t,&a[i].g);
	dp[0][0]=1;
	rep(mark,0,(1<<n)-1) rep(last,0,3){
		rep(i,0,n-1) if(a[i].g!=last&&((mark&(1<<i))==0))
			dp[mark^(1<<i)][a[i].g]=(dp[mark^(1<<i)][a[i].g]+dp[mark][last])%mod;
		int sum=0;
		rep(i,0,n-1) if(mark&(1<<i)) sum+=a[i].t;
		if(sum==m) ans=(ans+dp[mark][last])%mod;
	}
	printf("%lld\n",ans);
}

发表评论,支持MarkDown语法