# Educational Codeforces Round 72

## A. Creating a Character

time limit per test1 second memory limit per test256 megabytes

You play your favourite game yet another time. You chose the character you didn’t play before. It has 𝑠𝑡𝑟str points of strength and 𝑖𝑛𝑡int points of intelligence. Also, at start, the character has 𝑒𝑥𝑝exp free experience points you can invest either in strength or in intelligence (by investing one point you can either raise strength by 11 or raise intelligence by 11).

Since you’d like to make some fun you want to create a jock character, so it has more strength than intelligence points (resulting strength is strictly greater than the resulting intelligence).

Calculate the number of different character builds you can create (for the purpose of replayability) if you must invest all free points. Two character builds are different if their strength and/or intellect are different.Input

The first line contains the single integer 𝑇T (1≤𝑇≤1001≤T≤100) — the number of queries. Next 𝑇T lines contain descriptions of queries — one per line.

This line contains three integers 𝑠𝑡𝑟str, 𝑖𝑛𝑡int and 𝑒𝑥𝑝exp (1≤𝑠𝑡𝑟,𝑖𝑛𝑡≤1081≤str,int≤108, 0≤𝑒𝑥𝑝≤1080≤exp≤108) — the initial strength and intelligence of the character and the number of free points, respectively.Output

Print 𝑇T integers — one per query. For each query print the number of different character builds you can create.

Exampleinput

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

output

3
1
2
0

Note

In the first query there are only three appropriate character builds: (𝑠𝑡𝑟=7,𝑖𝑛𝑡=5)(str=7,int=5), (8,4)(8,4) and (9,3)(9,3). All other builds are either too smart or don’t use all free points.

In the second query there is only one possible build: (2,1)(2,1).

In the third query there are two appropriate builds: (7,6)(7,6), (8,5)(8,5).

In the fourth query all builds have too much brains.

#### 签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+10;
void solve(){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
printf("%d\n",max(min((a+c-b+1)/2,c+1),0));
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## B. Zmei Gorynich

time limit per test1 second memory limit per test256 megabytes

You are fighting with Zmei Gorynich — a ferocious monster from Slavic myths, a huge dragon-like reptile with multiple heads!

Initially Zmei Gorynich has 𝑥x heads. You can deal 𝑛n types of blows. If you deal a blow of the 𝑖i-th type, you decrease the number of Gorynich’s heads by 𝑚𝑖𝑛(𝑑𝑖,𝑐𝑢𝑟𝑋)min(di,curX), there 𝑐𝑢𝑟𝑋curX is the current number of heads. But if after this blow Zmei Gorynich has at least one head, he grows ℎ𝑖hi new heads. If 𝑐𝑢𝑟𝑋=0curX=0 then Gorynich is defeated.

You can deal each blow any number of times, in any order.

For example, if 𝑐𝑢𝑟𝑋=10curX=10, 𝑑=7d=7, ℎ=10h=10 then the number of heads changes to 1313 (you cut 77 heads off, but then Zmei grows 1010 new ones), but if 𝑐𝑢𝑟𝑋=10curX=10, 𝑑=11d=11, ℎ=100h=100 then number of heads changes to 00 and Zmei Gorynich is considered defeated.

Calculate the minimum number of blows to defeat Zmei Gorynich!

You have to answer 𝑡t independent queries.Input

The first line contains one integer 𝑡t (1≤𝑡≤1001≤t≤100) – the number of queries.

The first line of each query contains two integers 𝑛n and 𝑥x (1≤𝑛≤1001≤n≤100, 1≤𝑥≤1091≤x≤109) — the number of possible types of blows and the number of heads Zmei initially has, respectively.

The following 𝑛n lines of each query contain the descriptions of types of blows you can deal. The 𝑖i-th line contains two integers 𝑑𝑖di and ℎ𝑖hi (1≤𝑑𝑖,ℎ𝑖≤1091≤di,hi≤109) — the description of the 𝑖i-th blow.Output

For each query print the minimum number of blows you have to deal to defeat Zmei Gorynich.

If Zmei Gorynuch cannot be defeated print −1−1.

Exampleinput

3
3 10
6 3
8 2
1 4
4 10
4 1
3 2
2 6
1 100
2 15
10 11
14 100

output

2
3
-1

Note

In the first query you can deal the first blow (after that the number of heads changes to 10−6+3=710−6+3=7), and then deal the second blow.

In the second query you just deal the first blow three times, and Zmei is defeated.

In third query you can not defeat Zmei Gorynich. Maybe it’s better to convince it to stop fighting?

#### 签到题，稍微判一下，注意long long

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+10;
ll n,x;
void solve(){
scanf("%lld%lld",&n,&x);
ll a=0,b=0;
rep(i,1,n){
ll d,h;scanf("%lld%lld",&d,&h);
a=max(a,d);b=max(b,d-h);
}
if(a>=x){puts("1");return;}
if(!b){puts("-1");return;}
printf("%lld\n",a>=x?1:(ll)ceil((1.0*(x-a))/b)+1);
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## C. The Number Of Good Substrings

time limit per test4 seconds memory limit per test256 megabytes

You are given a binary string 𝑠s (recall that a string is binary if each character is either 00 or 11).

Let 𝑓(𝑡)f(t) be the decimal representation of integer 𝑡t written in binary form (possibly with leading zeroes). For example 𝑓(011)=3,𝑓(00101)=5,𝑓(00001)=1,𝑓(10)=2,𝑓(000)=0f(011)=3,f(00101)=5,f(00001)=1,f(10)=2,f(000)=0 and 𝑓(000100)=4f(000100)=4.

The substring 𝑠𝑙,𝑠𝑙+1,…,𝑠𝑟sl,sl+1,…,sr is good if 𝑟−𝑙+1=𝑓(𝑠𝑙…𝑠𝑟)r−l+1=f(sl…sr).

For example string 𝑠=1011s=1011 has 55 good substrings: 𝑠1…𝑠1=1s1…s1=1, 𝑠3…𝑠3=1s3…s3=1, 𝑠4…𝑠4=1s4…s4=1, 𝑠1…𝑠2=10s1…s2=10 and 𝑠2…𝑠4=011s2…s4=011.

Your task is to calculate the number of good substrings of string 𝑠s.

You have to answer 𝑡t independent queries.Input

The first line contains one integer 𝑡t (1≤𝑡≤10001≤t≤1000) — the number of queries.

The only line of each query contains string 𝑠s (1≤|𝑠|≤2⋅1051≤|s|≤2⋅105), consisting of only digits 00 and 11.

It is guaranteed that ∑𝑖=1𝑡|𝑠𝑖|≤2⋅105∑i=1t|si|≤2⋅105.Output

For each query print one integer — the number of good substrings of string 𝑠s.

Exampleinput

4
0110
0101
00001000
0001000

output

4
3
4
3

#### 考虑到2e5的二进制只有18位，所以暴力去判断，每次考虑一段连续的0作为前导0，数量为num，我们考虑这段0之后的二进制数res的值，令len=res的二进制长度，那么显然res的值要在区间[len,len+num]才会有答案，如果大于len+num则直接break，因为res的增长比len的增长快得多

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+10;
int n;
char s[maxn];
void solve(){
scanf("%s",s+1);
n=strlen(s+1);
ll ans=0,num=0;
rep(i,1,n){
if(s[i]=='0') num++;
else{
ll res=0;
for(int j=i;j<=n&&res<=j-i+1+num;++j){
res=res*2+s[j]-'0';
if(res>=j-i+1&&res<=num+j-i+1) ans++;
else break;
}
num=0;
}
}
printf("%lld\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## D. Coloring Edges

time limit per test1 second memory limit per test256 megabytes

You are given a directed graph with 𝑛n vertices and 𝑚m directed edges without self-loops or multiple edges.

Let’s denote the 𝑘k-coloring of a digraph as following: you color each edge in one of 𝑘k colors. The 𝑘k-coloring is good if and only if there no cycle formed by edges of same color.

Find a good 𝑘k-coloring of given digraph with minimum possible 𝑘k.Input

The first line contains two integers 𝑛n and 𝑚m (2≤𝑛≤50002≤n≤5000, 1≤𝑚≤50001≤m≤5000) — the number of vertices and edges in the digraph, respectively.

Next 𝑚m lines contain description of edges — one per line. Each edge is a pair of integers 𝑢u and 𝑣v (1≤𝑢,𝑣≤𝑛1≤u,v≤n, 𝑢≠𝑣u≠v) — there is directed edge from 𝑢u to 𝑣v in the graph.

It is guaranteed that each ordered pair (𝑢,𝑣)(u,v) appears in the list of edges at most once.Output

In the first line print single integer 𝑘k — the number of used colors in a good 𝑘k-coloring of given graph.

In the second line print 𝑚m integers 𝑐1,𝑐2,…,𝑐𝑚c1,c2,…,cm (1≤𝑐𝑖≤𝑘1≤ci≤k), where 𝑐𝑖ci is a color of the 𝑖i-th edge (in order as they are given in the input).

If there are multiple answers print any of them (you still have to minimize 𝑘k).

Examplesinput

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

output

1
1 1 1 1 1 

input

3 3
1 2
2 3
3 1

output

2
1 1 2 

#### 跑dfs，只要遇到环就把最后一条边染成2，否则都是1；

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
#define pii pair<int,int>
typedef long long ll;
const int maxn=(int)5e3+10;
int n,m,ans[maxn],vis[maxn],has[maxn],flag=1;
vector<pii> g[maxn];
void dfs(int u){
has[u]=1;vis[u]=1;
for(auto x:g[u]){
int v=x.first,id=x.second;
if(!vis[v]) dfs(v);
ans[id]=has[v]?2:1;
if(ans[id]==2) flag=2;
}
has[u]=0;
}
int main(){
scanf("%d%d",&n,&m);
rep(i,1,m){
int u,v;scanf("%d%d",&u,&v);
g[u].pb({v,i});
}
rep(i,1,n) if(!vis[i]) dfs(i);
printf("%d\n",flag);
rep(i,1,m) printf("%d ",ans[i]);
}