A：折半搜索+二分????跟上星期一樣的知識點
B：拓?fù)渑判?br> C：里面知識點都經(jīng)?？疾⑶音酆显谝黄穑浅：玫囊坏李}。并查集+樹DP考慮邊的貢獻(xiàn)
D：掃描線??上星期知識點???????????????出這道題是因為可以用bitset暴力卡，可以學(xué)習(xí)bitset，但是記得補正解
E：思維題?拿來簽到
F：弗洛伊德
G：高斯消元比較模板的題，但是很惡心，卡精度，卡eps不能調(diào)太大，而且卡long?double
?

?

A題

CodeForces - 912E?

Opposite to Grisha's nice behavior, Oleg, though he has an entire year at his disposal, didn't manage to learn how to solve number theory problems in the past year. That's why instead of Ded Moroz he was visited by his teammate Andrew, who solemnly presented him with a set of?n?distinct prime?numbers alongside with a simple task: Oleg is to find the?k-th smallest integer, such that?all?its prime divisors are in this set.

Input

The first line contains a single integer?n?(1?≤?n?≤?16).

The next line lists?n?distinct prime numbers?p1,?p2,?...,?pn?(2?≤?pi?≤?100) in ascending order.

The last line gives a single integer?k?(1?≤?k). It is guaranteed that the?k-th smallest integer such that all its prime divisors are in this set does not exceed?1018.

Output

Print a single line featuring the?k-th smallest integer. It's guaranteed that the answer doesn't exceed?1018.

Examples

Input

3
2 3 5
7

Output

8

Input

5
3 7 11 13 31
17

Output

93

Note

The list of numbers with all prime divisors inside?{2,?3,?5}?begins as follows:

(1,?2,?3,?4,?5,?6,?8,?...)

The seventh number in this list (1-indexed) is eight.

?

知識點和上星期一樣，折半搜索＋二分查找。

主要是一開始讀不懂題，根本不知道是什么意思，試了好久才知道是包括1且因數(shù)要包括集合內(nèi)的元素。

先用DFS枚舉好所有狀態(tài)的結(jié)果，然后兩邊雙指針同時進(jìn)行，二分枚舉目前的mid是排在第幾，直到找到ans為止。

?

代碼：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <string.h>
#include <math.h>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <vector>

using namespace std;

const long long oo=1e18;
int k;
int n; 
long long p[20];
vector<long long> a[2];
void ready()
{
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    cin>>k;
}

void dfs(int temp,int u,long long now)
{
	a[temp].push_back(now);
	for(int i=u;i<=n;i+=2)
	  if(oo/p[i]>=now)
	    dfs(temp,i,now*p[i]);
}

bool check(long long mid)
{
	long long ki=0;
	for(int i=(int)a[0].size()-1,j=0;i>=0;i--)
	{
		while(j<(int)a[1].size() && a[1][j]<=mid/a[0][i])
	      j++;
		ki+=j;
	}
	return ki>=k;
}

void work()
{
    dfs(0,1,1);
	dfs(1,2,1);
	sort(a[0].begin(),a[0].end());
	sort(a[1].begin(),a[1].end());
	long long l=1,r=oo,mid=(l+r)/2;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(check(mid))
		  r=mid-1;
		else
		  l=mid+1;
	}
	cout<<l;
	return ;
}

int main()
{
    ready();
    work();
    return 0;
}

?

B題

CodeForces - 770C

Now you can take online courses in the Berland State University! Polycarp needs to pass?k?main?online courses of his specialty to get a diploma. In total?n?courses are availiable for the passage.

The situation is complicated by the dependence of online courses, for each course there is a list of those that must be passed before starting this online course (the list can be empty, it means that there is no limitation).

Help Polycarp to pass the least number of courses in total to get the specialty (it means to pass all?main?and necessary courses). Write a program which prints the order of courses.

Polycarp passes courses consistently, he starts the next course when he finishes the previous one. Each course can't be passed more than once.

Input

The first line contains?n?and?k?(1?≤?k?≤?n?≤?105) — the number of online-courses and the number of main courses of Polycarp's specialty.

The second line contains?k?distinct integers from?1?to?n?— numbers of main online-courses of Polycarp's specialty.

Then?n?lines follow, each of them describes the next course: the?i-th of them corresponds to the course?i. Each line starts from the integer?ti?(0?≤?ti?≤?n?-?1) — the number of courses on which the?i-th depends. Then there follows the sequence of?ti?distinct integers from?1?to?n?— numbers of courses in random order, on which the?i-th depends. It is guaranteed that no course can depend on itself.

It is guaranteed that the sum of all values?ti?doesn't exceed?105.

Output

Print?-1, if there is no the way to get a specialty.

Otherwise, in the first line print the integer?m?— the minimum number of online-courses which it is necessary to pass to get a specialty. In the second line print?m?distinct integers — numbers of courses which it is necessary to pass in the chronological order of their passage. If there are several answers it is allowed to print any of them.

Examples

Input

6 2
5 3
0
0
0
2 2 1
1 4
1 5

Output

5
1 2 3 4 5 

Input

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

Output

6
1 2 9 4 5 3 

Input

3 3
1 2 3
1 2
1 3
1 1

Output

-1

Note

In the first test firstly you can take courses number?1?and?2, after that you can take the course number?4, then you can take the course number?5, which is the main. After that you have to take only the course number?3, which is the last not passed main course.

?

雖說是拓?fù)渑判?，但我感覺更像是思維DFS，主要在記錄狀態(tài)的時候注意一下。好吧就是記錄狀態(tài)這里要做好就行了，就是個普普通通的DFS。

保存狀態(tài)和最后存進(jìn)ans在DFS最后儲存，這樣能保證先儲存的就是最里面的點。這個地方卡了我好久，比賽的時候就是卡在這個地方了。

注意要反方向構(gòu)圖！

?

代碼：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <string.h>
#include <math.h>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <vector>
 
using namespace std;
 
int n,k;
int p[100005],nex[100005],to[100005],pi;
int ki[100005];
int ans[100005],ansi;
bool q[100005];
int f[100005];
int cnt[100005];
bool ANS;
struct B{
    int id;
    int in_;
}t[100005];
 
 
void read_in(int u,int v)
{
    pi++;nex[pi]=p[u];p[u]=pi;to[pi]=v;
}
 
bool cmp(B i,B j)
{
    return i.in_<j.in_;
}
 
void ready()
{
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=k;i++)
      cin>>ki[i];
    for(int i=1;i<=n;i++)
    {
        int ti;
        cin>>ti;
        while(ti--)
        {
            int vi;
            cin>>vi;
            read_in(i,vi);
        }
    }

}
 
void dfs(int u)
{
    f[u]=-1;
    for(int i=p[u],v=to[i];i;i=nex[i],v=to[i])
    {
    	if(f[v]==-1)
    	{
    		ANS=true;
    		return ;
		}
		
		if(!f[v])
		  dfs(v);
	}
	f[u]=1;
	ans[++ansi]=u;
}
 
void work()
{
    for(int i=1;i<=k;i++)
    {
        if(!f[ki[i]])
        dfs(ki[i]);        
		if(ANS)
        {
            cout<<-1;
            return ;
        }
    }
    cout<<ansi<<'\n';
    for(int i=1;i<=ansi;i++)
        cout<<ans[i]<<' ';
    return ;
}
 
int main()
{
    ready();
    work();
    return 0;
}
/*
5 3
2 1  3
0
1 1
1 2
0
0
*/

?

E題

CodeForces - 1186C?

Vus the Cossack has two binary strings, that is, strings that consist only of "0" and "1". We call these strings?aa?and?bb. It is known that?|b|≤|a||b|≤|a|, that is, the length of?bb?is at most the length of?aa.

The Cossack considers every substring of length?|b||b|?in string?aa. Let's call this substring?cc. He matches the corresponding characters in?bb?and?cc, after which he counts the number of positions where the two strings are different. We call this function?f(b,c)f(b,c).

For example, let?b=00110b=00110, and?c=11000c=11000. In these strings, the first, second, third and fourth positions are different.

Vus the Cossack counts the number of such substrings?cc?such that?f(b,c)f(b,c)?is?even.

For example, let?a=01100010a=01100010?and?b=00110b=00110.?aa?has four substrings of the length?|b||b|:?0110001100,?1100011000,?1000110001,?0001000010.

• f(00110,01100)=2f(00110,01100)=2;
• f(00110,11000)=4f(00110,11000)=4;
• f(00110,10001)=4f(00110,10001)=4;
• f(00110,00010)=1f(00110,00010)=1.

Since in three substrings,?f(b,c)f(b,c)?is even, the answer is?33.

Vus can not find the answer for big strings. That is why he is asking you to help him.

Input

The first line contains a binary string?aa?(1≤|a|≤1061≤|a|≤106)?— the first string.

The second line contains a binary string?bb?(1≤|b|≤|a|1≤|b|≤|a|)?— the second string.

Output

Print one number?— the answer.

Examples

Input

01100010
00110

Output

3

Input

1010111110
0110

Output

4

Note

The first example is explained in the legend.

In the second example, there are five substrings that satisfy us:?10101010,?01010101,?11111111,?11111111.

?

思維題。吃在了看不懂題的虧。不知道even是偶數(shù)的意思，也沒去猜f（b，c）到底是什么意思。

題意也就是兩串01組成的字符串a(chǎn)，b。|a| >= |b| ，在a中取 |b| 長度，和b異或后如果1的個數(shù)為偶數(shù)則這是一個目標(biāo)子串。問a中有多少個長度為|b|且滿足條件的子串。

思維題，找規(guī)律。7爺比完之后立刻和我說這肯定cf的題目。

如果兩個子串中，1的個數(shù)同為偶數(shù)或者同為奇數(shù)，則不管1在不在同一個位置，異或之后剩下的1肯定都是偶數(shù)。所以用前綴和維護(hù)就好。

?

代碼

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <string.h>
#include <math.h>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <vector>

using namespace std;

string a,b;
int la,lb,ai[1000006],bi[1000006],ans;
void ready()
{
    ios::sync_with_stdio(false),cin.tie(0);
	cin>>a>>b;
	la=a.size();lb=b.size();
	for(int i=0;i<la;i++)
	  if(i==0)
	    ai[i]=a[i]-'0';
	  else
	    ai[i]=ai[i-1]+a[i]-'0';
	for(int i=0;i<lb;i++)
	  if(i==0)
	    bi[i]=b[i]-'0';
	  else
	    bi[i]=bi[i-1]+b[i]-'0';
}

int check_(int x,int y)
{
	if(x%2==y%2)
	  return 1;
	else
	  return 0;
}

int main()
{
    ready();
    for(int i=lb-1;i<la;i++)
    {
    	if(i==lb-1)
    	  ans+=check_(bi[lb-1],ai[i]);
    	else
    	  ans+=check_(bi[lb-1],ai[i]-ai[i-lb]);
	}
	cout<<ans;
    return 0;
}

?

?

F題

CodeForces - 33B?

Boy Valera likes strings. And even more he likes them, when they are identical. That's why in his spare time Valera plays the following game. He takes any two strings, consisting of lower case Latin letters, and tries to make them identical. According to the game rules, with each move Valera can change?one?arbitrary character?Ai?in one of the strings into arbitrary character?Bi, but he has to pay for every move a particular sum of money, equal to?Wi. He is allowed to make as many moves as he needs. Since Valera is a very economical boy and never wastes his money, he asked you, an experienced programmer, to help him answer the question: what minimum amount of money should Valera have to get identical strings.

Input

The first input line contains two initial non-empty strings?s?and?t, consisting of lower case Latin letters. The length of each string doesn't exceed?105. The following line contains integer?n?(0?≤?n?≤?500)?— amount of possible changings. Then follow?n?lines, each containing characters?Ai?and?Bi?(lower case Latin letters) and integer?Wi?(0?≤?Wi?≤?100), saying that it's allowed to change character?Ai?into character?Bi?in any of the strings and spend sum of money?Wi.

Output

If the answer exists, output the answer to the problem, and the resulting string. Otherwise output?-1?in the only line. If the answer is not unique, output any.

Examples

Input

uayd
uxxd
3
a x 8
x y 13
d c 3

Output

21
uxyd

Input

a
b
3
a b 2
a b 3
b a 5

Output

2
b

Input

abc
ab
6
a b 4
a b 7
b a 8
c b 11
c a 3
a c 0

Output

-1

?

題意：有n種替換字母的方式，將兩個只包括小寫字母的字符串替換成相同字符串所需要的最少錢是多少，結(jié)果字符串是什么。

一開始以為直接逐位比較變成對方就OK了，然后發(fā)現(xiàn)可能可以同時變?yōu)榈谌齻€字母，然后加了個跳板一起變成第三個。然后想想，可以構(gòu)造一個圖，用Floyd來做，兩個字母之間有轉(zhuǎn)換也就是有路，費用就是權(quán)值，F(xiàn)loyd就能找到兩個之間轉(zhuǎn)換到哪個字母比較好，花錢比較少。后面就簡單了。

?

代碼：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <string.h>
#include <math.h>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <vector>

using namespace std;

string a,b;
long long val[30][30];
int len_a,len_b,n;
long long money;
char ans[100005];

void ready()
{
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>a>>b>>n;
    len_a=a.size();
    len_b=b.size();
    for(int i=1;i<=26;i++)
        for(int j=1;j<=26;j++)
          val[i][j]=1000000000;
    for(int i=1;i<=n;i++)
    {
        char x,y;
        long long v;
        cin>>x>>y>>v;
        val[x-'a'+1][y-'a'+1]=min(val[x-'a'+1][y-'a'+1],v);
    }
    for(int i=1;i<=26;i++)
        val[i][i]=0;
    for(int k=1;k<=26;k++)
        for(int i=1;i<=26;i++)
          for(int j=1;j<=26;j++)
            val[i][j]=min(val[i][j],val[i][k]+val[k][j]);
}

bool work()
{

    if(len_a!=len_b)
        return false;
    for(int i=0;i<len_a;i++)
    {
        if(a[i]!=b[i])
        {
            long long cost=1000000000,ci;
            int ai=a[i]-'a'+1;
            int bi=b[i]-'a'+1;
            for(int j=1;j<=26;j++)
            {
                if(val[ai][j]+val[bi][j]<cost)
                {
                    cost=val[ai][j]+val[bi][j];
                    ci=j;
                }
            }
            if(cost==1000000000)
                return false;
            money+=cost;
            ans[i]=char('a'+ci-1);
        }
        else
        {
            ans[i]=a[i];
        }
    }
    cout<<money<<'\n';
    for(int i=0;i<len_a;i++)
        cout<<ans[i];
    return true;
}

int main()
{
    ready();
    if(!work())
        cout<<-1;
    return 0;
}

?

?

G題

Gym - 100962A?

Problem A. ABBA Input file: standard input Output file: standard output Time limit: 1 second Memory limit: 256 mebibytes In this problem, we operate with tables of fixed size h × w consisting of real values. Let’s define an addition operation on two tables as their component-wise sum. A multiplication table for two real vectors α = (α1, α2, . . . , αh) and β = (β1, β2 . . . , βw) is the table Tα,β where the element at the intersection of i-th row and j-th column is αi · βj . You start with a table of size h × w consisting of zeroes. In one turn, you are allowed to add a multiplication table for two arbitrary real vectors α of length h and β of length w to the current table. Your task is to make the current table equal to a goal table G in the minimum number of turns. What is the minimum number of turns you have to perform? Input The first line of input contains two integers h and w (1 ≤ h, w ≤ 200). The i-th of the following h lines contain w space-separated integers ai,1, ai,2, . . . , ai,w (?106 ≤ ai,j ≤ 106 ), where ai,j is the value on the intersection of i-th row and j-th column of the goal table G. Output If it’s impossible to obtain the goal table G, print “-1” (without the quotes). Otherwise, output the minimum number of turns you have to perform in order to achieve it. Examples standard input standard output 3 5 1 2 3 4 5 2 4 6 8 10 3 6 9 12 15 1 3 3 2 0 2 0 2 0 2 0 2 2 Note In the first sample, the table T can be obtained using α = ( 1 2 3) , β = ( 1 2 3 4 5) . In the second sample, the table T can be obtained as sum of Tα1,β1 = ? ? 1 1 1 1 1 1 1 1 1 ? ? for vectors α1 = ( 1 1 1) , β1 = ( 1 1 1) and Tα2,β2 = ? ? 1 ?1 1 ?1 1 ?1 1 ?1 1 ? ? for vectors α2 = ( ?1 1 ?1 ) , β2 = ( ?1 1 ?1 )

?

題意：求矩陣的秩。

身為一個數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)的學(xué)生，高等代數(shù)上學(xué)期也學(xué)了，高斯消元法求矩陣的秩也是我們平常的做法。上學(xué)期高代學(xué)得不錯，專業(yè)第5，但是這道題看不懂題根本不知道再求秩......

而且以前不敢寫高斯消元法的代碼就是怕經(jīng)度問題，現(xiàn)在打出來了，剛剛好可以用進(jìn)程序設(shè)計的課程設(shè)計里。nice！

高斯消元法，也就是湊1消去后面的項，直到形成上三角矩陣。

代碼：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <string.h>
#include <math.h>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <vector>

using namespace std;

const long double ep=1e-2;
long double a[205][205];
int r,c;  

void ready()
{
    ios::sync_with_stdio(false),cin.tie(0);
	cin>>r>>c;
	for(int i=1;i<=r;i++)
	  for(int j=1;j<=c;j++)
	    cin>>a[i][j]; 
}

void work()
{
	int row=1,col=1;
	for( ;row<=r && col<=c;row++,col++)
	{
		int max_r=row;
		for(int i=row+1;i<=r;i++)
		  if(abs(a[i][col])>abs(a[max_r][col]))
		    max_r=i;
		if(max_r!=row)
		  for(int i=row;i<=c;i++)
		    swap(a[row][i],a[max_r][i]); 
		if(abs(a[row][col])<ep)
		{
			row--; 
			continue;
		}
		for(int i=row+1;i<=r;i++)
		  if(abs(a[i][col])>ep)
		  {
		  	double t=a[i][col]/a[row][col];
		  	for(int j=row;j<=c;j++)
		  	  a[i][j]-=t*a[row][j];
		  }
	}
	cout<<row-1;

}

int main()
{
    ready();
    work();
    return 0;
}

?

好好學(xué)英語。下次帶字典去了。