Forethought Future Cup – Elimination Round

A – Love “A”

time limit per test1 second . memory limit per test256 megabytes

Alice has a string 𝑠s. She really likes the letter “a”. She calls a string good if strictly more than half of the characters in that string are “a”s. For example “aaabb”, “axaa” are good strings, and “baca”, “awwwa”, “” (empty string) are not.

Alice can erase some characters from her string 𝑠s. She would like to know what is the longest string remaining after erasing some characters (possibly zero) to get a good string. It is guaranteed that the string has at least one “a” in it, so the answer always exists.Input

The first line contains a string 𝑠s (1≤|𝑠|≤501≤|s|≤50) consisting of lowercase English letters. It is guaranteed that there is at least one “a” in 𝑠s.Output

Print a single integer, the length of the longest good string that Alice can get after erasing some characters from 𝑠s.
Examples
input

xaxxxxa

output

3

input

aaabaa

output

6

Note

In the first example, it’s enough to erase any four of the “x”s. The answer is 33 since that is the maximum number of characters that can remain.

In the second example, we don’t need to erase any characters.

签到

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)1e5+100;
int main(){
	string s;cin>>s;int len=s.length(),tot=0;;
	rep(i,0,len-1) if(s[i]=='a') tot++;
	cout<<min(tot*2-1,len)<<endl;
}


B – Hate “A”

time limit per test1 second memory limit per test256 megabytes

Bob has a string 𝑠s consisting of lowercase English letters. He defines 𝑠′s′ to be the string after removing all “a” characters from 𝑠s(keeping all other characters in the same order). He then generates a new string 𝑡t by concatenating 𝑠s and 𝑠′s′. In other words, 𝑡=𝑠+𝑠′t=s+s′(look at notes for an example).

You are given a string 𝑡t. Your task is to find some 𝑠s that Bob could have used to generate 𝑡t. It can be shown that if an answer exists, it will be unique.Input

The first line of input contains a string 𝑡t (1≤|𝑡|≤1051≤|t|≤105) consisting of lowercase English letters.Output

Print a string 𝑠s that could have generated 𝑡t. It can be shown if an answer exists, it is unique. If no string exists, print “:(” (without double quotes, there is no space between the characters).
Examples
input

aaaaa

output

aaaaa

input

aacaababc

output

🙁

input

ababacacbbcc

output

ababacac

input

baba

output

🙁

Note

In the first example, we have 𝑠=s= “aaaaa”, and 𝑠′=s′= “”.

In the second example, no such 𝑠s can work that will generate the given 𝑡t.

In the third example, we have 𝑠=s= “ababacac”, and 𝑠′=s′= “bbcc”, and 𝑡=𝑠+𝑠′=t=s+s′= “ababacacbbcc”.

可知答案串必定是原串的某个前缀,那么可以暴力枚举答案

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)1e5+100;
int main(){
	string s,c;cin>>s;int len=s.length(); c.clear();
	rep(i,0,len-1){
		if(s[i]!='a') c+=s[i];
		if(c==s.substr(i+1)){
			cout<<s.substr(0,i+1)<<endl;
			exit(0);
		}
	}
	cout<<":(\n";
}


C – Tree Diameter

time limit per test4 seconds memory limit per test256 megabytes

There is a weighted tree with 𝑛n nodes and 𝑛−1n−1 edges. The nodes are conveniently labeled from 11 to 𝑛n. The weights are positive integers at most 100100. Define the distance between two nodes to be the sum of edges on the unique path between the nodes. You would like to find the diameter of the tree. Diameter is the maximum distance between a pair of nodes.

Unfortunately, the tree isn’t given to you, but you can ask some questions about it. In one question, you can specify two nonempty disjoint sets of nodes 𝑝p and 𝑞q, and the judge will return the maximum distance between a node in 𝑝p and a node in 𝑞q. In the words, maximum distance between 𝑥x and 𝑦y, where 𝑥∈𝑝x∈p and 𝑦∈𝑞y∈q. After asking not more than 99 questions, you must report the maximum distance between any pair of nodes.Interaction

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1≤𝑡≤10001≤t≤1000). Description of the test cases follows.

The first line of each test case contains an integer 𝑛n (2≤𝑛≤1002≤n≤100) — the number of nodes in the tree.

To ask a question, print “𝑘1 𝑘2 𝑎1 𝑎2 … 𝑎𝑘1 𝑏1 𝑏2 … 𝑏𝑘2k1 k2 a1 a2 … ak1 b1 b2 … bk2” (𝑘1,𝑘2≥1(k1,k2≥1 and 𝑘1+𝑘2≤𝑛k1+k2≤n). These two sets must be nonempty and disjoint. The judge will respond with a single integer max𝑝,𝑞𝑑𝑖𝑠𝑡(𝑎𝑝,𝑏𝑞)maxp,qdist(ap,bq). If you ever get a result of −1−1 (because you printed an invalid query), exit immediately to avoid getting other verdicts.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see documentation for other languages.

When you are ready to answer, print “−1 𝑑−1 d”, where 𝑑d is the maximum shortest distance over all pairs of nodes.

You can only ask at most 99 questions per test case.

Hack Format

To hack, use the following format. Note that you can only hack with one test case.

The first line should contain a single integer 𝑡t (𝑡=1t=1).

The second line should contain a single integer 𝑛n (2≤𝑛≤1002≤n≤100).

Each of the next 𝑛−1n−1 lines should contain three integers 𝑎𝑖,𝑏𝑖,𝑐𝑖ai,bi,ci (1≤𝑎𝑖,𝑏𝑖≤𝑛1≤ai,bi≤n, 1≤𝑐𝑖≤1001≤ci≤100). This denotes an undirected edge between nodes 𝑎𝑖ai and 𝑏𝑖bi with weight 𝑐𝑖ci. These edges must form a tree.
Example
input

2 
5
9
6
10
9
10
2
99

output

1 4 1 2 3 4 5 
1 4 2 3 4 5 1
1 4 3 4 5 1 2
1 4 4 5 1 2 3
1 4 5 1 2 3 4
-1 10
1 1 1 2
-1 99

Note

In the first example, the first tree looks as follows:

In the first question, we have 𝑝=1p=1, and 𝑞=2,3,4,5q=2,3,4,5. The maximum distance between a node in 𝑝p and a node in 𝑞q is 99 (the distance between nodes 11 and 55).

The second tree is a tree with two nodes with an edge with weight 9999 between them.

有趣的交互题;
首先我们有结论:对于任意点,和它距离最远的点必定是直径的某个端点;于是我们可以先查询任意一个点到其余所有点的最大距离,然后再二分查找距离最大的那个点,找到以后再一次查询就可以找到答案;
最坏情况下需要查询1+log2(99)+1=9次;

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)1e5+100;
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        cout<<"1 "<<n-1; rep(i,1,n) cout<<" "<<i; cout<<endl;
        int k;cin>>k;
        int l=2,r=n;
        while(l<r){
            int mid=l+r>>1;
            cout<<"1 "<<mid-l+1<<" 1"; rep(i,l,mid) cout<<" "<<i; cout<<endl;
            int x;cin>>x;
            if(x<k) l=mid+1;else r=mid;
        }
        cout<<"1 "<<n-1<<" "<<l; rep(i,1,n) if(i!=l) cout<<" "<<i; cout<<endl;
        int x;cin>>x;
        cout<<"-1 "<<x<<endl;
    }
}


D – Frog Jumping

time limit per test2 seconds memory limit per test256 megabytes

A frog is initially at position 00 on the number line. The frog has two positive integers 𝑎a and 𝑏b. From a position 𝑘k, it can either jump to position 𝑘+𝑎k+a or 𝑘−𝑏k−b.

Let 𝑓(𝑥)f(x) be the number of distinct integers the frog can reach if it never jumps on an integer outside the interval [0,𝑥][0,x]. The frog doesn’t need to visit all these integers in one trip, that is, an integer is counted if the frog can somehow reach it if it starts from 00.

Given an integer 𝑚m, find ∑𝑚𝑖=0𝑓(𝑖)∑i=0mf(i). That is, find the sum of all 𝑓(𝑖)f(i) for 𝑖i from 00 to 𝑚m.Input

The first line contains three integers 𝑚,𝑎,𝑏m,a,b (1≤𝑚≤109,1≤𝑎,𝑏≤1051≤m≤109,1≤a,b≤105).Output

Print a single integer, the desired sum.
Examples
input

7 5 3

output

19

input

1000000000 1 2019

output

500000001500000001

input

100 100000 1

output

101

input

6 4 5

output

10

Note

In the first example, we must find 𝑓(0)+𝑓(1)+…+𝑓(7)f(0)+f(1)+…+f(7). We have 𝑓(0)=1,𝑓(1)=1,𝑓(2)=1,𝑓(3)=1,𝑓(4)=1,𝑓(5)=3,𝑓(6)=3,𝑓(7)=8f(0)=1,f(1)=1,f(2)=1,f(3)=1,f(4)=1,f(5)=3,f(6)=3,f(7)=8. The sum of these values is 1919.

In the second example, we have 𝑓(𝑖)=𝑖+1f(i)=i+1, so we want to find ∑109𝑖=0𝑖+1∑i=0109i+1.

In the third example, the frog can’t make any jumps in any case.

首先如果没有限制条件,那么很容易想到坐标轴上所有gcd(a,b)的倍数都可以走到,这个值是等差数列。但是对于小于a+b的坐标是不严格满足这个式子的,考虑到a,b<2e5,可以直接暴力求答案,每次贪心的走,可以k-b就k-b,否则才k+a;

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)2e5+100;
int vis[maxn],step[maxn],pos=0;
ll gcd(ll x, ll y){return y?gcd(y,x%y):x;}
int main(){
	ll m,a,b;cin>>m>>a>>b;
	const ll g=gcd(a,b);ll last=m/g+1;
	ll ans=(1+last)*last/2*g-(last*g-1-m)*last;
	vis[step[++pos]=0]=1;
	while(1){
		++pos;
		step[pos]=step[pos-1]>=b?step[pos-1]-b:step[pos-1]+a;
		if(vis[step[pos]]) break;
		vis[step[pos]]=1;
	} --pos;
	for(int i=0,j=1;i<a+b&&i<=m;++i){
		ans-=i/g+1;
		while(step[j]<=i&&j<=pos) ++j;--j;
		ans+=j;
	}
	cout<<ans<<endl;
}

发表评论,支持MarkDown语法