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]);
}
