A. Cashier

Description:

Vasya has recently got a job as a cashier at a local store. His day at work is $L$L minutes long. Vasya has already memorized $n$n regular customers, the $i$i-th of which comes after $t_i$ti​ minutes after the beginning of the day, and his service consumes $l_i$li​ minutes. It is guaranteed that no customer will arrive while Vasya is servicing another customer.
Vasya is a bit lazy, so he likes taking smoke breaks for $a$a minutes each. Those breaks may go one after another, but Vasya must be present at work during all the time periods he must serve regular customers, otherwise one of them may alert his boss. What is the maximum number of breaks Vasya can take during the day?

Input:

The first line contains three integers $n$n, $L$L and $a$a ( $0\le n\le 10^5$0≤n≤105, $1\le L\le 10^9$1≤L≤109, $1\le a\le L$1≤a≤L).
The $i$i-th of the next $n$n lines contains two integers $t_i$ti​ and $l_i$li​ ( $0\le t_i\le L-1$0≤ti​≤L−1, $1\le l_i\le L$1≤li​≤L). It is guaranteed that $t_i+l_i\le t_{i+1}$ti​+li​≤ti+1​ and $t_n+l_n\le L$tn​+ln​≤L.

Output

Output one integer — the maximum number of breaks.

Sample Input:

2 11 3
0 1
1 1

Sample Output:

3

Sample Input:

0 5 2

Sample Output:

2

Sample Input:

1 3 2
1 2

Sample Output:

0

题目链接

Vasya总共工作L分钟，抽一根烟要a分钟，在有顾客时Vasya不能抽烟，求Vasya最多能抽几根烟。

因为 $t_i+l_i\le t_{i+1}$ti​+li​≤ti+1​，所以只需要根据输入顺序计算Vasya有多少空闲时间进行抽烟。

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char *argv[]) {
    int n, L, a;
    scanf("%d%d%d", &n, &L, &a);
    int Keep = 0, Ans = 0;
    for (int i = 0, t, l; i < n; ++i) {
        scanf("%d%d", &t, &l);
        Ans += (t - Keep) / a;
        Keep = t + l;
    }
    Ans += (L - Keep) / a;
    printf("%d\n", Ans);
    return 0;
}

B. Forgery

Description:

Student Andrey has been skipping physical education lessons for the whole term, and now he must somehow get a passing grade on this subject. Obviously, it is impossible to do this by legal means, but Andrey doesn’t give up. Having obtained an empty certificate from a local hospital, he is going to use his knowledge of local doctor’s handwriting to make a counterfeit certificate of illness. However, after writing most of the certificate, Andrey suddenly discovered that doctor’s signature is impossible to forge. Or is it?
For simplicity, the signature is represented as an $n\times m$n×m grid, where every cell is either filled with ink or empty. Andrey’s pen can fill a $3\times 3$3×3 square without its central cell if it is completely contained inside the grid, as shown below.

xxx
x.x
xxx
Determine whether is it possible to forge the signature on an empty $n\times m$n×m grid.

Input:

The first line of input contains two integers $n$n and $m$m ( $3\le n,m\le 1000$3≤n,m≤1000).
Then $n$n lines follow, each contains $m$m characters. Each of the characters is either ‘.’, representing an empty cell, or ‘#’, representing an ink filled cell.

Output

If Andrey can forge the signature, output “YES”. Otherwise output “NO”.
You can print each letter in any case (upper or lower).

Sample Input:

3 3

#.#

Sample Output:

YES

Sample Input:

3 3

Sample Output:

NO

Sample Input:

4 3

Sample Output:

YES

Sample Input:

5 7
…
.#####.
.#.#.#.
.#####.
…

Sample Output:

YES

题目链接

N*M的一个签名形状，Andrey每次只能在一个3*3的正方形内填充除中心方格以外的所有方格，求最后Andrey能否画出签名（’#‘全部填充，’.'全部不填充）。

枚举每一个方格，若其周围八个方格都为’#‘的全部填充，最后判断’#'是否全部被填充。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 5;

int N, M;
char Maze[maxn][maxn];
bool Book[maxn][maxn];

void Change(int X, int Y) {
    for (int i = -1; i <= 1; ++i) {
        for (int j = -1; j <= 1; ++j) {
            if (i == 0 && j == 0) {
                continue;
            }
            int NX = X + i, NY = Y + j;
            if (NX >= 0 && NX < N && NY >= 0 && NY < M) {
                if (Maze[NX][NY] == '.') {
                    return;
                }
            }
        }
    }
    for (int i = -1; i <= 1; ++i) {
        for (int j = -1; j <= 1; ++j) {
            if (i == 0 && j == 0) {
                continue;
            }
            int NX = X + i, NY = Y + j;
            Book[NX][NY] = true;
        }
    }
}

int main(int argc, char *argv[]) {
    scanf("%d%d", &N, &M);
    for (int i = 0; i < N; ++i) {
        scanf("%s", Maze[i]);
    }
    memset(Book, false, sizeof(Book));
    for (int i = 1; i < N - 1; ++i) {
        for (int j = 1; j < M - 1; ++j) {
            Change(i, j);
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (Maze[i][j] == '#' && Book[i][j] == false) {
                printf("NO\n");
                return 0;
            }
        }
    }
    printf("YES\n");
    return 0;
}

C. Sequence Transformation

Description:

Let’s call the following process a transformation of a sequence of length $n$n.
If the sequence is empty, the process ends. Otherwise, append the greatest common divisor (GCD) of all the elements of the sequence to the result and remove one arbitrary element from the sequence. Thus, when the process ends, we have a sequence of $n$n integers: the greatest common divisors of all the elements in the sequence before each deletion.
You are given an integer sequence $1,2,\dots ,n$1,2,…,n. Find the lexicographically maximum result of its transformation.
A sequence $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​ is lexicographically larger than a sequence $b_1,b_2,\dots ,b_n$b1​,b2​,…,bn​, if there is an index $i$i such that $a_j=b_j$aj​=bj​ for all $j\&lt;i$j<i, and $a_i\&gt;b_i$ai​>bi​.

Input:

The first and only line of input contains one integer $n$n ( $1\le n\le 10^6$1≤n≤106).

Output

Output $n$n integers — the lexicographically maximum result of the transformation.

Sample Input:

3

Sample Output:

1 1 3

Sample Input:

2

Sample Output:

1 2

Sample Input:

1

Sample Output:

1

题目链接

对一串1~n的数列进行n次操作，每次操作先向数列中加入数列所有数的最大公约数然后删除数列中任意一个数(不是后加入的最大公约数)，求最后字典序最大的数列结果。

对于一串数初始最大公约数一定为1，首先删除奇数（奇数偶数同时存在最大公约数只能为1）加入最大公约数1，删除之后目前最大公约数为2，将所有偶数除以2，此时数列是一个1~n/2的连续数列，继续首先删除奇数加入最大公约数2，删除之后目前最大公约数为2×2，继续将所有偶数除以2…直到连续数列长度≤3位置，当连续数列长度≤3时特判数列最大公约数。

显然此求解方式为递归，连续数列长度≤3为递归出口。

AC代码:

#include <bits/stdc++.h>
using namespace std;

vector<int> Ans;

void Solve(int N, int Factor) {
    if (N == 1) {
        Ans.push_back(Factor);
        return;
    }
    else if (N == 2) {
        Ans.push_back(Factor);
        Ans.push_back(Factor * 2);
        return;
    }
    else if (N == 3) {
        Ans.push_back(Factor);
        Ans.push_back(Factor);
        Ans.push_back(Factor * 3);
        return;
    }
    for (int i = 1; i <= N; ++i) {
        if (i & 1) {
            Ans.push_back(Factor);
        }
    }
    Solve(N / 2, Factor * 2);
}

int main(int argc, char *argv[]) {
    int N;
    scanf("%d", &N);
    Solve(N, 1);
    for (auto i : Ans) {
        printf("%d ", i);
    }
    return 0;
}

D. Nature Reserve

Description:

There is a forest that we model as a plane and live $n$n rare animals. Animal number $i$i has its lair in the point $(x_i,y_i)$(xi​,yi​). In order to protect them, a decision to build a nature reserve has been made.
The reserve must have a form of a circle containing all lairs. There is also a straight river flowing through the forest. All animals drink from this river, therefore it must have at least one common point with the reserve. On the other hand, ships constantly sail along the river, so the reserve must not have more than one common point with the river.
For convenience, scientists have made a transformation of coordinates so that the river is defined by $y=0$y=0. Check whether it is possible to build a reserve, and if possible, find the minimum possible radius of such a reserve.

Input:

The first line contains one integer $n$n ( $1\le n\le 10^5$1≤n≤105) — the number of animals.
Each of the next $n$n lines contains two integers $x_i$xi​, $y_i$yi​ ( $-10^7\le x_i,y_i\le 10^7$−107≤xi​,yi​≤107) — the coordinates of the $i$i-th animal’s lair. It is guaranteed that $y_i\ne 0$yi​̸​=0. No two lairs coincide.

Output

If the reserve cannot be built, print $-1$−1. Otherwise print the minimum radius. Your answer will be accepted if absolute or relative error does not exceed $10^{-6}$10−6.
Formally, let your answer be $a$a, and the jury’s answer be $b$b. Your answer is considered correct if $\frac{\mid a-b\mid }{\max (1,\mid b\mid )}\le 10^{-6}$max(1,∣b∣)∣a−b∣​≤10−6.

Sample Input:

1
0 1

Sample Output:

0.5

Sample Input:

3
0 1
0 2
0 -3

Sample Output:

-1

Sample Input:

2
0 1
1 1

Sample Output:

0.625

题目链接

求与x轴相切且包含所有输入点半径最小的圆。

直接对圆的半径进行二分查找，若当前二分值为半径R，则圆心一定在y=R直线上，求出圆心可在的横坐标范围，判断所有横坐标范围是否相交，根据判断结果缩小二分区间。

这里浮点数二分若只用Right - Left > eps进行判断会陷入死循环，需要限制二分循环次数(一般100即可)。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const double eps = 1e-8;

struct Point {
    long double X, Y;
    void input() {
        scanf("%LF%LF", &X, &Y);
    }
};

int N;
Point points[maxn];

bool Judge(long double R) {
    long double Left = -1e18, Right = 1e18;
    for (int i = 1; i <= N; ++i) {
        if (points[i].Y > R + R) {
            return false;
        }
        long double Dis = sqrt((2 * R - points[i].Y) * points[i].Y);
        Left = max(Left, points[i].X - Dis);
        Right = min(Right, points[i].X + Dis);
    }
    return Left <= Right;
}

int main(int argc, char *argv[]) {
    scanf("%d", &N);
    bool UpFlag = false, DownFlag = false;
    for (int i = 1; i <= N; ++i) {
        points[i].input();
        if (points[i].Y > 0) {
            UpFlag = true;
        }
        else if (points[i].Y < 0) {
            DownFlag = true;
        }
        points[i].Y = fabs(points[i].Y);
    }
    if (UpFlag && DownFlag) {
        printf("-1\n");
        return 0;
    }
    long double Left = 0, Right = 1e18;
    int Cnt = 100;
    while (Right - Left > eps && Cnt--) {
        long double Mid = (Left + Right) / 2.0;
        if (Judge(Mid)) {
            Right = Mid;
        }
        else {
            Left = Mid;
        }
    }
    printf("%LF\n", Left);
    return 0;
}