Codeforces Round #Pi (Div. 2) (ABCD題解)

 

聽說Round #Pi的意思是Round #314。。。

 

 

A. Lineland Mail time limit per test：3 seconds memory limit per test：256 megabytes

All cities of Lineland are located on the Ox coordinate axis. Thus, each city is associated with its position x_i — a coordinate on the Ox axis. No two cities are located at a single point.

Lineland residents love to send letters to each other. A person may send a letter only if the recipient lives in another city (because if they live in the same city, then it is easier to drop in).

Strange but true, the cost of sending the letter is exactly equal to the distance between the sender's city and the recipient's city.

For each city calculate two values ??min_i and max_i, where min_i is the minimum cost of sending a letter from the i-th city to some other city, and max_i is the the maximum cost of sending a letter from the i-th city to some other city

Input

The first line of the input contains integer n (2 ≤ n ≤ 10⁵) — the number of cities in Lineland. The second line contains the sequence of n distinct integers x₁, x₂, ..., x_n ( - 10⁹ ≤ x_i ≤ 10⁹), where x_i is the x-coordinate of the i-th city. All the x_i's are distinct and follow in ascending order.

Output

Print n lines, the i-th line must contain two integers min_i, max_i, separated by a space, where min_i is the minimum cost of sending a letter from the i-th city, and max_i is the maximum cost of sending a letter from the i-th city.

Sample test(s) Input

4
-5 -2 2 7

Output

3 12
3 9
4 7
5 12

Input

2
-1 1

Output

2 2
2 2

 

 

題目大意：一條線上n個點，求每個點到其他點的最近和最遠距離

 

題目分析：往左往右取最大最小

 

 

#include 
#include 
using namespace std;
int const MAX = 1e5 + 5;
int a[MAX];

int main()
{
    int n;
    scanf(%d, &n);
    for(int i = 0; i < n; i++)
        scanf(%d, &a[i]);
    printf(%d %d
, a[1] - a[0], a[n - 1] - a[0]);
    for(int i = 1; i < n - 1; i++)
        printf(%d %d
, min(a[i + 1] - a[i], a[i] - a[i - 1]), max(a[i] - a[0], a[n - 1] - a[i]));
    printf(%d %d
, a[n - 1] - a[n - 2], a[n - 1] - a[0]);
}

 

 

 

B. Berland National Library time limit per test：1 second memory limit per test：256 megabytes

Berland National Library has recently been built in the capital of Berland. In addition, in the library you can take any of the collected works of Berland leaders, the library has a reading room.

Today was the pilot launch of an automated reading room visitors' accounting system! The scanner of the system is installed at the entrance to the reading room. It records the events of the form reader entered room, reader left room. Every reader is assigned a registration number during the registration procedure at the library — it's a unique integer from 1 to 10⁶. Thus, the system logs events of two forms:

+ r_i — the reader with registration number r_i entered the room; - r_i — the reader with registration number r_i left the room.

The first launch of the system was a success, it functioned for some period of time, and, at the time of its launch and at the time of its shutdown, the reading room may already have visitors.

Significant funds of the budget of Berland have been spent on the design and installation of the system. Therefore, some of the citizens of the capital now demand to explain the need for this system and the benefits that its implementation will bring. Now, the developers of the system need to urgently come up with reasons for its existence.

Help the system developers to find the minimum possible capacity of the reading room (in visitors) using the log of the system available to you.

Input

The first line contains a positive integer n (1 ≤ n ≤ 100) — the number of records in the system log. Next follow n events from the system journal in the order in which the were made. Each event was written on a single line and looks as + r_i or - r_i, where r_i is an integer from 1 to 10⁶, the registration number of the visitor (that is, distinct visitors always have distinct registration numbers).

It is guaranteed that the log is not contradictory, that is, for every visitor the types of any of his two consecutive events are distinct. Before starting the system, and after stopping the room may possibly contain visitors.

Output

Print a single integer — the minimum possible capacity of the reading room.

Sample test(s) Input

6
+ 12001
- 12001
- 1
- 1200
+ 1
+ 7

Output

3

Input

2
- 1
- 2

Output

2

Input

2
+ 1
- 1

Output

1

Note

In the first sample test, the system log will ensure that at some point in the reading room were visitors with registration numbers 1, 1200 and 12001. More people were not in the room at the same time based on the log. Therefore, the answer to the test is 3.

 

題目大意：一共n個操作，+ i表示標號為i的人進會場，－i表示標號為i的人出會場，問會場的最小容量

 

題目分析：用個set模擬一下

 

 

#include 
#include 
#include 
using namespace std;
set  st;

int main()
{
    int n, ans = 0;;
    scanf(%d, &n);
    while(n --)
    {
        char s[2];
        int id;
        scanf(%s %d, s, &id);
        if(s[0] == '+') 
            st.insert(id);  //進去
        else
        {
            if(!st.count(id)) //本來就在裡面的出來
                ans ++;
            else
                st.erase(id);  //之前進去的出來
        }
        ans = max(ans, (int) st.size());
    }
    printf(%d
, ans);
}

 

 

 

 

C. Geometric Progression time limit per test：1 second memory limit per test：256 megabytes

Polycarp loves geometric progressions very much. Since he was only three years old, he loves only the progressions of length three. He also has a favorite integer k and a sequence a, consisting of n integers.

He wants to know how many subsequences of length three can be selected from a, so that they form a geometric progression with common ratio k.

A subsequence of length three is a combination of three such indexes i₁, i₂, i₃, that 1 ≤ i₁ < i₂ < i₃ ≤ n. That is, a subsequence of length three are such groups of three elements that are not necessarily consecutive in the sequence, but their indexes are strictly increasing.

A geometric progression with common ratio k is a sequence of numbers of the form b·k⁰, b·k¹, ..., b·k^r - 1.

Polycarp is only three years old, so he can not calculate this number himself. Help him to do it.

Input

The first line of the input contains two integers, n and k (1 ≤ n, k ≤ 2·10⁵), showing how many numbers Polycarp's sequence has and his favorite number.

The second line contains n integers a₁, a₂, ..., a_n ( - 10⁹ ≤ a_i ≤ 10⁹) — elements of the sequence.

Output

Output a single number — the number of ways to choose a subsequence of length three, such that it forms a geometric progression with a common ratio k.

Sample test(s) Input

5 2
1 1 2 2 4

Output

4

Input

3 1
1 1 1

Output

1

Input

10 3
1 2 6 2 3 6 9 18 3 9

Output

6

Note

In the first sample test the answer is four, as any of the two 1s can be chosen as the first element, the second element can be any of the 2s, and the third element of the subsequence must be equal to 4.

 

題目大意：n個數，問能找到多少組三個數，它們的下標嚴格遞增且公比為k

 

題目分析：ai那麼大，數組不夠，直接上map，fir表示中間那個數出現的次數，sec表示第一個數出現的次數，每次按公比k找滿足條件的數

 

 

#include 
#include

 

 

 

 

D. One-Dimensional Battle Ships time limit per test：1 second memory limit per test：256 megabytes

Alice and Bob love playing one-dimensional battle ships. They play on the field in the form of a line consisting of n square cells (that is, on a 1 × n table).

At the beginning of the game Alice puts k ships on the field without telling their positions to Bob. Each ship looks as a 1 × a rectangle (that is, it occupies a sequence of a consecutive squares of the field). The ships cannot intersect and even touch each other.

After that Bob makes a sequence of shots. He names cells of the field and Alice either says that the cell is empty (miss), or that the cell belongs to some ship (hit).

But here's the problem! Alice like to cheat. May be that is why she responds to each Bob's move with a miss.

Help Bob catch Alice cheating — find Bob's first move, such that after it you can be sure that Alice cheated.

Input

The first line of the input contains three integers: n, k and a (1 ≤ n, k, a ≤ 2·10⁵) — the size of the field, the number of the ships and the size of each ship. It is guaranteed that the n, k and a are such that you can put k ships of size a on the field, so that no two ships intersect or touch each other.

The second line contains integer m (1 ≤ m ≤ n) — the number of Bob's moves.

The third line contains m distinct integers x₁, x₂, ..., x_m, where x_i is the number of the cell where Bob made the i-th shot. The cells are numbered from left to right from 1 to n.

Output

Print a single integer — the number of such Bob's first move, after which you can be sure that Alice lied. Bob's moves are numbered from 1 to m in the order the were made. If the sought move doesn't exist, then print -1.

Sample test(s) Input

11 3 3
5
4 8 6 1 11

Output

3

Input

5 1 3
2
1 5

Output

-1

Input

5 1 3
1
3

Output

1

 

題目大意：在一條長度為n的線上放船，最多放k只船，每只船的長度為a，且任意兩只船不能重疊或者接觸對方，現在給出m條hit指令，每條指令表示攻擊線上xi的位置，問最少到第幾條指令能肯定會打到一個船，若都可能打不到則輸出－1

 

題目分析：因為不能接觸，所以一條船占用的最小長度實際為a + 1，注意在一端的情況，先求出實際最多可以放的船數，然後對於每個查詢的點，二分找到離它最近的兩個點，修改能放的船的數目，一旦數目小於k，則找到答案，因為這裡k是給定的最多能放的船數，如果小於這個值，說明一定有重復的地方出現

 

 

#include 
#include 
#include 
using namespace std;
set  s;
set  :: iterator it;

int main()
{
    int n, k, a;
    int ans = -1;
    scanf(%d %d %d, &n, &k, &a);
    int num = n / (a + 1);
    if(n % (a + 1) >= a)
        num ++;
    s.insert(0);
    s.insert(n + 1);
    int m;
    scanf(%d, &m);
    for(int i = 1; i <= m; i++)
    {
        int x;
        scanf(%d, &x);
        s.insert(x);
        it = s.lower_bound(x);
        it --;
        int l = *it;
        it = s.upper_bound(x);
        int r = *it;
        num -= (r - l) / (a + 1);
        num += (x - l) / (a + 1);
        num += (r - x) / (a + 1);
        if(num < k)
        {
            ans = i;
            break;
        }
    }
    printf(%d
, ans);
}