Codeforces Round #388 (Div. 2)

A. Bachgold Problem
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Bachgold problem is very easy to formulate. Given a positive integer n represent it as a sum of maximum possible number of prime numbers. One can prove that such representation exists for any integer greater than 1.
Recall that integer k is called prime if it is greater than 1 and has exactly two positive integer divisors — 1 and k.
Input
The only line of the input contains a single integer n (2 ≤ n ≤ 100 000).
Output
The first line of the output contains a single integer k — maximum possible number of primes in representation.
The second line should contain k primes with their sum equal to n. You can print them in any order. If there are several optimal solution, print any of them.
Examples
input
5
output
2
2 3
input
6
output
3
2 2 2

题意:给一个数n,要求最多的素数个数,使得这些素数之和等于n.
比如5 = 2 + 3(数字可以重复)。
要想素数个数最多,每个素数的值就应该越小,最小的素数是2,其次是3.
我们发现所有的偶数都是2的倍数,因此所有的偶数都可以写为数个2相加的形式。大于1的奇数在减掉一个3之后都会变成偶数。
因此,我们可以先判定这个数的奇偶性,再对其进行处理。

官方题解:

We need represent integer number N (1 < N) as a sum of maximum possible number of prime numbers, they don’t have to be different.
If N is even number, we can represent it as sum of only 2 - minimal prime number. It is minimal prime number, so number of primes in sum is maximal in this case.
If N is odd number, we can use representing of N - 1 as sum with only 2 and replace last summand from 2 to 3.
Using of any prime P > 3 as summand is not optimal, because it can be replaced by more than one 2 and 3.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 100000+5;

int n;
vector<int> ans;

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

    cin >> n;

    int k = 0;
    ans.clear();
    if (n % 2 == 1) {//n是奇数;
        n -= 3;
        ++k;
        ans.push_back(3);
    }

    while (n) {
        n -= 2;
        ++k;
        ans.push_back(2);
    }

    cout << k << "\n";
    int cnt = 0;
    for (auto const &elem : ans) {
        if (cnt > 0) cout << " ";
        cout << elem;
        ++cnt;
    }

    cout << endl;
    return 0;
}

B. Parallelogram is Back
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Long time ago Alex created an interesting problem about parallelogram. The input data for this problem contained four integer points on the Cartesian plane, that defined the set of vertices of some non-degenerate (positive area) parallelogram. Points not necessary were given in the order of clockwise or counterclockwise traversal.
Alex had very nice test for this problem, but is somehow happened that the last line of the input was lost and now he has only three out of four points of the original parallelogram. He remembers that test was so good that he asks you to restore it given only these three points.
Input
The input consists of three lines, each containing a pair of integer coordinates xi and yi ( - 1000 ≤ xi, yi ≤ 1000). It's guaranteed that these three points do not lie on the same line and no two of them coincide.
Output
First print integer k — the number of ways to add one new integer point such that the obtained set defines some parallelogram of positive area. There is no requirement for the points to be arranged in any special order (like traversal), they just define the set of vertices.
Then print k lines, each containing a pair of integer — possible coordinates of the fourth point.
Example
input
0 0
1 0
0 1
output
3
1 -1
-1 1
1 1
Note
If you need clarification of what parallelogram is, please check Wikipedia page:
https://en.wikipedia.org/wiki/Parallelogram

题意:已知一个平行四边形三个顶点的坐标,求第四个顶点有多少种可能性且每种可能性的坐标。

这是从网上搜到的关于此题的一种做法:

总结求平行四边形第四个顶点坐标的定理
任意两个顶点横坐标之和减去第三个顶点横坐标的差就是第四个顶点的横坐标;
任意两个顶点纵坐标之和减去第三个顶点纵坐标的差就是第四个顶点的纵坐标。
符合要求的点共有3个。

官方题解:

Denote the input points as A, B, C, and the point we need to find as D.
Consider the case when the segments AD and BC are the diagonals of parallelogram. Vector AD is equal to the sum of two vectors AB + BD = AC + CD. As in the parallelogram the opposite sides are equal and parallel, BD = AC, AB = CD, and we can conclude that AD = AB + AC. So, the coordinates of the point D can be calculated as A + AB + AC = (Ax + Bx - Ax + Cx - Ax, Ay + By - Ay + Cy - Ay) = (Bx + Cx - Ax, By + Cy - Ay).
The cases where the diagonals are BD and AC, CD and AB are processed in the same way.
Prove that all three given points are different. Let's suppose it's wrong. Without losing of generality suppose that the points got in cases AD and BD are equal.
Consider the system of two equations for the equality of these points:
Bx + Cx - Ax = Ax + Cx - Bx
By + Cy - Ay = Ay + Cy - By
We can see that in can be simplified as
Ax = Bx
Ay = By
And we got a contradiction, as all the points A, B, C are distinct.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

struct node {
    int x, y;
} a[4];

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

    for (int i = 0;i < 3;++i) {
        cin >> a[i].x >> a[i].y;
    }

    cout << 3 << "\n";

    int ansx1 = a[0].x + a[1].x - a[2].x;
    int ansy1 = a[0].y + a[1].y - a[2].y;

    int ansx2 = a[1].x + a[2].x - a[0].x;
    int ansy2 = a[1].y + a[2].y - a[0].y;

    int ansx3 = a[0].x + a[2].x - a[1].x;
    int ansy3 = a[0].y + a[2].y - a[1].y;

    cout << ansx1 << " " << ansy1 << "\n";
    cout << ansx2 << " " << ansy2 << "\n";
    cout << ansx3 << " " << ansy3 << endl;  
    return 0;
}

C. Voting
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
There are n employees in Alternative Cake Manufacturing (ACM). They are now voting on some very important question and the leading world media are trying to predict the outcome of the vote.
Each of the employees belongs to one of two fractions: depublicans or remocrats, and these two fractions have opposite opinions on what should be the outcome of the vote. The voting procedure is rather complicated:
Each of n employees makes a statement. They make statements one by one starting from employees 1 and finishing with employee n. If at the moment when it's time for the i-th employee to make a statement he no longer has the right to vote, he just skips his turn (and no longer takes part in this voting).
When employee makes a statement, he can do nothing or declare that one of the other employees no longer has a right to vote. It's allowed to deny from voting people who already made the statement or people who are only waiting to do so. If someone is denied from voting he no longer participates in the voting till the very end.
When all employees are done with their statements, the procedure repeats: again, each employees starting from 1 and finishing with n who are still eligible to vote make their statements.
The process repeats until there is only one employee eligible to vote remaining and he determines the outcome of the whole voting. Of course, he votes for the decision suitable for his fraction.
You know the order employees are going to vote and that they behave optimal (and they also know the order and who belongs to which fraction). Predict the outcome of the vote.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of employees.
The next line contains n characters. The i-th character is 'D' if the i-th employee is from depublicans fraction or 'R' if he is from remocrats.
Output
Print 'D' if the outcome of the vote will be suitable for depublicans and 'R' if remocrats will win.
Examples
input
5
DDRRR
output
D
input
6
DDRRRR
output
R
Note
Consider one of the voting scenarios for the first sample:
Employee 1 denies employee 5 to vote.
Employee 2 denies employee 3 to vote.
Employee 3 has no right to vote and skips his turn (he was denied by employee 2).
Employee 4 denies employee 2 to vote.
Employee 5 has no right to vote and skips his turn (he was denied by employee 1).
Employee 1 denies employee 4.
Only employee 1 now has the right to vote so the voting ends with the victory of depublicans.

题意:有两个派别的人要对某事进行选举,'D'代表这个人属于D派别,'R'代表这个人属于R派别。每个人都按顺序上台。某个人上台后可以宣布底下某一个人无权参加选举,之后轮到那个人时就只能跳过;也可以什么都不做。问最后哪个派别的人会获胜(另一个派别没有人有权利参加选举)。

由于是按顺序进行的,所以靠前的人有优势决定别人是否有选举的权利。每个人都希望自己的派别最终获胜,肯定会让对方派别的某个人没有选举权利,少掉一个对手。但是这道题要考虑最优的情况。
比如:DRDR,如果第一个D选择让最后一个R没有选举权利,那么第一个R可以让它之后的D没有选举权利,因此最后就只剩一个D。
但如果第一个D让它之后的R没有选举权利,那么之后的D就可以得到保护,并且可以再让它之后的R没有选举权利,从而又增加了一次让对手少掉一人的机会。
因此这道题的方法就是,当轮到某人时让它之后最靠近它的对手失去选举权利。
可以用两个队列模拟D和R派别人数的变化。

官方题解:

We will emulate the process with two queues. Let’s store in the first queue the moments of time when D-people will vote, and in the second queue - the moments of time of R-people. For every man where will be only one element in the queue.
Now compare the first elements in the queues. The man whose moment of time is less votes first. It’s obvious that it’s always profitable to vote against the first opponent. So we will remove the first element from the opponent’s queue, and move ourselves to the back of our queue, increasing the current time by n - next time this man will vote after n turns.
When one of the queues becomes empty, the corresponding party loses.

#include <iostream>
#include <cstring>
#include <vector>
#include <string>
#include <queue>
using namespace std;

queue<int> qd;
queue<int> qr;

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

    int n;
    cin >> n;
    string str;
    cin >> str;

    for (int i = 0;i < str.length();++i) {
        if (str[i] == 'D') qd.push(i);
        else qr.push(i);
    }

    int i = 0;
    while (!qd.empty() && !qr.empty()) {
        int fd = qd.front();
        int fr = qr.front();

        if (fd < fr) {//小的先做决策;
            qr.pop();//对方下一个被淘汰;
            qd.pop();//等待下一轮;
            qd.push(fd+n);
        }
        else {
            qd.pop();
            qr.pop();
            qr.push(fr+n);
        }
    }

    if (!qd.empty()) cout << 'D' << endl;
    else cout << 'R' << endl;
    return 0;
}

D. Leaving Auction
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
There are n people taking part in auction today. The rules of auction are classical. There were n bids made, though it's not guaranteed they were from different people. It might happen that some people made no bids at all.
Each bid is define by two integers (ai, bi), where ai is the index of the person, who made this bid and bi is its size. Bids are given in chronological order, meaning bi < bi + 1 for all i < n. Moreover, participant never makes two bids in a row (no one updates his own bid), i.e. ai ≠ ai + 1 for all i < n.
Now you are curious with the following question: who (and which bid) will win the auction if some participants were absent? Consider that if someone was absent, all his bids are just removed and no new bids are added.
Note, that if during this imaginary exclusion of some participants it happens that some of the remaining participants makes a bid twice (or more times) in a row, only first of these bids is counted. For better understanding take a look at the samples.
You have several questions in your mind, compute the answer for each of them.
Input
The first line of the input contains an integer n (1 ≤ n ≤ 200 000) — the number of participants and bids.
Each of the following n lines contains two integers ai and bi (1 ≤ ai ≤ n, 1 ≤ bi ≤ 10^9, bi < bi + 1) — the number of participant who made the i-th bid and the size of this bid.
Next line contains an integer q (1 ≤ q ≤ 200 000) — the number of question you have in mind.
Each of next q lines contains an integer k (1 ≤ k ≤ n), followed by k integers lj (1 ≤ lj ≤ n) — the number of people who are not coming in this question and their indices. It is guarenteed that lj values are different for a single question.
It's guaranteed that the sum of k over all question won't exceed 200 000.
Output
For each question print two integer — the index of the winner and the size of the winning bid. If there is no winner (there are no remaining bids at all), print two zeroes.
Examples
input
6
1 10
2 100
3 1000
1 10000
2 100000
3 1000000
3
1 3
2 2 3
2 1 2
output
2 100000
1 10
3 1000
input
3
1 10
2 100
1 1000
2
2 1 2
2 2 3
output
0 0
1 10
Note
Consider the first sample:
In the first question participant number 3 is absent so the sequence of bids looks as follows:
1 10
2 100
1 10 000
2 100 000
Participant number 2 wins with the bid 100 000.
In the second question participants 2 and 3 are absent, so the sequence of bids looks:
1 10
1 10 000
The winner is, of course, participant number 1 but the winning bid is 10 instead of 10 000 as no one will ever increase his own bid (in this problem).
In the third question participants 1 and 2 are absent and the sequence is:
3 1 000
3 1 000 000
The winner is participant 3 with the bid 1 000.

题意:有数个人(人数<=n)在拍卖场竞价,一共有n次喊价(可能有些人没有参与),每次给出喊价人的编号以及他/她给出的价钱(价格只能一次比一次高)。之后会有q次询问,每次询问给一个数字,表明有多少个人被除去,在剩余的人中求出是谁获得了胜利,并求出获胜的最小金额。

这道题有几种情况:
最后所有人都被除去了,那么最终结果就是0 0.
最后只剩下一个人,这个人肯定就是胜利者,而他/她之前报的最小的金额就是最终的结果。
最后多于1个人,那么就要找到当前最大金额的竞价人,将他/她之前的报价同第二大的最高报价作比较,找出刚刚大于此报价的最小价格。

官方题解:

For every man at the auction we will save two values: his maximum bid and the list of all his bids. Then save all men in the set sorted by the maximal bid.
Now, when the query comes, we will remove from the set all men who left the auction, then answer the query, and then add the men back. The total number of deletions and insertions will not exceed 200000.
How to answer the query. Now our set contains only men who has not left.
If the set is empty, the answer is 0 0. Otherwise, the maximal man in the set is the winner. Now we have to determine the winning bid. Let’s look at the second maximal man in the set.
If it doesn’t exist, the winner takes part solo and wins with his minimal bid.
Otherwise he should bid the minimal value that is greater than the maximal bid of the second man in the set. This is where we need a list of bids of the first maximal man. We can apply binary search and find the maximal bid of the second man there.

这道题开始我不太明白,后来看了别人的代码后才稍稍理解。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
using namespace std;
const int N = 200000+5;

int n;
set<pair<int, int> > pos;//竞价人的编号和当前该竞价人给出的最大竞价价格(排序);
vector<int> lst[N];//每个人的所有竞价价格(从小到大);
int del[N];//要去掉的竞价人的编号;
int mx[N];//每个竞价人给出的最大竞价额;
bool vis[N];//当前哪些编号的竞价人参与了竞价, 有人可能没参加;

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

    cin >> n;
    int a, b;
    for (int i = 1;i <= n;++i) {
        cin >> a >> b;
        lst[a].push_back(b);
        vis[a] = true;
        mx[a] = max(b, mx[a]);
    }

    for (int i = 1;i <= n;++i) {
        if (vis[i]) {
            pos.insert({mx[i], i});//价格在前, 之后set会自动对价格排序;
        }
    }

    int q;
    cin >> q;
    for (int i = 1;i <= q;++i) {
        int num;//每次要去掉多少人;
        cin >> num;
        for (int j = 1;j <= num;++j) {
            cin >> del[j];
            if (vis[del[j]]) {
                pos.erase({mx[del[j]], del[j]});
            }
        }

        if (pos.size() == 0) {//全部被去掉了;
            cout << 0 << " " << 0 << endl;
        }
        else if (pos.size() == 1) {//仅剩一个人;
            cout << (pos.begin())->second << " " << lst[pos.begin()->second].at(0) << endl;//取最小值;
        }
        else {
            auto it1 = pos.end();
            auto it2 = pos.end();

            --it1;
            --it1;//第二大竞价人;
            --it2;//第一大竞价人;
            int tmpnum = it1->first;//第二大竞价人的价格;
            int tmppos = it2->second;//第一大竞价人的编号;

            auto it = upper_bound(lst[tmppos].begin(), lst[tmppos].end(), tmpnum);//找出第一大竞价人所有报价里面刚好大于第二大竞价人的价格;
            cout << tmppos << " " << *it << endl;
        }

        for (int j = 1;j <= num;++j) {//数据还原;
            if (vis[del[j]]) {
                pos.insert({mx[del[j]], del[j]});
            }
        }
    }
    return 0;
}

还有一道还没看,以后有时间的话在做一做。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,884评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,347评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,435评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,509评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,611评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,837评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,987评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,730评论 0 267
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,194评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,525评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,664评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,334评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,944评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,764评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,997评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,389评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,554评论 2 349

推荐阅读更多精彩内容