A – CF651B Beautiful Paintings

1000ms 262144K

Description:

There are n pictures delivered for the new exhibition. The i-th painting has beauty a_i. We know that a visitor becomes happy every time he passes from a painting to a more beautiful one.

We are allowed to arranged pictures in any order. What is the maximum possible number of times the visitor may become happy while passing all pictures from first to last? In other words, we are allowed to rearrange elements of a in any order. What is the maximum possible number of indices i (1 ≤ i ≤ n - 1), such that a_{i+1} > a_i.

Input:

The first line of the input contains integer n (1 ≤ n ≤ 1000) — the number of painting.

The second line contains the sequence a_1, a_2, …, a_n (1 ≤ a_i ≤ 1000), where a_i means the beauty of the i-th painting.

Output:

Print one integer — the maximum possible number of neighbouring pairs, such that a_{i+1} > a_i, after the optimal rearrangement.

Sample Input:

520 30 10 50 40

Sample Output:

4

Sample Input:

4200 100 100 200

Sample Output:

2

Note:

In the first sample, the optimal order is: 10, 20, 30, 40, 50.

In the second sample, the optimal order is: 100, 200, 100, 200.

分析:

题目大意是说将一个数组排序,使得a_{i+1} > a_i的次数最多。

规律是用总长度减去出现单一值的最多出现次数。

题解:

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
int a[1005];
int main(void) {
    int n;
    scanf("%d", &n);
    for(int i=0;i<n;i++) {
        int x;
        scanf("%d", &x);
        a[x]++;
    }
    printf("%d\n", n - *max_element(a, a+1001));
    return 0;
}

B – CF758A Holiday Of Equality

1000ms 262144K

Description:

In Berland it is the holiday of equality. In honor of the holiday the king decided to equalize the welfare of all citizens in Berland by the expense of the state treasury.

Totally in Berland there are n citizens, the welfare of each of them is estimated as the integer in a_i burles (burle is the currency in Berland).

You are the royal treasurer, which needs to count the minimum charges of the kingdom on the king’s present. The king can only give money, he hasn’t a power to take away them.

Input:

The first line contains the integer n (1 ≤ n ≤ 100) — the number of citizens in the kingdom.

The second line contains n integers a_1, a_2, …, a_n, where a_i (0 ≤ a_i ≤ 106) — the welfare of the i-th citizen.

Output:

In the only line print the integer S — the minimum number of burles which are had to spend.

Sample Input:

50 1 2 3 4

Sample Output:

10

Sample Input:

51 1 0 1 1

Sample Output:

1

Sample Input:

31 3 1

Sample Output:

4

Sample Input:

112

Sample Output:

0

Note:

In the first example if we add to the first citizen 4 burles, to the second 3, to the third 2 and to the fourth 1, then the welfare of all citizens will equal 4.

In the second example it is enough to give one burle to the third citizen.

In the third example it is necessary to give two burles to the first and the third citizens to make the welfare of citizens equal 3.

In the fourth example it is possible to give nothing to everyone because all citizens have 12 burles.

分析:

给定一个数组,通过扩大某些数的大小使得数组每个数都相等。

只需求出最大值,减去每个数然后求和即可。

题解:

#include<iostream>
using namespace std;
int m,s,n,a;
int main()
{
    cin>>n;
    for(int x=1;x<=n;x++)cin>>a,m=max(m,a),s+=a;
    cout<<n*m-s;
    return 0;
}

C – CF935A Fafa and his Company

1000ms 262144K

Description:

Fafa owns a company that works on huge projects. There are n employees in Fafa’s company. Whenever the company has a new project to start working on, Fafa has to divide the tasks of this project among all the employees.

Fafa finds doing this every time is very tiring for him. So, he decided to choose the best l employees in his company as team leaders. Whenever there is a new project, Fafa will divide the tasks among only the team leaders and each team leader will be responsible of some positive number of employees to give them the tasks. To make this process fair for the team leaders, each one of them should be responsible for the same number of employees. Moreover, every employee, who is not a team leader, has to be under the responsibility of exactly one team leader, and no team leader is responsible for another team leader.

Given the number of employees n, find in how many ways Fafa could choose the number of team leaders l in such a way that it is possible to divide employees between them evenly.

Input:

The input consists of a single line containing a positive integer n (2 ≤ n ≤ 105) — the number of employees in Fafa’s company.

Output:

Print a single integer representing the answer to the problem.

Sample Input:

2

Sample Output:

1

Sample Input:

10

Sample Output:

3

Note:

In the second sample Fafa has 3 ways:

  • choose only 1 employee as a team leader with 9 employees under his responsibility.
  • choose 2 employees as team leaders with 4 employees under the responsibility of each of them.
  • choose 5 employees as team leaders with 1 employee under the responsibility of each of them.

分析:

暴力判断总员工数能不能被老大数整除即可。

题解:

#include<cstdio>
using namespace std;
int main(){
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        if(n%i==0) ans++;
    }
    printf("%d",ans);
    return 0;
}

D – POJ1835 宇航员

2000ms 30000K

Description:

问题描述:

  宇航员在太空中迷失了方向,在他的起始位置现在建立一个虚拟xyz坐标系,称为绝对坐标系,宇航员正面的方向为x轴正方向,头顶方向为z轴正方向,则宇航员的初始状态如下图所示:

img

现对六个方向分别标号,x,y,z正方向分别为0,1,2,负方向分别为3,4,5;称它们为绝对方向。宇航员在宇宙中只沿着与绝对坐标系xyz轴平行的方向行走,但是他不知道自己当前绝对坐标和自己面向的绝对方向。

任务描述:

  请根据宇航员对自己在相对方向上移动的描述确定宇航员最终的绝对坐标和面向的绝对方向。对在相对方向上移动的描述及意义如下:

forward x  向前走x米。

back x 先转向后,再走x米。

left x 先转向左,再走x米。

right x 先转向右,再走x米。

up x 先面向上,再走x米。

down x 先面向下,再走x米。

其中向上和向下如下图所示:

img

Input:

第一行一个正整数m,表示测试数据的组数。每组测试数据第一行是一个正整数n(1<=n<=10000)表示宇航员行走的次数,下面n行每行输入一次相对行走,格式如上所述,其中( 1 <= x <= 10000 为正整数)。

Output:

对于每组输入数据输出一行,x y z p, 中间用空格隔开,x y z是宇航员的位置的绝对坐标,p是宇航员面向的绝对方向编号(0<=p <=5)。

Sample Input:

1
6
left 10
right 11
up 12
down 13
forward 14
back 15

Sample Output:

23 -10 12 3

分析:

这一题出的还是蛮巧妙的。训练的时候估算了一下,大概是几百行的代码量,就没有动手去写。

实际上只需要二十几行就可以完成,先确定宇航员的方向,然后再确定宇航员走的步数即可。

题解:

#include<cstdio>
char s[10];
int main(){
    int t, n;
    int x, y, z, face, left, head, temp, move;
    scanf("%d", &t);
    while (t--){
        scanf("%d", &n);
        x = y = z = 0;
        face = 0, left = 4, head = 2;
        while (n--){
            scanf("%s %d", s, &move);
            if (s[0] == 'b')  face = (face + 3) % 6, left = (left + 3) % 6;
            else if (s[0] == 'l')  temp = face, face = left, left = (temp + 3) % 6;
            else if (s[0] == 'r')  temp = left, left = face, face = (temp + 3) % 6;
            else if (s[0] == 'u')  temp = face, face = head, head = (temp + 3) % 6;
            else if (s[0] == 'd')  temp = head, head = face, face = (temp + 3) % 6;
            if (face == 0)  x += move;
            else if (face == 1)  y += move;
            else if (face == 2)  z += move;
            else if (face == 3)  x -= move;
            else if (face == 4)  y -= move;
            else  z -= move;
        }
        printf("%d %d %d %d\n", x, y, z, face);
    }
    return 0;
}

E – CF1060A Phone Numbers

2000ms 524288K

Description:

Let’s call a string a phone number if it has length 11 and fits the pattern “8xxxxxxxxxx”, where each “x” is replaced by a digit.

For example, “80123456789” and “80000000000” are phone numbers, while “8012345678” and “79000000000” are not.

You have nn cards with digits, and you want to use them to make as many phone numbers as possible. Each card must be used in at most one phone number, and you don’t have to use all cards. The phone numbers do not necessarily have to be distinct.

Input:

The first line contains an integer nn — the number of cards with digits that you have (1≤n≤1001≤n≤100).

The second line contains a string of nn digits (characters “0”, “1”, …, “9”) s1,s2,…,sns1,s2,…,sn. The string will not contain any other characters, such as leading or trailing spaces.

Output:

If at least one phone number can be made from these cards, output the maximum number of phone numbers that can be made. Otherwise, output 0.

Sample Input:

1100000000008

Sample Output:

1

Sample Input:

220011223344556677889988

Sample Output:

2

Sample Input:

1131415926535

Sample Output:

0

Note:

In the first example, one phone number, “8000000000”, can be made from these cards.

In the second example, you can make two phone numbers from the cards, for example, “80123456789” and “80123456789”.

In the third example you can’t make any phone number from the given cards.

分析:

给定一些数字,问最多能生成多少个电话号码。电话号码要满足以8开头、11位数两个特征。

只需要输出8的个数和总数字数量除以11中小的那个即可。

题解:

#include<cstdio>
#include<iostream>
using namespace std;
int main(){
    int count=0;
    int t;
    char temp;
    cin >> t;
    for(int i = 0; i < t; i++){
        cin >> temp;
        if(temp=='8'){
            count++;
        }
    }
    int tmp = t / 11;
    if(tmp > count){
        printf("%d", count);
    }else{
        printf("%d", tmp);
    }
    return 0;
}

F – CF1057B DDoS

2000ms 262144K

Description:

We get more and more news about DDoS-attacks of popular websites.

Arseny is an admin and he thinks that a website is under a DDoS-attack if the total number of requests for a some period of time exceeds 100⋅t100⋅t, where tt — the number of seconds in this time segment.

Arseny knows statistics on the number of requests per second since the server is booted. He knows the sequence r1,r2,…,rnr1,r2,…,rn, where riri — the number of requests in the ii-th second after boot.

Determine the length of the longest continuous period of time, which Arseny considers to be a DDoS-attack. A seeking time period should not go beyond the boundaries of the segment [1,n][1,n].

Input:

The first line contains nn (1≤n≤50001≤n≤5000) — number of seconds since server has been booted. The second line contains sequence of integers r1,r2,…,rnr1,r2,…,rn (0≤ri≤50000≤ri≤5000), riri — number of requests in the ii-th second.

Output:

Print the only integer number — the length of the longest time period which is considered to be a DDoS-attack by Arseny. If it doesn’t exist print 0.

Sample Input:

5100 200 1 1 1

Sample Output:

3

Sample Input:

51 2 3 4 5

Sample Output:

0

Sample Input:

2101 99

Sample Output:

1

分析:

考的是前缀和。

题解:

#include<iostream>
using namespace std;
int n,maxnn=0,maxmm=0;
int a[5050],s[5050];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int t;cin>>t;
        a[i]=t;
        s[i]=s[i-1]+t;
    }
    for(int i=n;i>=1;i--){
        for(int j=0;j<i;j++){
            if((s[i]-s[j])>(100*(i-j))&&i-j>maxnn){
                maxnn=i-j;
                break;
            }
        }
    }
    cout<<maxnn<<endl;
    return 0;
}

G – CF908A New Year and Counting Cards

1000ms 262144K

Description:

Your friend has n cards.

You know that each card has a lowercase English letter on one side and a digit on the other.

Currently, your friend has laid out the cards on a table so only one side of each card is visible.

You would like to know if the following statement is true for cards that your friend owns: “If a card has a vowel on one side, then it has an even digit on the other side.” More specifically, a vowel is one of ‘a’, ‘e’, ‘i’, ‘o’ or ‘u’, and even digit is one of ‘0’, ‘2’, ‘4’, ‘6’ or ‘8’.

For example, if a card has ‘a’ on one side, and ‘6’ on the other side, then this statement is true for it. Also, the statement is true, for example, for a card with ‘b’ and ‘4’, and for a card with ‘b’ and ‘3’ (since the letter is not a vowel). The statement is false, for example, for card with ‘e’ and ‘5’. You are interested if the statement is true for all cards. In particular, if no card has a vowel, the statement is true.

To determine this, you can flip over some cards to reveal the other side. You would like to know what is the minimum number of cards you need to flip in the worst case in order to verify that the statement is true.

Input:

The first and only line of input will contain a string s (1 ≤ |s| ≤ 50), denoting the sides of the cards that you can see on the table currently. Each character of s is either a lowercase English letter or a digit.

Output:

Print a single integer, the minimum number of cards you must turn over to verify your claim.

Sample Input:

ee

Sample Output:

2

Sample Input:

z

Sample Output:

0

Sample Input:

0ay1

Sample Output:

2

Note:

In the first sample, we must turn over both cards. Note that even though both cards have the same letter, they could possibly have different numbers on the other side.

In the second sample, we don’t need to turn over any cards. The statement is vacuously true, since you know your friend has no cards with a vowel on them.

In the third sample, we need to flip the second and fourth cards.

分析:

需要翻元音字母和奇数数字。

题解:

#include<cstdio>
#include<iostream>
using namespace std;
int main(){
    int count=0;
    char temp;
    while(true){
        scanf("%c", &temp);
        if(temp=='\n'){
            break;
        }
        if(temp == 'a' || temp == 'e' || temp == 'i' || temp == 'o' || temp == 'u' || temp == '1' || temp == '3' || temp == '5' || temp == '7' || temp == '9'){
            count++;
        }
    }
    printf("%d", count);
    return 0;
}

H – CF808A Lucky Year

1000ms 262144K

Description:

Apart from having lots of holidays throughout the year, residents of Berland also have whole lucky years. Year is considered lucky if it has no more than 1 non-zero digit in its number. So years 100, 40000, 5 are luckyand 12, 3001 and 12345 are not.

You are given current year in Berland. Your task is to find how long will residents of Berland wait till the next lucky year.

Input:

The first line contains integer number n (1 ≤ n ≤ 109) — current year in Berland.

Output:

Output amount of years from the current year to the next lucky one.

Sample Input:

4

Sample Output:

1

Sample Input:

201

Sample Output:

99

Sample Input:

4000

Sample Output:

1000

Note:

In the first example next lucky year is 5. In the second one — 300. In the third — 5000.

分析:

仅需把最高位的数+1取整再减原来的数即可。

比如2345的最高位数+1取整得3000,输出3000-2345即可。

不过这一题有一个大坑!不能用pow函数,要自己写一个。

题解:

#include<cstdio>
#include<iostream>
#include<cmath>

using namespace std;

long long poww(int count){
    if(count == 0) return 1;
    else return 10*poww(count-1);
}

int main(){
    long long year;
    int count = 0;
    cin >> year;
    long long backup = year;
    while(year > 9){
        year = year / 10;
        count++;
    }
    long long temp = (year + 1) * poww(count);
    cout << temp - backup;
    return 0;
}

I – CF954A Diagonal Walking

1000ms 262144K

Description:

Mikhail walks on a 2D plane. He can go either up or right. You are given a sequence of Mikhail’s moves. He thinks that this sequence is too long and he wants to make it as short as possible.

In the given sequence moving up is described by character U and moving right is described by character R. Mikhail can replace any pair of consecutive moves RU or UR with a diagonal move (described as character D). After that, he can go on and do some other replacements, until there is no pair of consecutive moves RU or UR left.

Your problem is to print the minimum possible length of the sequence of moves after the replacements.

Input:

The first line of the input contains one integer n (1 ≤ n ≤ 100) — the length of the sequence. The second line contains the sequence consisting of n characters U and R.

Output:

Print the minimum possible length of the sequence of moves after all replacements are done.

Sample Input:

5
RUURU

Sample Output:

3

Sample Input:

17
UUURRRRRUUURURUUU

Sample Output:

13

Note:

In the first test the shortened sequence of moves may be DUD (its length is 3).

In the second test the shortened sequence of moves can be UUDRRRDUDDUUU (its length is 13).

分析:

判断一下和上一步是不是不同,如果是就步数不变,如果不是就加一步。

题解:

#include<cstdio>
#include<iostream>
using namespace std;
char arr[105];
int main(){
    int t;
    int count=0;
    cin >> t;
    for(int i = 0; i < t; i++){
        cin >> arr[i];
        if(i != 0 && arr[i] != arr[i-1] && arr[i-1] != 'D'){
            arr[i] = 'D';
        }else{
            count++;
        }
    }
    printf("%d", count);
    return 0;
}

J – CF1006A Adjacent Replacements

1000ms 262144K

Description:

Mishka got an integer array aa of length nn as a birthday present (what a surprise!).

Mishka doesn’t like this present and wants to change it somehow. He has invented an algorithm and called it “Mishka’s Adjacent Replacements Algorithm”. This algorithm can be represented as a sequence of steps:

  • Replace each occurrence of 11 in the array aa with 22;
  • Replace each occurrence of 22 in the array aa with 11;
  • Replace each occurrence of 33 in the array aa with 44;
  • Replace each occurrence of 44 in the array aa with 33;
  • Replace each occurrence of 55 in the array aa with 66;
  • Replace each occurrence of 66 in the array aa with 55;
  • ……
  • Replace each occurrence of 109−1109−1 in the array aa with 109109;
  • Replace each occurrence of 109109 in the array aa with 109−1109−1.

Note that the dots in the middle of this algorithm mean that Mishka applies these replacements for each pair of adjacent integers (2i−1,2i2i−1,2i) for each i∈{1,2,…,5⋅108}i∈{1,2,…,5⋅108} as described above.

For example, for the array a=[1,2,4,5,10]a=[1,2,4,5,10], the following sequence of arrays represents the algorithm:

[1,2,4,5,10][1,2,4,5,10] →→ (replace all occurrences of 11 with 22) →→ [2,2,4,5,10][2,2,4,5,10] →→(replace all occurrences of 22 with 11) →→ [1,1,4,5,10][1,1,4,5,10] →→ (replace all occurrences of 33 with 44) →→ [1,1,4,5,10][1,1,4,5,10] →→ (replace all occurrences of 44with 33) →→ [1,1,3,5,10][1,1,3,5,10] →→ (replace all occurrences of 55 with 66) →→ [1,1,3,6,10][1,1,3,6,10] →→ (replace all occurrences of 66 with 55) →→ [1,1,3,5,10][1,1,3,5,10] →→ ……→→ [1,1,3,5,10][1,1,3,5,10] →→ (replace all occurrences of 1010 with 99) →→ [1,1,3,5,9][1,1,3,5,9]. The later steps of the algorithm do not change the array.

Mishka is very lazy and he doesn’t want to apply these changes by himself. But he is very interested in their result. Help him find it.

Input:

The first line of the input contains one integer number nn (1≤n≤10001≤n≤1000) — the number of elements in Mishka’s birthday present (surprisingly, an array).

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the elements of the array.

Output:

Print nn integers — b1,b2,…,bnb1,b2,…,bn, where bibi is the final value of the ii-th element of the array after applying “Mishka’s Adjacent Replacements Algorithm” to the array aa. Note that you cannot change the order of elements in the array.

Sample Input:

51 2 4 5 10

Sample Output:

1 1 3 5 9

Sample Input:

1010000 10 50605065 1 5 89 5 999999999 60506056 1000000000

Sample Output:

9999 9 50605065 1 5 89 5 999999999 60506055 999999999

Note:

The first example is described in the problem statement.

分析:

把所有的偶数减一。

题解:

#include<iostream>
using namespace std;
long long array[1005];
int main(){
    int t;
    cin >> t;
    for(int i = 0; i < t; i++){
        cin >> array[i];
    }
    for(int i = 0; i < t; i++){
        if(array[i] % 2){
            cout << array[i];
        }else{
            cout << array[i]-1;
        }
        if(i != t-1) cout << " ";
    }
    return 0;
}