code.blood's blog

By code.blood, 5 years ago, In English

Hello codeforces community , I am facing with that problem . For the input 12 how output is 5 ?

My solution is :

at time 0 we jump from 0 to 1 co-ordinate

at time 1 we jump from 1 to 3 co-ordinate

at time 2 we jump from 3 to 6 co-ordinate

at time 3 we dont jump because now jump length will be 4 , since we are on co-ordinate 6 so if we jump we will be on 6+4=10 co-ordinate ,

at time 4 we dont jump because now jump length will be 5 , since we are on co-ordinate 6 so if we jump we will be on 6+5=10 co-ordinate ,

at time 5 we will jump because now jump length will be 6 , since we are on co-ordinate 6 so if we jump we will be on 6+6=12 co-ordinate . We reached on co-ordinate 12 at time 6 . because one jump takes one second (5+1=6) .

So ans should be 6 . Why 5 ?

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
5 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it
  • during time between 0 and 1 jump to coordinate 1
  • during time between 1 and 2 jump to coordinate 3
  • during time between 2 and 3 do not jump so remain at coordinate 3
  • during time between 3 and 4 jump to coordinate 7
  • during time between 4 and 5 jump to coordinate 12
  • so we need 5 units of time hence it is 5
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    thanks :) . How to solve this problem if they said Find minimum jump and minimum time to reach X . Here we have to minimize the time and minimize the jump also . For example : 12 ans should be : minimum jump=4 and minimum time=5

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      Minimum number of jumps is always 1 :)

      By the way, If you mean minimum number of jumps in minimum time (also for 12 the answer would be 3; 3+4+5=12), I think greedy is OK. Am I wrong?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 5   Vote: I like it +8 Vote: I do not like it

        Great solution . Thanks :) .

        Your solution is correct i think :

        16

        time=6 , jump=4 (6+5+4+1=16)

        24

        time=7 , jump=5 (7+6+5+4+3=24)

        17

        minimum time=6 , minimum jump=4 (6+5+4+2)

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        How to implement it ? Is a linear loop is enough ? ( For minimum jump calculation)

        int cnt=0,tot=0;

        for(int i=time;i>=1;i--) {

        tot+=i;
        
           cnt++;
        
          if(tot==x)
        
            break;
        
        
          if(tot>x)
            {
        
                tot-=i;
        
                cnt--;
        
            }

        }

        cout<<cnt<<'\n';

        17

        minimum time=6 , minimum jump=4 (6+5+4+2)

        am i wrong ?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I'm not totally sure about the algorithm, But your implementation is correct.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            17

            minimum time=6 , minimum jump=4 (6+5+4+2) is this correct too ?