You are not logged in. Please login at www.codechef.com to post your questions!

×

# 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

This question is marked "community wiki".

asked 21 Jan '18, 23:50 179819
accept rate: 12% 19.8k350498541

 5 @admin Weak test cases for this question: 1 9 8 10 Submissions giving wrong answer 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. answered 22 Jan '18, 10:31 4★manishkc 81●4 accept rate: 0% Please add this at least to practice test cases (19 Feb '18, 17:04) Another Weak Testcase 1 8 7 8  (19 Feb '18, 17:07)
 1 @admin 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. answered 22 Jan '18, 16:31 11●2 accept rate: 0% I am guilty of this (19 Feb '18, 17:03)
 0 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). answered 22 Jan '18, 10:38 3★eugalt 282●7 accept rate: 4%
 0 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): answer=0 counter=0 for i in range(s): counter+=1 counter%=7 if(counter!=0): maans+=1 answer+=n if(answer>=capacity): 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. For Codes as files to download visit:- DOWNLOAD CODE answered 22 Jan '18, 18:10 67●3 accept rate: 12%
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?

answered 04 Aug '18, 13:44 1
accept rate: 0%

# include <iostream>

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;


}

This answer is marked "community wiki".

answered 15 Aug '18, 01:32 1★snshah
1
accept rate: 0%

 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 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 answered 05 Oct '18, 00:05 1 accept rate: 0%
 0 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!! answered 21 Dec '18, 15:23 11●2 accept rate: 0%
 0 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!! answered 21 Dec '18, 15:23 11●2 accept rate: 0%
 0 30 6 30 is not coming -1, it should be 6 itself answered 15 Jan, 12:54 2★dkcs 1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,851
×3,820
×1,024
×82
×28

question asked: 21 Jan '18, 23:50

question was seen: 2,933 times

last updated: 15 Jan, 12:54