Please, give me test 18

I mean, there obviously must be some compiler optimizations that enable the O(K^2) algorithm to be accepted for the worst case.

For example, I've tried binary search, given that this is a convex function, and the amount of branch prediction misses slows the thing down a lot.

I've been looking at godbolt.org output and can't figure out what is happening here.

I don't understand why my code fails. I have been very careful with all cases. The precision of the numbers, the zero and negative benefits, everything. My code should not have so many lines but I have put them for the frustration of having so many WA. Are you sure test # 2 is ok? Check it with my code. Previously I tried it with a much shorter code that reached test # 7 and failed, but it did not take care of rounding problems, this does and fails in test # 2 X-¿
Help, Please!


// Brute force
#include <stdio.h>
#include <math.h>

long calcMax (int horn_n , int hoof_n,  float horn_b, float  hoof_b ) {

    long max =  (long) horn_b * horn_n + (long) hoof_b * hoof_n - (long) 100 * ( horn_n * horn_n +  hoof_n * hoof_n);
    return max;
}

int passtoInt( char *number) {
    int num = 0, signo = 1, begin = 0;
    char decimal_flag = 'N';
    int dec_ndig = 0;
    if( number[0] == '-')  {
        signo = -1;
        begin = 1;
    }
    for(int i=begin; number[i] != 0; i++) {
        if(number[i] == '.')  {
            decimal_flag = 'Y' ;
            continue;
        }
        if(decimal_flag == 'Y') dec_ndig++;
        if(dec_ndig > 2) break;

        num = num * 10  + (number[i] - '0');

    }
    for(int i = dec_ndig; i < 2; i++) num = num*10;

    return num * signo;
}


void getPartEntAndDec(long num, long *ent, unsigned *dec )  {
    *ent = num / 100;
    *dec = num % 100;

}


int main(void) {
    char horn_s[14],  hoof_s[14];
    int  horn_n= 0, hoof_n = 0, horn = 0, hoof = 0;

    int horn_b, hoof_b;
    long max = 0, max1, max_ent;
    unsigned max_dec;
    int maxmount;

    scanf("%s%s%d", horn_s, hoof_s, &maxmount);
    horn_b = passtoInt( horn_s);
    hoof_b = passtoInt( hoof_s);

    for(int horn_n = 0; horn_n <= maxmount; horn_n++) {
        for(int hoof_n = 0; hoof_n <= maxmount -  horn_n;  hoof_n++) {
            max1 = calcMax (horn_n , hoof_n,  horn_b,  hoof_b );
            if(max1 > max) {
                horn = horn_n;
                hoof = hoof_n;
                max = max1;
            }
        }
    }
    getPartEntAndDec(max, &max_ent, &max_dec );
    printf("%ld.%02u\n", max_ent, max_dec);
    printf("%d %d\n", horn,  hoof);
    return 0;

}

Can you please share some tests?

Answer was correct on every test from forum, still can't pass test 14 + implemented all the hints, including rounding with 0.5000000001 and searching near the optimal values
:(

Thanks in advance!

Edited by author 28.12.2016 02:12

New tests have been added. All solutions have been rejudged: 288 authors have lost AC.

// del

Edited by author 26.11.2015 22:08

Try this test:
-1 -1
1

Answer:
0.00
0 0

could you give me test #7?
I can not  understand what is wrong!

O(k)    0.015 s

Please give test 2 for this problem.

Hi, I have read all messages from the forum about this test 14, but nothing helps. Here is my code
[code deleted]
, what is wrong? Thanks in advance/

Edited by moderator 06.12.2019 20:41

This code gets WA 1:

long long readLL()
{
    string s;
    cin >> s;
    s.erase(s.find('.'),1);
    stringstream ss(s);
    long long x;
    ss >> x;
    return x;
}

And this code gets AC:

long long readLL()
{
    double d;
    cin >> d;
    return ll(d*100 + 0.0000001);
}

input:
2 2
10
Output:
2.00
1 1
Algo:
cin>>a>>b; cin>>k;
    for(i=0; i<=k-1; i++){
              for(j=0;j<=k-i; j++){
               l=i*i+j*j;
               g=i*a+j*b;
               x=g-l;
              if(x>=r){n++; r=x; s[n]=r; si[n]=i; sj[n]=j;}}}
      for(int y=1; y<=n; y++){ if(s[n]==s[y]){
              cout<<fixed<<setprecision(2)<<s[y];
              cout<<endl<<si[y]<<" "<<sj[y]<<endl; } }

Is it right?

can anyone here tell me the test data for test#7?
and thanks

my AC solution works 0.218 sec
and it is O(K^2), which is bad, and shouldn't be Accepted

1) Slow algorithm O(K*(K+1)/2) : brute force. AC : 0.2 !
-> Find the profit with each number of horn and hoof (horn + hoof <= k).

2) Fast algorithm O(K*2) : caching the optimal number of horns and hoof. AC : 0.031 !
Find :
   +     The optimal number of horns <= k (A)
   +     The optimal number of hoof <= k - num of horns (B)
=>    result = A + B;

2) More Fast algorithm O(K) : caching the optimal number of horn or hoof. AC : 0.031 !
Caching the number of hoof.
-> For each number of horn
   + The optimal number of hoof = 0 ... k - optimal num of horn.

What's the test#12? I failed!!!
Could you help me?