Title Description

Note: the header files that can be used in this topic are limited to cstdio # iostream # cstring

Dreaming back to senior three, Xiao AI remembered the time when she recited ancient poems and articles of the college entrance examination a few months ago

It's already evening. There was a test the next day, but AI still had a testThis ancient poem was not memorized. thisEvery ancient poem has a corresponding drowsiness valueIn other words, choose to reciteIt will increase AI's drowsiness​. AI's current drowsiness isAnd when AI's drowsinessWhen, Xiao AI will sleep directly until tomorrow morning, so there will be no more time to recite! Note that because half of the articles memorized are also articles not memorized, it just makes Xiao AI sleepyThe article of is also regarded as not memorized.

Fortunately, the goal probability of each article in the quiz is the same, so in order to get a higher score in the quiz, Xiao AI only needs to recite as many articles as possible. Xiao AI predicted that the articles he recited will be right in the quiz tomorrow, and the articles he didn't recite will have a 10% probability of being right. The quiz only examines the dictation of these n ancient poems. Each article has one question, and the score of each question is the same. The full score of the quiz is 100.

"How about the night? The night is still in the ascendant." It's getting late. AI is still a little nervous about tomorrow's quiz. Please help Xiao AI calculate the maximum score of tomorrow's quiz after staying up late to endorse!

Input format

There are two lines to enter.

The first line is the third integerRespectively represents the number of articles, AI's current drowsiness value, and the drowsiness value for AI to fall asleep directly.

Second actA nonnegative integer indicating thisSleepiness value of an ancient poem​.

Output format

Output a total of one line.

The first line is an integer, indicating the expected maximum score of Xiao AI (rounded down).

sample input

5 0 10
2 4 6 10 1

sample output

64

There are 5 questions in total, so 20 points for each question. Xiao AI can recite up to three articles (drowsiness value is 24.1), and the expected score is

Data range

For 40% of the data,

For another 20% of the data,

For another 40% of the data,

For all data, and

Make complaints about Tucao

First of all, this person is really a talent. He doesn't start reciting so many ancient articles early and wants to recite them all in one night... He doesn't study hard at ordinary times...

Is it very much like you before the final exam

The most outrageous thing is that after reading that data

        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Yes, I'm really speechless...

Darling, not really. It seems that there is a lot of ancient Chinese, thatLet's not comment for the time being. It's estimated to be a Book King. The 5000 articles are outrageous enough. Can he really recite them

Suddenly I think of sjtu's English test... I can't finish learning

Fortunately, I will learn data structure next semester

You'd better go to bed. It's so sweet to sleep

Also, I don't know why this topic is called McDonald's. is it because the questioner matched the data at McDonald's? Suddenly the aroma came 2333

Only cstdio ， iostream ， cstring is allowed. It seems that the purpose is not to allow you to use the sort function, so split it yourself

Dichotomy yyds

No, I make complaints about it. Anyway, it's a fat diet.

Problem solving

Obviously, this topic is four steps

1. Put these strange ancient texts in order according to the degree of drowsiness o(╥﹏╥) O
2. Start endorsing from small to large. o(╥﹏╥) o is like brushing English texts before sjtu English quiz. Of course, the short one is preferred
3. If you can't carry it, go to bed (✿ﾟﾟﾟﾟﾟ) ok, (I didn't finish reading it several times, but I still lay flat)
4. How much you take depends on your luck ()

sort function is not allowed to be used, but it is OK. The use method is at the end of the article.

It seems that this topic is very suitable for learning first-hand sorting methods,

Let's first look at the most common method, bubble sorting:

You might as well review the principle of bubbling first. If yes, please ignore the following parts directly:

>Supplementary knowledge: principle of bubble sorting

First, let's assume that there is an array (whether to start from 0 or 1 depends on yourself). The first row is the number and the second row is the number of the corresponding sequence

number
numerical value	8	2	5	7	1	9	0

To complete the sorting, you need to go through the bubble process

First round blistering: fix a position on the left (green part), and scan the numbers in the yellow part from left to right

number
numerical value	8	2	5	7	1	9	0

Once a number smaller than the green element is found, the exchange is performed immediately: for exampleThe exchange is required, as shown in the figure below

number
numerical value	2	8	5	7	1	9	0

Continue scanning. The next thing to exchange is

number
numerical value	1	8	5	7	2	9	0

Continue scanning. The next thing to exchange is

number
numerical value	0	8	5	7	2	9	1

After scanning, the first position has been confirmed, which is also the smallest number in all arrays. The confirmed position is marked with blue, and then the green mark moves to the right to start the second round of blistering

number
numerical value	0	8	5	7	2	9	1

The second round of bubbles is similar to the first round, which can be found in the second roundAfter a round of bubbles,It will be confirmed. In this way, a total of 7 rounds can be completed

Thinking: for a sequence with n termsHow many rounds does it take? At mostTimes, so the time complexity is.

>Solution of bubble sorting

Similarly, the code for solving the problem by bubble sorting is as follows:

#include <iostream>
using namespace std;
int main()
{
    long long int n, t, k,temp;
    cin >> n >> t >> k;
    long long int array[n];
    for (int i = 0; i < n; i++)
    {
        cin >> array[i];
    }

    for (int x = 0; x < n; x++)
    {
        for (int y = 0; y < n-1; y++)
        {
            if (array[y + 1] < array[y])
            {
                temp = array[y + 1];
                array[y + 1] = array[y];
                array[y] = temp;
            }
        }
    }//Bubble sorting

    for (int i = 0; i < n;i++)
    {
        
        t = t + array[i];
        if (t >= k)     
        {
            cout << i * 100 / n + (n - i) * 10 / n;
            break;
        }
    }
    system("pause");
    return 0;
}

However, the complexity of this code is too high to be used to solve problems, especially in the case of such a scroll King endorsement, where can hold live, really

Therefore, quick sorting is called dichotomy

>Supplementary knowledge: the principle of dichotomy sorting

The basic idea of dichotomy is the recursion of functions, assuming that there is a sequence with a length of 10

number
numerical value	5	7	3	0	4	2	1	9	6	8

        1. First, we take one of these 10 numbers at random, such as, and save it to Variable k, which will be used as a reference value for subsequent comparison

For ease of understanding, we might as well putIt can be emptied or not actually emptied

number
numerical value		7	3	0	4	2	1	9	6	8

        2. Define low and high variables, low=1, high=10; High prepare to scan from right to left (reference object is )  

number
numerical value		7	3	0	4	2	1	9	6	8

        3. Scan from high to left from 10, pass if it is greater than or equal to K, stop if it is less than k, and put this element in a[low]; Scanned are shown in yellow

number
numerical value		7	3	0	4	2	1	9	6	8

high scan from right to left, now we find, thenIt should be in, low continue scanning

number
numerical value	1	7	3	0	4	2		9	6	8

low scans from left to right and findsIt's bigger than k, so put it on the right

number
numerical value	1		3	0	4	2	7	9	6	8

high continued to scan from right to left and found thatSmaller than k, put it on the left

number
numerical value	1	2	3	0	4		7	9	6	8

low continues to scan from left to right and finds, ha ha ha ha ha, low crazy all the way to

number
numerical value	1	2	3	0	4		7	9	6	8

OK, low and high rounds. OK, put k in a6 of the meeting

number
numerical value	1	2	3	0	4	5	7	9	6	8

Smart, you must have found outYour position is already right. Now you want to sort~，~

Recursion is enough

This function is the total function responsible for sorting

//Sort function to obtain an array of elements from low to high in increasing order
//Because the array is passed directly in the function, the operation and modification are directly performed on the original array
void SortQuick(int a[], int low, int high)
{
    int mid;
    if (low >= high)    return;
    mid = divide(a, low, high);
    SortQuick(a, low, mid - 1);
    SortQuick(a, mid + 1, high);
}

This function is responsible for returning the position of low and high rounds

//The divide function is used to sort. Those less than a[0] are placed on the left and those greater than a[0] are placed on the right
int divide(int a[], int low, int high)
{
    int k = a[low];

    do{
        while (low < high && a[high] >= k)      --high;
        if (low < high) 
        {
            a[low] = a[high];
            ++low;
        }
        while (low < high && a[low] <=k)        ++low;
        if (low < high) 
        {
            a[high] = a[low];
            --high;
        }
    } while (low != high);
    a[low] = k;
    return low;
}

The test results can only pass 70% of the data

        o(╥﹏╥)oo(╥﹏╥)oo(╥﹏╥)oo(╥﹏╥)oo(╥﹏╥)oo(╥﹏╥)o

Ahhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh

Continue to change,

void QuickSort(int l, int r)   //The thought has not changed, but the method has improved a lot
{                              //l is the left end to start sorting, and r is the right end to start sorting
    int mid = (l + r) / 2;     //Take the median value
    int i = l;                 //Why define i and j separately?
    int j = r;                 //A: l and r are fixed. We need to sort. L is the starting point and r is the end point
    int x = array[mid];        //In the later process, there are self increasing and self decreasing processes, but the sorting start and end points remain the same,
    do                         //The definition of i j is used for the following services
    {
        while(array[i]<x)      //Simulate the above-mentioned scanning from left to right, and pass as long as it is smaller than mid
            ++i;               //! Warning: must be array [i] < x, not<=
                               //The reason is that once the array[mid] is the maximum, the program subscript directly crosses the boundary
        while(array[j]>x)      //Simulate the scanning from right to left as mentioned above, and pass as long as it is larger than mid
            --j;               //! Warning: must be array [J] > x, not >=
                               //The reason is that once the array[mid] is the minimum, the program subscript directly crosses the boundary
        if (i <= j)            //Running here shows a problem. Scanning from left to right and from right to left has stopped
        {                      //Stop means array[i], array[j] that do not meet the conditions
                               //Note: if (I < = J) must be < = and cannot be < otherwise, sorting cannot be performed when there is only one number
           swap(array[i], array[j]);
           ++i;--j;            //Obviously, as long as the two of them are exchanged, the conditions can be met. Remember + + I when the exchange is over-- j; 
                               //! Warning: must be + + I-- j; Otherwise, one or two numbers will loop
        }                      //
    } while (i <= j);          //I < J is also correct, which can be passed
    
    //We might as well consider the result of the last run of the function
    //It must be I > mid > J
    //that
    if (l<j) QuickSort(l,j);    //The purpose of if is to prevent subscripts from crossing boundaries
    if (i<r) QuickSort(i,r);
}

void swap(int a, int b)        //This function exchanges the elements in array [a] and array [b]
{
    int temp = a;
    a = b;
    b = temp;
}

So you can pass

>Solution of bubble sorting

Here is the complete code

#include <iostream>
using namespace std;

unsigned long long int array[1000005];
unsigned long long int n, t, k;
void QuickSort(int l, int r);
void swap(int a, int b);

int main()
{
    cin >> n >> t >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> array[i];
    }
    
    QuickSort(0, n - 1);      //Sort
    long long int temp = 0;
    long long int cnt = 0;
    k = k - t;                //Remind me, this fool may be worth millions or hundreds of millions of dozing,
                              //It's not more scary to carry it on your back, so subtraction is smarter
                              //Otherwise, it may cross the border
    long long int i;
    for (i = 0; i < n; i++)
    {
        if (temp + array[i] >= k)    
        {
            break;
        }
        temp = temp + array[i];
    }                         //Stop when exceeded
    cnt = i;
    int ans=(cnt*100+(n-cnt)*10)/n;
    cout<<ans;
    system("pause");
    return 0;
}


void QuickSort(int l, int r)
{
    int mid = (l + r) / 2;
    int i = l;
    int j = r;
    int x = array[mid];
    do
    {
        while(array[i]<x)
            ++i;             
        while(array[j]>x)
            --j;
        if (i <= j)
        {
            swap(array[i], array[j]);
            ++i;--j;
        }
        // cout << "#" << endl;
    } while (i <= j);
    if (l<j) 
        QuickSort(l,j);
    if (i<r) 
        QuickSort(i,r);
}

void swap(int a, int b)
{
    int temp = a;
    a = b;
    b = temp;
}

>Supplementary knowledge: usage of Sort function

The sort function is used in C + + to sort all elements in a given interval. The default is ascending or descending. The time complexity of sorting by sort function is n*log2n, which is more efficient than sorting algorithms such as bubble. Sort function is included in C + + standard library with header file of #include < algorithm >.

Syntax:

sort(start,end,cmp);

Explanation:

(1) start indicates the starting address of the array to be sorted;

(2) End indicates the next bit of the end address of the array;

(3) cmp is used to specify the sorting method. It is optional. The default is ascending.

explain:

The sort function is used in C + + to sort all elements in a given interval. The default is ascending or descending.

Generally, the array is sorted directly, such as sorting array a[10], sort (a,a+10). The power of sort function can be combined with cmp function, that is, the selection of sorting method.