GYMDAY - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Chef has Y coins, a gym membership costs X.
Chef can spend one coin to attend a trial session, which gets him a D\% discount on the membership.

Find the minimum number of trials Chef must attend to be able to afford a membership.

EXPLANATION:

Suppose Chef attends exactly k trials, and then buys a membership.
He then receives a total discount of (k\cdot D)\% on the membership cost, while spending k coins beforehand.

So, the total cost to Chef is

k + X\cdot\left( \frac{100 - k\cdot D}{100} \right)

If this quantity is \leq Y, Chef can afford it; otherwise he cannot.

Chef cannot attend more than Y trials (since he can’t spend more than Y coins), so simply try every k = 0, 1, 2, \ldots, Y and find the first one among them such that

k + X\cdot\left( \frac{100 - k\cdot D}{100} \right) \leq Y

If they all fail the check, the answer is -1.

TIME COMPLEXITY:

\mathcal{O}(Y) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    d, x, y = map(int, input().split())
    
    ans = -1
    for i in range(y+1):
        coins = y - i
        discount = i*d*x/100
        if coins >= x - discount:
            ans = i
            break
    print(ans)
2 Likes
2

Thanks for the solution. It is well explained.

I have a question regarding floating-point operations in c++.

All the variables are defined as int.
The following code snippet wrongly prints 25 for d, x, y being 3 50 38 respectively.

if(x * ((100-cnt*d)/100.0) <= y-cnt) {
    cout << cnt << "\n";
    return;
}

Whereas the following one correctly prints 24

if(x*(100-cnt*d)/100.0 <= y-cnt) {
    cout << cnt << "\n";
    return;
}

Thanks in advance.

Edit: Any help that suggests an approach to the division involving operations in c++ is appreciated.

3

Use ceil() function for this one:
if(x * ((100-cnt*d)/100.0) <= y-cnt) {
cout << cnt << “\n”;
return;
}
it turns float number to nearest integer.
5.7 → 6
ceil(5.7) will give 6
(100-cnt * d)/100.0 will turn 2.5 to 2

1 Like
4

Are we clear that whenever a double involves in multiplication or division, the result is a double?

If so, when I come to your appreciated suggestion, unfortunately I did not get the logic of the use of ceil function either. Can you explain, please?

My main concern is the difference between the two approaches below.

x * (100-cnt*d) / 100.0

x * ( (100-cnt*d) / 100.0 )
1 Like
5

Can someone help me understand on which testcase this code is failing? It’s failing on tc 2.

void solve()
{
	double d, x, y; cin >> d >> x >> y;
	double count = 0.0;
	double price = x;
	while (x > y) {
		count += 1.0;
		x = (double)(price * (100.0 - count * d) ) / 100.0;
		y--;
		cerr << "x: " << (x) << endl;
		cerr << "y: " << (y) << endl;

		if (y == 0) {
			if (x == 0) cout << count << endl;
			else cout << -1 << endl;
			return;
		}
	}
	cout << count << endl;
	cerr << endl;
	return;

}
6

Help me figure out failing tc in second test case

void sol(){
    ll discount,membershipCost,current;
    cin>>discount>>membershipCost>>current;

    int trail=0,updatedMewmbership=membershipCost;
    while(current<updatedMewmbership){
        if(current<=0){
            cout<<-1<<endl;
            return;
        }

        trail++;
        current--;
        updatedMewmbership= (double)(membershipCost*(100.0-discount))/(double)100;
        discount+=5;

    }
    cout<<trail<<endl;
}```