CF879A - Borya’s Diagnosis

题目描述

It seems that Borya is seriously sick. He is going visit n doctors to find out the exact diagnosis. Each of the doctors needs the information about all previous visits, so Borya has to visit them in the prescribed order (i.e. Borya should first visit doctor 1, then doctor 2, then doctor 3 and so on). Borya will get the information about his health from the last doctor.

Doctors have a strange working schedule. The doctor i goes to work on the si-th day and works every di day. So, he works on days si, si + di, si + 2di, ….

The doctor’s appointment takes quite a long time, so Borya can not see more than one doctor per day. What is the minimum time he needs to visit all doctors?

输入

First line contains an integer n — number of doctors (1 ≤ n ≤ 1000).

Next n lines contain two numbers si and di (1 ≤ si, di ≤ 1000).

输出

Output a single integer — the minimum day at which Borya can visit the last doctor.

样例

Input

1
2
3
4
3
2 2
1 2
2 2

Output

1
4

Input

1
2
3
2
10 1
6 5

Output

1
11

注意

In the first sample case, Borya can visit all doctors on days 2, 3 and 4.

In the second sample case, Borya can visit all doctors on days 10 and 11.

解题思路

😋这题是简单的模拟水题,Borya需要去按照指定顺序看医生。每天最多看一位医生。

医生并不是每天上班,已知某个医生第*si天上班,并且每di*天上一次班。

求这个人看医生所需的天数

题意很简单,理解清楚题意后直接模拟就行。

刚开始理解错题意了,以为需要用贪心思想给医生安排最优时间,题目说的是按给出的指定顺序看医生,这就使题目难度大大降低。

下面的题解定义了Doc结构体用来保存医生信息,最后才发现题目其实很简单,也可以直接按给出顺序输出,这样可以节省内存空间。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>  
#include <algorithm>

using namespace std;

struct Doc //定义Doc结构体,保存医生信息。
{
int s; //第s天医生上班
int d; //每隔d天上班
};

int main()
{
int n = 0; //医生数量
int days = 0; //即答案,所求的天数

cin >> n;

Doc doc[1000] = { 0 };

for(int i = 0; i < n; i++)
{
cin >> doc[i].s >> doc[i].d;
}

days = doc[0].s; //先让days为第一个医生第一次上班的时间
for (int i = 0; i < n; i++)
{
while (days >= doc[i].s) //当前医生就诊日期小于我们当前的时间,计算这个医生的下一个就诊日期
{
if (i == 0) break; //第一个医生时间即days的初始值,跳过
doc[i].s += doc[i].d; //就诊日期推到下一个(+d)
}

days = doc[i].s; //当前日期为这个医生的就诊日期
}

cout << days << endl;

return 0;
}

English单词积累

diagnosis—诊断; (问题原因的)判断;

prescribed order—规定的顺序

CF879B - Table Tennis

题目描述

n people are standing in a line to play table tennis. At first, the first two players in the line play a game. Then the loser goes to the end of the line, and the winner plays with the next person from the line, and so on. They play until someone wins k games in a row. This player becomes the winner.

For each of the participants, you know the power to play table tennis, and for all players these values are different. In a game the player with greater power always wins. Determine who will be the winner.

输入

The first line contains two integers: n and k (2 ≤ n ≤ 500, 2 ≤ k ≤ 10^12^) — the number of people and the number of wins.

The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ n) — powers of the player. It’s guaranteed that this line contains a valid permutation, i.e. all ai are distinct.

输出

Output a single integer — power of the winner.

样例

Input

1
2
2 2
1 2

Output

1
2 

Input

1
2
4 2
3 1 2 4

Output

1
3 

Input

1
2
6 2
6 5 3 1 2 4

Output

1
6 

Input

1
2
2 10000000000
2 1

Output

1
2

注意

Games in the second sample:

3 plays with 1. 3 wins. 1 goes to the end of the line.

3 plays with 2. 3 wins. He wins twice in a row. He becomes the winner.

解题思路

😁题意很简单,也是一道模拟水题。有n个人进行网球比赛,求谁首先赢得k场比赛。

网球规则:从第一个人开始,他首先和第二个人比赛,输的到队伍末尾,赢得继续和下一位进行比赛。

判断输赢的规则:题目第二行给出每个人的power值,power值大的赢得比赛。

理解清楚题意后,显示可知,当所有人都参与了比赛(即完成一轮比赛)。

这时,有两种情况:

  1. 在比赛途中,有人已经赢得k场比赛,这时答案出来了,直接break跳出,不需要继续进行比赛。

  2. 进行一轮比赛后,依旧没有人赢得k场比赛。这时,赢得比赛的人是场上power最大的。继续进行比赛,只有这个人会赢,所以他会首先赢得k场比赛。

总之,我们循环进行PK,如果有人满足条件就break跳出,如果没人就循环一次后跳出。最后输出当前赢家。

中途发现数据很大,按照模拟会超时,所以改了代码,所幸不需重写。起初没有想清楚输出的内容,导致WA了3次才AC。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>  

using namespace std;

struct Player //定义选手结构体
{
int power; //power值,power高的人赢得比赛
long long cnt; //赢得比赛的次数

};

int main()
{
int n = 0; //参加比赛的选手人数
long long k = 0; //题目所给条件:赢得比赛次数
Player player[500] = { 0 };

cin >> n >> k;

for (int i = 0; i < n; i++)
{
cin >> player[i].power;
}

int now = 1; //当前选手
int nowWin = 0; //当前赢得比赛的选手
while (player[nowWin].cnt < k) //每进行一次比赛都判断是否有人满足了题目条件。
{
if (now > n - 1) //判断是否完成了一轮比赛
{
break;
}


if (player[nowWin].power > player[now].power) //进行PK
{
player[nowWin].cnt++;
}
else
{
nowWin = now;
player[nowWin].cnt++;
}

now++; //下一位选手继续PK
}

cout << player[nowWin].power << endl; //输出当前赢得比赛的选手

return 0;
}

English单词积累

permutation—排列(方式); 组合(方式); 置换;

CF879C - Short Program

题目描述

Petya learned a new programming language CALPAS. A program in this language always takes one non-negative integer and returns one non-negative integer as well.

In the language, there are only three commands: apply a bitwise operation AND, OR or XOR with a given constant to the current integer. A program can contain an arbitrary sequence of these operations with arbitrary constants from 0 to 1023. When the program is run, all operations are applied (in the given order) to the argument and in the end the result integer is returned.

Petya wrote a program in this language, but it turned out to be too long. Write a program in CALPAS that does the same thing as the Petya’s program, and consists of no more than 5 lines. Your program should return the same integer as Petya’s program for all arguments from 0 to 1023.

输入

The first line contains an integer n (1 ≤ n ≤ 5·10^5^) — the number of lines.

Next n lines contain commands. A command consists of a character that represents the operation (“&”, “|” or “^” for AND, OR or XOR respectively), and the constant xi (0 ≤ xi ≤ 1023).

输出

Output an integer k (0 ≤ k ≤ 5) — the length of your program.

Next k lines must contain commands in the same format as in the input.

样例

Input

1
2
3
4
3
| 3
^ 2
| 1

Output

1
2
3
2
| 3
^ 2

Input

1
2
3
4
3
& 1
& 3
& 5

Output

1
2
1
& 1

Input

1
2
3
4
3
^ 1
^ 2
^ 3

Output

1
0

注意

You can read about bitwise operations in https://en.wikipedia.org/wiki/Bitwise_operation.

Second sample:

Let x be an input of the Petya’s program. It’s output is ((x&1)&3)&5 = x&(1&3&5) = x&1. So these two programs always give the same outputs.

解题思路

😅题意不难理解,把某个0-1023的常数按照输入给出的顺序执行位运算。要求把运算过程精简到5次运算以内。

这种题没有想到什么思路。赛后通过研究题解发现:

对每一个二进制位进行讨论:

0->0 1->1 不运算

0->1 1->0 xor1

0->1 1->1 or1

0->0 1->0 &0

因此,我们可以使用0(00 0000 00002)和1023(11 1111 11112)作为基数,判断每位二进制的变化。

根据题目所给步骤对这两个基数进行位运算,最后根据两个基数各个位的变化情况判断需要进行何种运算。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>  
#include <algorithm>

using namespace std;

int main()
{
int n;

char op;
int num;

int a = 0; //基数00 0000 0000
int b = 1023; //基数11 1111 1111

cin >> n;

for (int i = 0; i < n; i++)
{
cin >> op >> num;
if (op == '|') //进行按位或运算
{
a |= num;
b |= num;
}

if (op == '^') //进行按位异或运算
{
a ^= num;
b ^= num;
}

if (op == '&') //进行按位与运算
{
a &= num;
b &= num;
}
}

//上面的代码按照题目模拟进行了一系列的位运算。
//运算后,下面的代码根据每位二进制的变化确定运算。
/*
0->0 1->1 不运算
0->1 1->0 xor1
0->1 1->1 or1
0->0 1->0 &0
*/

int AND = 1023, OR = 0, XOR = 0;
for (int i = 0; i < 10; i++) //从第0位到第9位 一共10位 判断每位二进制变化 确定进行的运算
{
int A = (a >> i) & 1; //取第i位二进制
int B = (b >> i) & 1; //取第i位二进制

if (A && B) OR |= (1 << i); //or1(将OR的第i位设置为1)
if (A && !B) XOR |= (1 << i); //xor1(将XOR的第i位设置为1)
if (!A && !B) AND -= (1 << i); //and0(将AND的第i位设置为0)
}

cout << 3 << endl;
cout << "& " << AND << endl;
cout << "| " << OR << endl;
cout << "^ " << XOR << endl;
}

English单词积累

non-negative—非负的; 正的

bitwise—位元; 按位; 逐位; 位运算; 运算;

constant—连续发生的; 不断的; 重复的; 不变的; 固定的; 恒定的;

arbitrary—任意的; 武断的; 随心所欲的; 专横的; 专制的;

CF879D - Teams Formation

CF879E - Tournament