Codeforces Round #384(Div.2)(A~D

A. Vladik and flights
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Vladik is a competitive programmer. This year he is going to win the International Olympiad in Informatics. But it is not as easy as it sounds: the question Vladik face now is to find the cheapest way to get to the olympiad.
Vladik knows n airports. All the airports are located on a straight line. Each airport has unique id from 1 to n, Vladik's house is situated next to the airport with id a, and the place of the olympiad is situated next to the airport with id b. It is possible that Vladik's house and the place of the olympiad are located near the same airport.
To get to the olympiad, Vladik can fly between any pair of airports any number of times, but he has to start his route at the airport a and finish it at the airport b.
Each airport belongs to one of two companies. The cost of flight from the airport i to the airport j is zero if both airports belong to the same company, and |i - j| if they belong to different companies.
Print the minimum cost Vladik has to pay to get to the olympiad.
Input
The first line contains three integers n, a, and b (1 ≤ n ≤ 10^5, 1 ≤ a, b ≤ n) — the number of airports, the id of the airport from which Vladik starts his route and the id of the airport which he has to reach.
The second line contains a string with length n, which consists only of characters 0 and 1. If the i-th character in this string is 0, then i-th airport belongs to first company, otherwise it belongs to the second.
Output
Print single integer — the minimum cost Vladik has to pay to get to the olympiad.
Examples
input
4 1 4
1010
output
1
input
5 5 2
10110
output
0
Note
In the first example Vladik can fly to the airport 2 at first and pay |1 - 2| = 1 (because the airports belong to different companies), and then fly from the airport 2 to the airport 4 for free (because the airports belong to the same company). So the cost of the whole flight is equal to 1. It's impossible to get to the olympiad for free, so the answer is equal to 1.
In the second example Vladik can fly directly from the airport 5 to the airport 2, because they belong to the same company.

题意：有n个地点，每个地点都有航班，0代表这个地点的航班属于第一家公司，1代表这个地点的航班属于第二家公司。如果出发地和目的地都属于同一家公司的航班则免费，否则就是两点之间标号差的绝对值。给出起点和终点的标号，问最少需要花费的费用（可以先到中间点再换乘别的航班）。

事实上，如果起点的公司号和终点的一致，肯定不花钱。
如果不一致，由于此题求的是最少花费数，且公司只有两家，因此我们可以先乘与起点相同的航班去靠近与终点航班相同的航班的地点相邻的不相同的点。实际上最少情况就是0切换为相邻的1或1切换为相邻的0.
答案不是0就是1.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 1e5+10;

int n, a, b;
char loc[N];//每个地点的航班所属的公司情况;//0: 第一家公司, 1: 第二家公司;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> a >> b;
    cin >> loc;

    int sum = 0;
    int be, en;//起点和终点;
    be = min(a, b);
    en = max(a, b);//由小到大;
    int closetoreach = be;
    //cout << be << " " << en << endl;
    if (loc[be-1] == loc[en-1]) cout << 0 << endl;
    else cout << 1 << endl; 
    return 0;
}

B. Chloe and the sequence
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Chloe, the same as Vladik, is a competitive programmer. She didn't have any problems to get to the olympiad like Vladik, but she was confused by the task proposed on the olympiad.
Let's consider the following algorithm of generating a sequence of integers. Initially we have a sequence consisting of a single element equal to 1. Then we perform (n - 1) steps. On each step we take the sequence we've got on the previous step, append it to the end of itself and insert in the middle the minimum positive integer we haven't used before. For example, we get the sequence [1, 2, 1] after the first step, the sequence [1, 2, 1, 3, 1, 2, 1] after the second step.

The task is to find the value of the element with index k (the elements are numbered from 1) in the obtained sequence, i. e. after (n - 1) steps.
Please help Chloe to solve the problem!
Input
The only line contains two integers n and k (1 ≤ n ≤ 50, 1 ≤ k ≤ 2n - 1).
Output
Print single integer — the integer at the k-th position in the obtained sequence.
Examples
input
3 2
output
2
input
4 8
output
4
Note
In the first sample the obtained sequence is [1, 2, 1, 3, 1, 2, 1]. The number on the second position is 2.
In the second sample the obtained sequence is [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]. The number on the eighth position is 4.

题意：给出一个n，每个n对应的序列的排列方法如题中所述，给出一个index值，要求第index个元素在序列中对应的值。

这道题的序列是有规律的，经过发现，最终的结果就是index分解质因数后2的个数+1或者index的二进制最后一个1之后的0的个数+1.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

LL n, k;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> k;
    if (k % 2 == 1) {//奇数;
        cout << 1 << endl;
    }
    else {
        int sum = 0;//分解质因数中2的个数;
        while (k % 2 == 0) {
            k /= 2;//k >>= 1;
            ++sum;
        }
        cout << (sum + 1) << endl;  
    }
    return 0;
}

C. Vladik and fractions
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Vladik and Chloe decided to determine who of them is better at math. Vladik claimed that for any positive integer n he can represent fraction

as a sum of three distinct positive fractions in form .
Help Vladik with that, i.e for a given n find three distinct positive integers x, y and z such that . Because Chloe can't check Vladik's answer if the numbers are large, he asks you to print numbers not exceeding 10^9.
If there is no such answer, print -1.
Input
The single line contains single integer n (1 ≤ n ≤ 10^4).
Output
If the answer exists, print 3 distinct numbers x, y and z (1 ≤ x, y, z ≤ 10^9
, x ≠ y, x ≠ z, y ≠ z). Otherwise print -1.
If there are multiple answers, print any of them.
Examples
input
3
output
2 7 42
input
7
output
7 8 56

题意：给一个数n，要求找到三个互不相同的数x，y，z，使得满足题目中的方程，如果有多个，任意输出一个；如果没有，则输出-1.

其实这道题我之前想多了，看了别人的博客后恍然大悟：这道题可以输出任何一个，那么我们随意构造一个满足上面条件的不就可以了。
当n=1时，由于等式左边为2，右边无论如何都无法构造符合条件的数。
其他情况：令x = n，则原式变为1/n = 1/y + 1/z.
变形：z = (y*n) / (y-n).
由于三个数互不相同，因此令y = n + 1，则z = n * (n + 1).

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    if (n == 1) cout << -1 << endl;//n == 1时, 左式=2, x, y, z互不相等, 无法构造;
    else cout << n << " " << (n + 1) << " " << n * (n + 1) << endl; 
    return 0; 
}

D. Chloe and pleasant prizes
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Generous sponsors of the olympiad in which Chloe and Vladik took part allowed all the participants to choose a prize for them on their own. Christmas is coming, so sponsors decided to decorate the Christmas tree with their prizes.
They took n prizes for the contestants and wrote on each of them a unique id (integer from 1 to n). A gift i is characterized by integer ai — pleasantness of the gift. The pleasantness of the gift can be positive, negative or zero. Sponsors placed the gift 1 on the top of the tree. All the other gifts hung on a rope tied to some other gift so that each gift hung on the first gift, possibly with a sequence of ropes and another gifts. Formally, the gifts formed a rooted tree with n vertices.
The prize-giving procedure goes in the following way: the participants come to the tree one after another, choose any of the remaining gifts and cut the rope this prize hang on. Note that all the ropes which were used to hang other prizes on the chosen one are not cut. So the contestant gets the chosen gift as well as the all the gifts that hang on it, possibly with a sequence of ropes and another gifts.
Our friends, Chloe and Vladik, shared the first place on the olympiad and they will choose prizes at the same time! To keep themselves from fighting, they decided to choose two different gifts so that the sets of the gifts that hang on them with a sequence of ropes and another gifts don't intersect. In other words, there shouldn't be any gift that hang both on the gift chosen by Chloe and on the gift chosen by Vladik. From all of the possible variants they will choose such pair of prizes that the sum of pleasantness of all the gifts that they will take after cutting the ropes is as large as possible.
Print the maximum sum of pleasantness that Vladik and Chloe can get. If it is impossible for them to choose the gifts without fighting, print Impossible.
Input
The first line contains a single integer n (1 ≤ n ≤ 2·10^5) — the number of gifts.
The next line contains n integers a1, a2, ..., an ( - 10^9 ≤ ai ≤ 10^9) — the pleasantness of the gifts.
The next (n - 1) lines contain two numbers each. The i-th of these lines contains integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — the description of the tree's edges. It means that gifts with numbers ui and vi are connected to each other with a rope. The gifts' ids in the description of the ropes can be given in arbirtary order: vi hangs on ui or ui hangs on vi.
It is guaranteed that all the gifts hang on the first gift, possibly with a sequence of ropes and another gifts.
Output
If it is possible for Chloe and Vladik to choose prizes without fighting, print single integer — the maximum possible sum of pleasantness they can get together.
Otherwise print Impossible.
Examples
input
8
0 5 -1 4 3 2 6 5
1 2
2 4
2 5
1 3
3 6
6 7
6 8
output
25
input
4
1 -5 1 1
1 2
1 4
2 3
output
2
input
1
-1
output
Impossible

题意：给一棵树，编号为1~n，每个节点都有相应的权值。找出该树中两棵不相交的点权值和最大的子树，并求这两棵子树的最大点权值之和。

这道题可以用树形DP做，但是找两棵符合条件的子树我开始不会，因此参考别人的博客写的。

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2 * 1e5 + 10;
const LL INF = 10e18;

vector<int> g[N];//与该点直接相连的点的集合;
LL scores[N];//该点所对应的分数值;
bool vis[N];//该点是否被遍历过;
LL dp[N];//以该点为根的所有子树的最大权值和;
LL sum[N];//以该点为根的子树的所有权值和(包括自己);

int n;
LL ans;
void init() {
    for (int i = 1;i <= n;++i) {
        g[i].clear();
    }
    memset(scores, 0, sizeof(scores));
    memset(vis, false, sizeof(vis));
    memset(dp, 0, sizeof(dp));
    memset(sum, 0, sizeof(sum));
    ans = -INF;
}

void dfs(int u) {
    sum[u] += scores[u];

    int len = g[u].size();
    for (int i = 0;i < len;++i) {
        int v = g[u][i];

        if (vis[v]) continue;
        vis[v] = true;
        dfs(v);
        sum[u] += sum[v];//该点的值以及它的子节点的值加入此点的父节点;

        if (dp[u] > -INF) ans = max(ans, dp[u]+dp[v]);//dp[u]还是上一次的最大值;
        dp[u] = max(dp[u], dp[v]);//以u节点为父节点的最大值更新;
    }

    dp[u] = max(dp[u], sum[u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    init();
    for (int i = 1;i <= n;++i) {
        cin >> scores[i];
        dp[i] = -INF;
    }

    int u, v;
    for (int i = 1;i <= n-1;++i) {//树的边与点的性质;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vis[1] = true;
    dfs(1);//该点为根节点;

    if (ans <= -INF) cout << "Impossible" << endl;
    else cout << ans << endl;
    return 0;
}