Блог пользователя Vladosiya

Автор Vladosiya, история, 2 года назад, По-русски

Привет! В 18.11.2022 17:35 (Московское время) начнётся Codeforces Round 834 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, myav, Gol_D, Aris, Gornak40, senjougaharin и Vladosiya.

Также большое спасибо: mumumucoder, Enkognit, orloffm, TeaTime, ilyamzy, Olympia, moonveil, 74TrAkToR, molney, elseecay, bigDuck, Nickir, Be_dos, OAleksa за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.

Всем удачи!

UPD: Разбор

  • Проголосовать: нравится
  • +114
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Div 3 after a long time...

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

YEAHHH div 3 is the best opportunity to become a specialist.. ;D

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

As a tester give me contribution

»
2 года назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

OMG DIV 3! HOPING FOR GLACEON COLOR!!! never, Leafeon. is the best :sunglasses:

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Omg blue round

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

Div.3! Hope to Specialist!

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Aleksamaster is the best tester , Oro najjaki

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Aleksamaster is the best tester , Oro najjaki

»
2 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Among us

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

End term Exams and contest on same day :(... I guess I'll miss my becoming pupil chance ..

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Best of luck to everyone writing the contest!

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

GL

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I swear, this time I am going to change color!

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

OMG Blue Round

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Time to change my rating.

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Спасибо bigDuck за тестирование.

»
2 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

I will try my best to become expert.Only need 20 scores,best wishes.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

OMG div 3 , hoping for big +ve delta

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Never miss the rounds that written by ITMO University team

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

where I will get the contest link

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Go to the contest section Codeforces page. Find round 834 and register before the contest

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Good luck for everyone . Do your best to be the best !!

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I didn't compete with you a month ago, so i am in a hopeless situation, what should i do?

»
2 года назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

It would be nice to finally fix language selector issue and remove excessive use of flags.

Sources with supporting arguments:

Codeforces Language Picker -- chrome extension to see how fixed codeforces language picker would look like.

Please support the initiative and stop reinforcing poor UX practices.

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Good luck everyone :)

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Goof luck everyone!!!

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Hope to become an Expert.

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

What if it is my 5th rated round? Will I become trusted participant if I will solve a problem in it?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

great

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I hope to become a specialist soon

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This round seems to be a more interesting one:)

»
2 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

How to solve G?

  • »
    »
    2 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +12 Проголосовать: не нравится

    I used a greedy idea:

    Starting from the reverse direction...

    However, I haven't proved this idea in the contest, so I'm not sure about the systests. If someone else who have proved it can mention it here, then it would be helpful.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why max unused? We want the minimal permutation, so should not we place minimum in the range?

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Notice that I am iterating from index N to 1, so using the maximum ones at higher indices is more optimal than using the minimum ones.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      It seems logical...

      Everytime you pick the maximum possible choice and you ignore smaller values which have higher chances of being used in another pair than the max value ($$$1$$$ is smaller than $$$n-1$$$ values, $$$2$$$ is smaller than $$$n-2$$$ values, and so forth...)

      So even if it can be used somewhere else also, no problem because there is another smaller value you can put there (and if there isn't, it's impossible to construct the permutation).

      Getting the max guarantees the smallest permutation also.

  • »
    »
    2 года назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    I used a Maximum Segment Tree.

    • Initialize int[] answer of length n which will store our final permutation. On every odd position(0 based indexing) fill the elements of int[] b. Because we want minimum number to be in front position, so it makes sense to keep the maximum element on the second position.
    • Now we have filled half of answer array. Now we iterate integers from n to 1 and check if its not present in answer, find the right_most element in answers array which is less than this current number. So we can safely place this number on left hand side of the found number. Now delete this number. This type of operations can be done by segment trees.

    My solution is not clean as wrote in hurry in contest and its a newbie's code. My AC 181520850

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    If you are a braindead grey (like me) and never thought to solve the problem backward, you can also binary search on a lazy add/min segtree.

    https://mirror.codeforces.com/contest/1759/submission/181510473

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Solution for G:

    From $$$i=n/2 \space to \space1$$$,for each $$$b[i]$$$,find $$$max(x)(x<b[i],x≠b[j])$$$ .

    Proof:

    Note $$$X=max(x)(x<b[i],x≠b[j])$$$.

    Consider $$$"... Y\space b[j] ... X\space b[i] ..."$$$ and $$$"... X \space b[j] ... Y\space b[i] ..."$$$.Because $$$X$$$ is the largest number less than $$$b[i]$$$,we get $$$X>Y$$$,the former has a smaller lexicographical order.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the correct approach to solve problem C?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can consider cases like: a == b then answer is 0 distance between a and b is >= x then answer is 1 distance between a and l or a and r is more then x and then distance from that end is more then x ( to the b ) then the answer is 2 and the last case is to make the deistance to one of the endpoints equal to at least x, and this just adds 1 to the previous case, so the answer is 3 in the last case, if you can't do that than the answer is -1

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Check if ans==0

    If possible use 1 step, else

    if possible go to left or right end, then to b, else

    if possible go to left end then right end, or to right end then left end, then to b.

    else not possible.

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I felt problem D to be tougher than E & G :|

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Me the same. I wasted too much time in D and then found out E was much easier to figure out. But it was too late... :(

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell me what's wrong in my submission of D

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I am not sure what is your code doing. But i found a test case:

    1
    513943340 921893439
    
    Brute Force Output: 
    256971670000000000
    
    Obtained Output: 
    462549006000000000
    
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can any one tell, what would be the difficulty level for the problem D?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone explain problem c and d

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

    My solution for D:

    k zeros at the end of a number means that this number can be represented as 10^k*a, where a is some number. 10 = 2 * 5, therefore, in the answer we need to maximize the number of pairs {2, 5}

    1) Decompose n into prime factors and count the number of 2 (let it be q2) and 5 (let it be q5). If q5 > q2, then we need to add q5 - q2 twos in the price increase coefficient. If q2 > q5, then q2 — q5 fives. If q2 == q5, it means that we cannot "collect" tens from two numbers and add a zero to the end of the answer.

    2) After that, I started picking up a number from [1; m]. We need as many 10 as possible in the answer multipliers, so I multiply the number (2 or 5) that I lacked to create pairs with multipliers of the number n, abs(q5 - q2) times by itself. tmp = (q5 > q2 ? 2 : 5)^abs(q5 - q2)

    3) Then, I need to maximize the quantity of 10 at answer and, if there is solutions with the same number of zeros, need to get maximum. So we can increase tmp variable. To increase the number of tens, you need a number that can be represented as 10^k * a. This is easy to do if you take a digit of the highest digit and add to it (the length of the number - 1) zeros. For example, when m = 21345, you need to take 20000. So we have to do something like this:

    r = m // tmp
    t = int(str(r)[0] + (len(str(r)) - 1) * '0')
    tmp *= t
    

    4) When working with the tmp variable, it is necessary not to forget that it cannot be more than m, so it is necessary to set conditions that tmp <= m everywhere you are increasing tmp.

    The answer is n * tmp or n * m if there isn't solutions with zeros at the end.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My code return negative value in problem D but i am doing only multiplication in my code. can someone please help me with that

here is my submission 181501309

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve F?

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    Observation 1. The maximum answer is $$$p-1$$$, One case where this happens is where the number is a single digit.

    Observation 2. A full carry across one or several digits happens only once at most.

    Now think of it like this. How many steps do we need when our number is 0? That's $$$p-1$$$. Now, how many steps do we need when we have a few more digits existing in the number, smaller than the last digit? Might be smaller than that, but we may still have to run a full cycle. For this reason, we manage two variables, $$$\mathbf{pp}$$$ and $$$\mathbf{pk}$$$. $$$\mathbf{pp}$$$ is the smallest number connected as a continuous group with $$$p$$$, $$$\mathbf{pk}$$$ is the same but it is for the last digit. These two variables serve as boundaries. To be precise, $$$\mathbf{pp}$$$ serves as the boundary before the carry, $$$\mathbf{pk}$$$ serves as a boundary after the carry. So, you should be very well able to case-work with $$$\mathbf{pk}$$$ on whether we need a carry or not. Now the rest is just implementing the carry, and fiddling with these two variables (and the last digit).

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Solution for F:

    Note $$$k=a[n]$$$,consider $$$k->k+1->...$$$

    Case1:

    $$$k->k+1->...->p-t$$$

    In this case, there is no carry bit.$$$0,1,..,k-1$$$ must appear in $$$a[]$$$.

    $$$p-t$$$ is the largest number that does not appear in $$$a[]$$$.

    Case2:

    $$$k->k+1->...->p-1->0->...->k-t$$$

    In this case, you should recalculate $$$a[]$$$(consider carry bit),note it as $$$b[]$$$.

    $$$k-t$$$ is the largest number that does not appear in $$$a[]$$$ and $$$b[]$$$.

»
2 года назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

Accidentally hacked jiangly submission with Ticket 16429 from CF Stress :)

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D ?? Made me drop the contest..

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Just find out how many 2 and 5 you get from m and (1<=x<=n) if(x==1) answer will be m*n; otherwise m*x;

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Sorry can you elaborate ??

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        You'll get $$$n$$$ 0's in the suffix of the answer if the factorization of $$$n * k$$$ ($$$1<=k<=m$$$) contains atleast n fives and n twos. Greedily check if you can get $$$x$$$ zeroes in the suffix of the answer for every x uptill about 18 should suffice (since n * m is atmost 1e18).

        For example, if you want $$$x=5$$$ and $$$n$$$ contains $$$4$$$ 5s and $$$3$$$ 2s in it's factorization. Then you require such a k that has atleast $$$x-4$$$ 5s and $$$x-2$$$ 2s

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could someone please explain why my code for E fails on test case 3? https://mirror.codeforces.com/contest/1759/submission/181515762

I have used the following approach, there may be at most 3 orders of choosing potions whenever we encounter an astronaut with health greater than the humanoid's health, and they will be GBG BGG GGB

The final answer should be the maximum of the number of astronauts we can defeat using one of the three orders. Please point out the logical inconsistency in my approach or provide an example where my code fails.

(the recursive way to solve this did strike my mind, but I decided to do it this way as it seemed simpler)

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    As the humanoid can gain more health as it consumes an astronaut, you should iterate until you cannot consume an astronaut anymore instead of binary search the position at the beginning. After that you will drink a potion then try again that strategy. There are 3 ways to drink potion (2,2,3), (3,2,2) and (2,3,2) so just try all of them.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody tell me what's wrong with my B code? (Pretest 4 WA)

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I figured it out, I thought the original permutation's size can't be over 50, but the problem statement never actually said that, only the found elements can't be more than 50

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

1759A - Да-да?

Здесь что то есть
»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Personally to me, it felt more like a div4 round. The maximum difficulty rating for the problems of this contest should be around 1700 or 1800 I guess.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Someone please tell me how the humanoid can absorb the astronaut with power 15 in the case 7 of Problem E. It says that the humanoid can absorb an astronaut with power strictly less humanoid power. It confuses me a lot.

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Take a look at submissions of the rk8 NightSky_Yozora.

Obviously, there are 4 coding styles in his submissions:
Problem A, B, C is solved by the first person;
Problem D by second;
Problem E by third;
Problem F, G by fourth.

it's a violation of the rules, isn't it?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Sir, what about Sneh_Patel_0701 he has cheated in previous rounds too. But didn't get caught. Now he is going to become expert. Is there any punishment for them?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone point out what I may be doing wrong? What edge case I may be missing?

https://mirror.codeforces.com/contest/1759/submission/181520511

»
2 года назад, # |
Rev. 6   Проголосовать: нравится +8 Проголосовать: не нравится

1759D - Сделай круглым

Greedy approach : We will try to append as many 0's at the end within given constraint How to find it ?

Let's take input examples : 6 11

  • We can have 30 60 90 120 ...
  • But only 30 and 60 falls within constraint
  • 6*5 = 30, k = 5
  • 6*10 = 60, k = 10
  • 6*15 = 90, k = 15 not possible

Now we will build our answer by checking if I append zeros can I get some k such that it falls under constraint, once we can't append 0's we will break loop

How to do it? How to find possible values of k? Well it's easy, we can use some mathematics


We will check if I can have some possible number as z*10 z*100 z*1000 and so on... z [1, 9] z should be minimum possible as we are using greedy
we have our n as 6 so to append 0 at the end I can have z*10
n   = 2*3
ans = z*10
so we have ans = n*k, 1 <= k <= m
n = 6 k = 5  z = 3 ans = 30
n = 6 k = 10 z = 6 ans = 60

How to find k ? Let g = gcd(x, n) = (10, 6) = 2 then k = x/g = 10/2 = 5, k can take minimum value as 5 within given constraints But as we have to find max answer if we append some zeros so we will find k as k = (11/5)*k k = 10

Here's my code

#include <iostream>
#define int long long int
     
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int t = 1;
    std::cin >> t;
    while(t--){
        int n, m;
        std::cin >> n >> m;
        int x = 10, ans = n*m;
     
        while(1){
            int g = std::__gcd(x, n);
            int k = x/g;
            if(k <= m){
                ans = k*(m/k)*n;
            }
            else
                break;
            x *= 10;
        }
     
        std::cout << ans << "\n";
    }
}

Thanks :), You can ask doubt

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can u explain little more how exactly u getting logic to finding k?

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      k = x/gcd(x, n) x goes from 10, 100, 1000, ...

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I tried doing this but it was always giving wrong answer in C++ (probably some overflow issues or something like that) but it worked fine in Python

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hi, @djay24 What's your intuition behind (m / k) .?? like, you used k = (11/5)*k, why are you doing so, can you explain.?

    Thanks in advance.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      1 <= k <= m Initially k is minimum possible value it can take within given constraints So k can take values from k, 2*k, 3*k, 4*k, ... z*k, I have to find such z such that z*k is maximum possible but less than equal to m, so I am multiplying by (m/k) factor... That's why initially k = 5 but after we can see k = 10 is best answer so k = 5*(11/5)

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

Is there a problem with hacks in problem F? Any hack in this problem still in the waiting process. Screenshot-2022-11-18-200635
Also Some of them give unexpected verdict. MikeMirzayanov

Upd: Hacks still in waiting state after 6 hours problem F hacks

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E and G are far far easier than D (did'nt read F yet)

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

E and G are far far easier than D (did'nt read F yet)

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Has anyone solved E with a memorized dp? the recursive approach is very simple but i cant seem to get my head around implementing a dp solution.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What is your state? I had an iterative dp where $$$dp[i][j][k]$$$ denoted the max cost achievable till index $$$i$$$ if you take $$$j$$$ green potions and $$$k$$$ blue potions in total. While transitioning, I tried to take $$$l$$$ green potions and $$$m$$$ green potions in the $$$ith$$$ step. If the cost achievable without taking these $$$l$$$ potions and $$$m$$$ blue potions was greater than $$$a[i]$$$ then I greedily add $$$a[i]/2$$$ to my answer and then multiply by 2 and 3 on the basis of how many $$$l$$$ potions and how many $$$m$$$ potions I took.

    Submission

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks, makes a lot of sense! i had the same 3 states but had trouble differentiating the cases where the potions were taken before or during the round.

»
2 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

177670435``

````````Please, Who can help me to find out the queetion of problem D. I guess my code's part of maximal price of several possible variants is wrong.because the Checker Log told that expected: '874999993000000000', found: '749999994000000000'.

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
typedef long long ll;
ll m,t,n,cnt1,cnt2,sy,i;
ll qpow(ll a,ll b){
    ll sum=1;
 while(b){
if(b&1) sum*=a;
 else a=a*a;
 b>>=1;
 }
return sum;
}
signed main()
{  
 cin>>t;
 while(t--){
cnt1=0;cnt2=0;
cin>>n>>m;
ll good=n;
while(1){
if(n%2==0) cnt1++,n=n/2;
if(n%5==0) cnt2++,n=n/5;
if(n%5!=0 && n%2!=0) break;
}
if(cnt1>cnt2){
 sy=cnt1-cnt2; i=1;
 while(i<=qpow(5,sy)&&i<=m) i*=5;
 if(i>m) i=i/5;
 if(i>qpow(5,sy)) i=i/5;
 
 while(i<=m) i*=10;
 i=i/10;
 ll tmp=i;
while(i<=m) 
 i=i+tmp;
 i=i-tmp;
 cout<<good*i<<"\n";
}

else if(cnt1<=cnt2){
 sy=cnt2-cnt1; i=1;
 while(i<=qpow(2,sy)&&i<=m) i*=2;
 if(i>m) i=i/2;
 if(i>qpow(2,sy)) i=i/2;
 while(i<=m) i*=10;
 i=i/10;
 ll tmp=i;
 while(i<=m) 
 i=i+tmp;
  i=i-tmp;
  cout<<good*i<<"\n";
} 
} 
 return 0;
}- - 
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My feedback to the round authors (just for problems A-D (problems I managed to solve in the contest)):

A: Easy implementation problem, the problem statement could've been written more simply because I needed to look at the examples to understand the problem without spending like 5 minutes. It shouldn't be like that since this is Div.3 A problem.

B: OK problem, nothing else to say.

C: Good problem, even though I don't prefer problems with $$$l,r$$$, and many if statements like this one. I like the problem.

D: Best problem (rating $$$\leq{1400}$$$) along with 1748B - Разнообразные подстроки in the past few weeks in my opinion. It's always interesting to solve number theory problems.

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

The feeling when Div. 3 round was more problematic for you than Div. 2 round XD

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i have a problem.In problem e ,java,i use the same algorithm to solve this problem,but three different sorting methords(priorityqueue, Collections.sort,Arrays.sort),the first two is accepted,but the third one has TLE.Can anyone figure it out?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Solutions were already there on YouTube I check the timings. People just copied from there. So unfair

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Goof luck everyone

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone please explain me the approach for problem C? I can't figure it out!

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you only have the following options:

    1. if a is already at b -> answer is 0
    2. if difference between a and b is >= x -> answer is 1
    3. from a go to l (if possible), then to b (if possible) -> answer is 2
    4. from a go to r (if possible), then to b (if possible) -> answer is 2
    5. from a go to l (if possible), then go to r (if possible), then to b (if possible) -> answer is 3
    6. from a go to r (if possible), then go to l (if possible), then to b (if possible) -> answer is 3
    7. if none of the above is possible, then answer is -1, otherwise it is the minimum of all the cases

    for steps 3-6, we chose either l or r and not any other temperature because its always efficient to use an operation go to the farthest possible index.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I like this competition very much. The F and G questions are very simple, which is simpler than the level questions in div2. They do not involve advanced algorithms and data structures, and their meanings are very clear.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i wasn't able to solve F without implicit segment tree with lazy propagation and binary search on it(got MLE 2 times xd)

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I remember it was a line segment tree binary, someone did it, maybe you wrote it wrong.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        yeah, memory consumption was huge because i didn't use shared ptr or vector, just raw pointers..

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please clarify if it was rated? I participated in the contest and solved A but I was not rated. What are the rules for being rated?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The contest doesn't even show in my contest tab. What is the reason for that? Can someone please clear up the confusion?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

NightSky_Yozora was obviously cheating, plz do something.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is this contest was rated for participant whose rating < 1000 ??

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

There are still about 40 hacks stuck at "In queue" or "Unexpected verdict" state, despite the fact that the final testing has already been conducted. This is not the first time such a situation arises.

I think that such occasions should be automatically reported to contest managers and, in general, should block the final testing unless fixed.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why my rating is still not updated until now?

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Now it`s time for the Ultimate Question of life, universe and everything: Is it rated?

»
2 года назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

All Questions were mathematical as always. No concept used of DSA. Disappointing contest

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Nice problems! I love the round

I hope that I can be specialist xd

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Has this contest turned unrated??? Why the ratings are not updated yet

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please update the rating

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

Hello, 2 hours ago I got a message that tells my solution for problem C matches with some other participants. Also, this round will be unrated for me and it shows I am out of competition. My solutions are skipped also.

I checked their submissions and found some similarities in logic and I think this is normal as thousands of people are participating here. But their code writing style and solution for this problem are totally different.

Also, this happened to me for the first time. I don't know what to do! Help me if anyone can! Thanks in advance.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry to hear that. You may send emails to the codeforces official account and provide exact evidence to show you didn't share code with other participants. You may get the round into a rated one finally if you are resonable.

    Hope that will help you.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    One contest doesn't mean everything.... Try in next contest.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have been skiped , i have not cheated , what i should do to prove that

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You have been skipped several times. Just admit it and don't cheat again.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      noooooo he didn't cheat of course he just keeps getting accidentally skipped /s

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When is editorial going to be posted?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://mirror.codeforces.com/contest/1759/submission/182444103 I am Getting Runtime Error in Problem F but not able to find it , It would be great if anyone can help .