code.blood's blog

C — Go Home . Atcoder last day contest
By code.blood, 8 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

»
8 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
→ Reply
  • »
    »
    8 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

    → Reply
    • »
      »
      »
      8 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?

      → Reply
      • »
        »
        »
        »
        8 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)

        → Reply
      • »
        »
        »
        »
        8 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 ?

        → Reply
        • »
          »
          »
          »
          »
          8 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 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 ?

            → Reply