You might want to study this article: https://www.elcamino.edu/faculty/gfry/210/DistributeDifBallsDifBoxes.pdf

Please, give me test 18

Pigeonhole principle: It will always be possible and the answer will always be a continuous sequence.
How to solve:
Consider N = 7:
1 2 50 3 4 0 0
The sum of the segment 1, 2, 50 is 53 and that of 1,2,50,3,4 is 60
53 % 7 = 4
60 % 7 = 4
if a % x = 1
and b % x =1
then (a-b)%x is always 0
So the segment between those two prefix sums will give 0 as modulo which is (3,4) = 7

this

3 1
1000 90
1000 90
1000 90
2 5

helps me

I've noticed that the solution is always the number of walls we encounter*9 (excluding the first and last boxes). Why is this working?

If you pick n-1 as l then the second player will always win, so answer can never be 0
0 means  picked up the first player and 1 means picked up the second;
Case 1: 3 buttons
for i = 1 //doesn't make sense to solve for 1 since its asked to choose >=2
1 2 3
0 1 0 //first player won
for i = 2
1 2 3
0 0 1
0 1 1 // first play wins in each case
Case 2: 4 buttons
for i = 2
1 2 3 4
0 1 1 0
0 1 0 0 //first player wins in both these cases
for i = 3:
1 2 3 4
0 0 0 1
0 1 1 1
0 0 1 1 //second player wins in each case
case 3: 6 buttons (5 and 6 are similar)
1 2 3 4 5 6
for i = 2
0 1 1 0 0 1
0 0 1 0 0 1
0 1 1 0 1 1 //second player is  winning

It's clearly seen that the minimal choice to win is k such that n %(k+1) == 0
since n%((n-1)+1) is always 0, n-1 is always an answer in case no smaller answer exists.

import itertools
surprize =[]
x = int(input())
while x > 1:
    x -= 1
    surprize.append(x)
print (len(list(itertools.permutations (surprize))))

It's very easy to calculate this integral. But if you don't know what's integral, there are solution

In-first, i calculated a k
k = (a^2 * b * pi / 8) (or a*a*b*0.39269908169872415480783042290994 :) )
In-second, you should calculate y (or other symbol) from 1 to -1 with division (if n = 5: 1, 3/5, 1/5, -1/5, -3/5, -1)
In-third, calculate F(y) = y*(1 - y^2 / 3). (F(1) = 2/3)
in-fourth, print k*(F(yi) - F(y(i-1))) in loop
example:
if n = 2: first calculate should be k*(F(1) - F(0)), second k*(F(0) - F(-1))
if n = 3: 1) k*(F(1) - F(1/3)); 2) k*(F(1/3) - F(-1/3)); 3) k*(F(-1/3) - F(1))
etc.

[code deleted]

Edited by moderator 02.09.2020 19:58

If you want to get AC for a Kotlin solution, you should probably use java.util.Scanner instead of readLine() and try multiple times. I was able to get AC only on the second try with the same code, got TLE first time.

Read tasks and deadlines from the programmer's handbook. similar greedy approach will work in this one.
Also, why is this tagged dp? my dp soln is giving tle

/***************************************************************************************************
                         Anzmaul Haque Akash
                    DIU, Daffodil International University
                    E-mail: anzamul15-2297@diu.edu.bd
 Youtube:https://www.youtube.com/channel/UCXvXHUkxyLYKeQkIg_RyMBw
******************************************************************************************************/
#include<bits/stdc++.h>

#define ln     (int)1e6
#define pi     acos(-1.0)
#define pb     push_back
#define pf     push_front 1
#define mp     make_pair
#define F      first
#define S      second
#define INF    1000000000000000000
#define LES    -1000000000000000000
#define intlim 2147483648
#define ll     long long
#define ull    unsigned long long
#define str    string
#define in     insert

#define all(akash)       akash.begin(),akash.end()
#define ms(arr)          memset(arr,0,sizeof(arr))
#define msbooltrue(arr)  memset(arr,true,sizeof(arr))
#define msboolfalse(arr) memset(arr,false,sizeof(arr))
#define msINF(arr)       memset(arr,INF,sizeof(arr))
#define case1(cs)        cout<<"Case "<<cs<<": "
#define case2(cs)        cout<<"Case "<<cs<<":\n"
#define lb               cout<<"\n";

#define vec vector
#define qu  queue
#define li  list
#define pq  priority_queue
#define em  empty

#define fori(i,a,b) for(int i=0;i<b;i++)
#define ford(i,a,b) for(int i=b-1;i>=0;i--)
#define forc(ch);   for(char ch:str)

#define sc1(a)         scanf("%lld",&a)
#define sc2(a,b)       scanf("%lld %lld",&a,&b)
#define sc3(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define sc4(a,b,c,d)   scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sc5(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)

using namespace std;

void solve(ll n){

    ll temp_n=n;

    temp_n--;

    for(ll i=0; i<n-1; i++){
        cout<<"(";
    }
    cout<<"sin(1)+"<<n<<")"; //Segment 1.

    str s="sin(1-sin("; // if n>1 this one is using for the template.


    for(ll i=2;i<=n;i++){ //main loop.

        str temp;
        temp.clear();
        temp=s;


        for(ll x=2; x<i;x++){ //This one creat middle of Every part.

            if(x%2==0){ //' + ' for even ' - ' for odd.
                temp+=to_string(x);
                temp+="+sin(";
            }
            else{
                temp+=to_string(x);
                temp+="-sin(";
            }

        }

        temp+=to_string(i);

        for(ll y=1;y<=i;y++){ //for closing ' ) ' every equation.
            temp+=")";
        }

        cout<<temp; //print each segment.

        if(temp_n > 1){
            cout<<"+"<<temp_n<<")"; //Printing every segment last digit with out 1.
        }
        temp_n--;
    }

    cout<<"+1";lb//This one for end.
}

int main()
{
    ll n;
    sc1(n);

    if(n>1){
        solve(n); //solve function.
    }
    else if(n==1){
        cout<<"sin(1)+1";lb //for 1.
    }

    return 0;
}

Друзья, если вам не принципиально какую задачу порешать вечером - ищите другую.
Решение к этой задаче легко придумать за 5 минут... А потом искать 4 часа ошибки (ибо они будут 100%)
Удачи.

Tree for minimum is enough.

hm.ok



Edited by author 25.08.2020 03:14

Why WA#8?

How to solve this problem using c++ ? My pick is  #MLE 14. I use (10^5 + 1000)*4 + 10^5 * 2
 = 589,84375 kilobytes of memory. I have no idea how to optimize it even more(

Edited by author 20.08.2020 02:34

Edited by author 20.08.2020 02:34

My AC code gives "No" on the following testcase due to the overflow
1000000000 1000000000 1000000000
0 0 0