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

×

SURVIVE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sidhant Bansal
Testers: Hasan Jaddouh
Editorialist: Sidhant Bansal

DIFFICULTY:

easy

PREREQUISITES:

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

Setter's solution.
Tester's solution.

This question is marked "community wiki".

asked 21 Jan '18, 23:50

sidhant007's gravatar image

6★sidhant007
179819
accept rate: 12%

edited 22 Jan '18, 15:35

admin's gravatar image

0★admin ♦♦
19.8k350498541


@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.

link

answered 22 Jan '18, 10:31

manishkc's gravatar image

4★manishkc
814
accept rate: 0%

Please add this at least to practice test cases

(19 Feb '18, 17:04) dollarakshay4★

Another Weak Testcase

1 
8 7 8
(19 Feb '18, 17:07) dollarakshay4★

@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.

link

answered 22 Jan '18, 16:31

shashank1998's gravatar image

5★shashank1998
112
accept rate: 0%

edited 22 Jan '18, 16:37

I am guilty of this

(19 Feb '18, 17:03) dollarakshay4★

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).

Solution.

link

answered 22 Jan '18, 10:38

eugalt's gravatar image

3★eugalt
2827
accept rate: 4%

edited 22 Jan '18, 12:50

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

link

answered 22 Jan '18, 18:10

anirudhjarvis's gravatar image

3★anirudhjarvis
673
accept rate: 12%

wikified 28 Jan '18, 15:02

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?

link

answered 04 Aug '18, 13:44

toppythoncoder's gravatar image

0★toppythoncoder
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;

}

link
This answer is marked "community wiki".

answered 15 Aug '18, 01:32

snshah's gravatar image

1★snshah
1
accept rate: 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" <="" code="">


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

link

answered 05 Oct '18, 00:05

polarstern's gravatar image

0★polarstern
1
accept rate: 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!!

link

answered 21 Dec '18, 15:23

stunner2k18's gravatar image

3★stunner2k18
112
accept rate: 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!!

link

answered 21 Dec '18, 15:23

stunner2k18's gravatar image

3★stunner2k18
112
accept rate: 0%

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

link

answered 15 Jan, 12:54

dkcs's gravatar image

2★dkcs
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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