()

Is it rated?

Yep,but for me it is a right time to have supper,so maybe I'll be hungry solving the problems.

Even I'm Chinese, I still want the round to be later. The darkness has given me dark eyes, but I use them to find bugs.

Thanks to the time,I can participate for an official contest after a long period of time.

Thanks to the contest writers.

You can simply just open the "Complete Problemset" page!

you too

The solution is max{N, 2 * (N — positionOfTheFirstStaircase), 2 * (positionOfTheLastStaircase + 1)}

I used BFS and start point is (floor,room)=(0,0)(0,s.size()-1)(1,0)(1,s.size()-1)

there are only two possible cases either you start from leftmost room and use rightmost stair or start from rightmost room and use leftmost stair. ans is maximum of these two cases.

:(

I can totally feel you bro... i wrote a solution which worked for 10^6 test cases that I randomly generated using Chelper and my code passed without any error, but this case 5 totally took my life.

try this if you use exgcd approach:

1000000000000 90000000000000007 100000 77777

Answer should be

899999922230 99991 99999977779

My exgcd template failed on this because of long long overflow when multiplying

If you really want to solve that equation, maybe you could try something like this:

The goal is to find the smallest possible $$$y$$$ such that $$$wx+dy=p$$$.

We could first divide both $$$w$$$, $$$d$$$ and $$$p$$$ by $$$gcd(w, d)$$$ then $$$w$$$ and $$$d$$$ become coprimes.

We take $$$mod\ w$$$ and the equation becomes something like $$$dy=p \ (mod\ w)$$$. Thus $$$y=p\times {d}^{-1}\ (mod\ w)$$$.

For coprimes, modular inverse always exists and could be found by extended euclidean algorithm.

first check if the (p % (gcd of(w,d) != 0) then the answer -1.

then you should know the min number of draw matches you need cuz of (d<w) and more number of winning matches.

so you should precalculate this : Mod[ (i*d) % w ] = min ( Mod[ (i*d) % w ] , i ) for each (0 <= i <= w-1) calculate def=(p%w) and now you know the min number of draw matches you need to achieve ( def = (Mod[def] * d) % w )

the number of draw matches is Mod[def] and the number of winning matches is ( ( p — (Mod[def]*d) ) / w ) just make sure the sum of them less or equal to n then print them

Diophantine equations i guess.

I have tried the diophantine equation but no luck. What a bad problem for C..

I tried to solve it using extended GCD algorithm. This helps you to find (x, y) such what:

wx + dy = p, though after finding a initial value of (x, y) you need to somehow convert it into a valid solution (Here is where I got totally stuck)

You can use extended Euclidean algorithm to find x and y(keep in mind there can be more than one solution to the linear combination, so you need to take the one where y is minimal while still being >= 0).

brute force would work cuz small contraints on w or d

binary search and binary search and more binary search... no number theory no nothing only binary search... at least that's how I did it

https://codeforces.me/blog/entry/70516?#comment-549838

After contest, I solve F and G by myself, so C is the hardest for me...

We ca use Binary Search to find minimum difference, The Min. element or Max. element in the final array after applying operations will be from the original array.

I guess, E is ternary search within binary search.

i solved it greedy

increase / decrease elements which frequency is less to the next element

I solved it by greedy.I hope it passes the main system cases too!

We also need 30 more minutes to submit more problems :)

so is the system testing delayed by 30 minutes or it'll start normally?

We can employ brute force. Iterate over all possible numbers of draws from zero to $$$W-1$$$. We can easily compute the number of wins necessary with a given number of draws and whether this configuration is possible (this requires that $$$P = Di$$$ mod $$$W$$$, where $$$i$$$ is the number of draws, and that $$$(P - Di) / W + D$$$ is at most $$$N$$$, since we need to have an integer number of wins and can have at most $$$N$$$ wins and draws). As soon as we find a working configuration, just print it and exit.

We now prove that this is optimal--in other words, this will find a solution if one exists. Note that if there exists a solution $$$(x, y, z)$$$ with $$$y \geq W$$$, $$$(x+D, y-W, z)$$$ is also a valid solution. Moreover, the total number of wins and draws in the second solution is lower than in the first, meaning the second solution is more likely to fit within our $$$N$$$ game limit. Thus, any optimal solution will have $$$0 \leq y \lt W$$$, as desired, so our solution will find a solution if one exists.