 # SURVIVE - Editorial

Author: Sidhant Bansal
Editorialist: Sidhant Bansal

easy

basic math

### PROBLEM:

In this problem, the greedy approach of buying the box of chocolate for some consecutive early days is the right direction.

Let A = K * S and B = N * (S - S/7), here A denotes the total number of chocolates we need to eat and B denotes the maximum no. of chocolates we can buy. Here S - S/7 denotes the number of days the shop is open.

So if A > B or ((N - K) * 6 < K and S \geq 7), then the answer is -1.
otherwise the answer is ceil(\frac{A}{N}), where ceil(x) denotes ceiling function on x.

The first condition i.e A > B, for -1 is fairly obvious that if the total no. of chocolates we need to eat is more than we can buy at max then it is invalid.

The second condition i.e (N - K) * 6 < K and S \geq 7 is a bit tricky, it is basically the contrapositive of the statement, “if you can survive the first 7 days, then you can survive any given number of days”. So the contrapositive (i.e same statement in different words) is "if you cannot survive the first 7 days then you won’t be able to survive for S \geq 7". The condition for being able to survive on the 7^{th} day is basically if we add our remaining chocolates from the first 6 days, i.e (N - K) * 6 and it is still smaller than K, i.e the chocolates we need for the 7^{th} day, then we don’t survive. But we only need to test this when S \geq 7.

Incase, we are able to survive, then the answer is ceil(\frac{A}{N}), which is basically total number of chocolates we need to eat divided by the number of chocolates we can buy in a single day (and if a remainder exists, then we need to buy one more day). This portion is pretty straightforward.

The above reasoning to check for -1 is obviously tricky and a simpler approach exists which is to just simulate the days once we know the value of ceil(\frac{A}{N}).

### SOLUTIONS

1 Like

@admin Weak test cases for this question:
1
9 8 10

S1
S2

I request you to add this test case in practice question. Please make sure such things not happen in future as it brings down the moral of participants.

5 Likes

For the first condition we could just use N < K (we must buy at least a day supply of chocolate on the first day), and the second condition can be written as 6N < 7K (we must buy at least a week supply of chocolate during the first week).

The test cases are very week

1

8 7 8.

The output should be -1. But many accepted solutions of this problem are producing output 7 for this case which is quite obvious wrong. Please make sure such kind of things not occur in future and the test cases for questions in the contest should have appropriate corner cases.

1 Like

Problem: SURVIVE

My short solution in PYTHON-3.5:My solution in O(n) easy to understand. O(1) is more efficient

te=int(input())
for _ in range(te):
n,k,s=input().split()
n,k,s=int(n),int(k),int(s)
capacity=k*s
availablity=n*s
availablity-=n*(s//7)
maans=0
if(capacity<=availablity):
counter=0
for i in range(s):
counter+=1
counter%=7
if(counter!=0):
maans+=1
break
print(maans)
else:
print("-1")


LOGIC:-
Maxmimum choclates he needs is ks which is capacity. And the availablity of chocolates is ns-(n(s//7)) as on Sunday shop is closed and he can’t buy any chocolates. So if capacity > availablity print("-1") as it is not possible to purchase. Else Run a loop to find the number of days and dont forget not to calculate sundays and add n chocolates only on non sundays.

Like,Comment, Follow and award reputation points if u like. For any other queries or doubts contact me.

I am guilty of this

Another Weak Testcase

1
8 7 8

for t in xrange(int(raw_input())):
n,k,s=map(int,raw_input().split())
b=1
F=True

d=[]
for i in xrange(1,(s/7)+2):
d.append((7*i)-1)

for i in xrange(1,s+1):
if k>n:
F=False
break
elif i in d and (n*b)-(k*i)<k and s!=i:
F=False
break
elif (n*b)-(k*i)==0 and s==i:
pass
elif (n*b)-(k*i)<k and (n*b)-(k*i)!=0 and i!=1:
b+=1
if F==True:
print b
elif F==False:
print -1


#### What seems wrong with my code?

#include
using namespace std;

int main() {

int t;
cin>>t;
while(t--)
{
int n,k,s,tot,box=1,flag=0,set=0;
cin>>n>>k>>s;
tot=n;
for(int i=1;i<=s;i++)
{
//  cout<<"before tot="<<tot<<" day="<<i<<" set="<<set<<endl;

if(tot>=k)
{tot=tot-k;
set=0;
}
else if(i%7!=0)
{

tot=tot+n-k;
box++;
if(i%7==6)
set=1;

}
else if(i%7==0&&set==0)
{i--;
tot=tot+n;
box++;

}
else
{ flag=1;
cout<<"-1"<<endl;
}

}
if(flag==0)
cout<<box<<endl;

}

return 0;


}


t = int(input())
while t:
cnt=0
n,k,s = (int(n) for n in input().split())
chocs=n
days=1
while chocs>=0:
if cnt==s:
print(days)
break
cnt+=1
if chocs<k and cnt%7!=0:
days+=1
chocs+=n
chocs-=k
else:
print(-1)
t-=1



my code gives correct answer for the weak cases mentioned but is not being accepted can anyone help what should i modify or where am i incorrect
ps: it is in python 3

1

30 6 30

check this one correct answer should be -1 but many accepted solutions are showing it to be 6.please anyone help!!

1

30 6 30

check this one correct answer should be -1 but many accepted solutions are showing it to be 6.please anyone help!!

30 6 30 is not coming -1,
it should be 6 itself

//