M_a_h_t_a_b's blog

Nice Mathematical Problem
By M_a_h_t_a_b, history, 9 months ago, In English 
Magical Diamond
                                                  Time Limit: 1 second
                                               Memory Limit: 256 megabytes

Problem Statement Alice discovered a Magical Diamond sequence defined by a positive integer k. The sequence is constructed as follows: 1,2,3,…,k−1,k,k−1,k−2,…,2,1 In other words, the sequence first increases from 1 to k, then decreases back to 1. The total length of the sequence is 2k−1. For a given position x in this sequence (1-based index), Alice wants to know the cumulative sum of the first x elements. Formally, define: Cumulative Sum(x) = sum of the first x elements of the sequence Help Alice calculate Cumulative Sum(x) efficiently.

Input The first and only line contains two integers k and x (1≤k≤10^9,1≤x≤2k−1) — the size of the diamond and the position for which the cumulative sum is required.

Output Print a single integer — the cumulative sum of the first x elements of the Magical Diamond sequence.

Examples Input: 4 3

Output: 6

Explanation: The sequence is: 1 2 3 4 3 2 1 Cumulative sum of the first 3 elements: 1 + 2 + 3 = 6

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
9 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

If(x<=k)then its (x*(x+1))/2 else from k*(k+1)(added twice)subtract k then subtract (t*(t+1)/2 where t=k+k-1-x.

→ Reply
  • »
    »
    9 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    if x<=k then x(x+1)/2 but when x>k then d=x-k, sum=(k(k+1)/2) + d*(k-1) — (d(d-1)/2) [ this is the decreasing part]

    → Reply
    • »
      »
      »
      9 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      For instance k=10 and x=13 then we have to exclude the sum [1,6].Here t=6 (19-13)

      → Reply
      • »
        »
        »
        »
        9 months ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it

        yes, you are right. sorry

        → Reply
      • »
        »
        »
        »
        9 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

        include <bits/stdc++.h>

        using namespace std;

        const long double pi = acos(-1); const int mod = 1e9 + 7;

        define int int64_t

        define ll long long

        define nl '\n'

        define all(x) (x).begin(), (x).end()

        define vvl(name, n, m, val) vector<vector> name(n, vector(m, val))

        define yes cout << "YES" << '\n'

        define no cout << "NO" << '\n'

        int sum(int N) { return (N*(N+1))/2; }

        void solve(){ int k,x; cin>>k>>x; if(x<=k) { cout<<sum(x); } else { int temp=k*k; int rem=(2*k-1)-x; cout<<temp-sum(rem); } }

        signed main(){ int t=1; // cin>>t; while(t--) solve(); return 0; } ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

        → Reply
»
9 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Do you create it by yourself?

→ Reply
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What a problem it was.....Very interesting..

→ Reply
»
9 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Take love brooooo...and go on

→ Reply