[PYTHON] Codeforces Round # 671 (Div. 2) Bacha Review (9/22)

This time's results

Impressions of this time

It was a wasteful time because I was impatient and my thoughts became messy. I came up with the E problem in the idea game, but I couldn't secure enough time.

After all ** the accuracy and intuition of consideration is still poor **, so I think there is no choice but to solve more problems and refine them.

Problem A

(Hereafter, the first Raze is R and the second Breach is B.)

** Pay attention to the last remaining number **. If the number of remaining ones is odd, R wins, and if not, B wins. At this time, if there are an odd number, the odd number will remain in the end, so it is sufficient to leave the odd number so that the first R will win, and if there is at least one odd number in the odd number, R will win. I will. Also, if there are an even number, the even number will remain in the end, so it is sufficient to leave an even number so that B in the second attack wins, and if there is at least one even number in the even number, B wins. I will.

** I made a mistake in the number of outputs and issued 1WA **.

A.py

for _ in range(int(input())):
    n=int(input())
    a=2**n+sum(2**i for i in range(1,n//2))
    b=sum(2**i for i in range(n//2,n))
    print(a-b)

Problem B

It was non-trivial, so I solved it from other problems. It is important to ** perform experiments accurately ** for such graphic problems.

A $ n $ staircase made using only $ n $ squares is called a nice (at first, it was ** misread ** as a rectangle). We will conduct an experiment considering the case where this nice staircase can be made.

At this time, if you do not make ** as large a square as possible ** as shown in the figure below, you cannot make only $ n $ squares ($ \ because $ smaller squares will definitely exceed $ n $ pieces. Because it will end up). That is, it looks like the figure below.

The above figure shows the time when $ n $ = 1 ~ 7, but it holds only when $ n $ = 1,3,7. Also, it is clear that it holds for odd numbers, and if you make a large rectangle when $ n = 2k + 1 $, ** the rest will be a rectangle of two sizes $ k $ **. I noticed. In other words, when the size of the stairs that can be created is $ a \ _i $, it must be $ a \ _ {i + 1} = 2a \ _i + 1 $ ($ a \ _ 0 = 1 $).

Also, the number of tiles given is at most $ 10 ^ {18} $, and $ a \ _i $ grows faster than the geometric progression, so ** a nice staircase size is $ a \ _0 $. It is enough to find from to $ a \ _ {29} $ **.

Therefore, what you want to find is the number of ** different nice stairs ** that can be made for a given number of tiles $ x $, and different stairs have different stairs, so make from small nice stairs. You can make them in order until they run out. Also note that since you are given the number of tiles, you should subtract $ \ frac {a \ _i (a \ _ i + 1)} {2} $ from $ x $.

B.py

cand=[1]
for i in range(100):
    cand.append(cand[-1]*2+1)
    if cand[-1]>10**18:
        break
for i in range(int(input())):
    ans=0
    x=int(input())
    for i in cand:
        j=i*(i+1)//2
        if x-j<0:
            break
        else:
            x-=j
            ans+=1
    print(ans)

C problem

During the contest, I was rushing to think of a strange solution, but when I'm calm, it's not that difficult.

During the contest, I first considered the following cases.

(1) When everyone's rating is $ x $ You can infect without having to hold a contest once.

(2) When the total rating of all people is $ nx $ You only have to open the contest once because you can make everyone equal to $ x $ by setting the total amount of change to 0.

(3) Other than (1) and (2) ** You can make all but one person ** $ x $, and you can infect everyone with two operations.

Actually, (1) and (2) are correct, but ** (3) is not always correct **. During the contest, I took AC thinking that if I adjusted the already infected person well, it would be enough to do it once, but logically speaking ** If at least one person is already infected, that person It can be said that all people can be infected at once ** by $ x $ other than. Probably, if I could pay attention to the part of ** other than one person, I could solve it correctly, so I felt that accuracy was important for the case classification.

C.py

for _ in range(int(input())):
    n,x=map(int,input().split())
    a=list(map(int,input().split()))
    if a.count(x)==n:
        print(0)
    elif sum(a)==n*x:
        print(1)
    else:
        if a.count(x)>0:
            print(1)
        else:
            print(2)

D1 problem

Since they are all different, it is possible to use 0-indexed from the even-numbered largest one in descending order and the odd-numbered smallest one in ascending order. I think this is a very simple problem.

D.py

n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import deque
b=deque(a)
l=n//2-1 if n%2==0 else n//2
ans=[]
while len(b)>=2:
    ans.append(b.pop())
    ans.append(b.popleft())
if len(b)==1:
    ans.append(b.pop())
print(l)
print(" ".join(map(str,ans)))

D2 problem

It seems that the code implementation of the policy that was finally AC was wrong, ** I could not determine whether the policy or the implementation was wrong **. In the future, I would like to improve my thinking ability so that I can implement it after thoroughly setting the policy.

The maximum number of ice balls you can buy when arranged in the following order is (ABC178-F is a similar subject).

If the maximum number of ice balls of the same price is $ [\ frac {n} {2}] $, the maximum value at D1 can be achieved, and if it is more than that, the maximum number will be whatever you arrange. I thought I couldn't achieve it, so I arranged it this way. ** I thought there was no other rational arrangement **, so I chose this arrangement.

Looking at the answer, when you can buy $ m $ ice balls, there are smaller combinations of $ m + 1 $ ice balls, so ** the method of searching for $ m $ by binary search ** method I was taking it. If there is an assumption ** when you can buy ** $ m $ ice balls **, there should be no reason to think of binary search from the combination of ** monotonicity and maximum value **, so you have to learn the typical. felt.

D.py

n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import deque
b=deque(a[:n//2])
c=deque(a[n//2:])
ans=[]
while len(b) or len(c):
    ans.append(c.popleft())
    if len(b)>0:
        ans.append(b.popleft())
#print(ans)
l=0
for i in range(1,n-1):
    if ans[i-1]>ans[i] and ans[i]<ans[i+1]:
        l+=1
print(l)
print(" ".join(map(str,ans)))

E problem

Due to an implementation mistake, the solution was completed 10 minutes after the contest ended. I am very disappointed. When such a problem stabilizes, I think I can overcome the wall at once, so I will endure it.

When I experimented while looking at the sample, I thought that ** in many cases, it is not necessary to take lcm once **. Therefore, we arrange the adjacent numbers so that they are not relatively prime, but since we want to prevent the gcd of the adjacent numbers from becoming 0, ** pay attention to which number the adjacent numbers are multiples **. did. In particular, I paid attention to ** which prime number each number is a multiple of **. In other words, for example, you can build it as shown in the figure below (I think there are several ways to build it, but you can easily think of it by paying attention to ** which prime number is a multiple **).

You can make gcd other than 1 between any elements by ** assuming that the boundary part indicated by the yellow circle is multiplied by one prime number as above **. ..

Therefore, $ O (\ sqrt {n}) $ enumerates divisors and stores them in divisors, and $ O (\ sqrt {n}) $ performs prime factorization and stores them in prime. , The elements that are multiples of each prime number are extracted from the divisors in order from the front of the prime element and stored in the array ʻansthat is output as the answer. Also, since I want to save in ascending order and the speed of taking out is stable, I setdivisors and prime` to set respectively.

Also, you can store multiples of each prime number remaining in divisors appropriately in ʻans, but be aware that ** the boundary part must be done separately **. This can be easily achieved by later storing the product of the prime number you are looking at and the next prime number later in ʻans (see implementation for details).

Furthermore, it is necessary to take lcm as in the first sample ** when there are only two different prime factors and $ n $ is represented by the product of the prime factors **. In other cases, you can always meet the conditions with your own construction method.

E.cc

//Debugging options:-fsanitize=undefined,address

//Compiler optimization
#pragma GCC optimize("Ofast")

//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x is a container such as vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair

//n is not included
set<ll> divisors;//Set to store divisors(I want to delete it)

void make_divisors(ll n){
    FOR(i,2,sqrt(n)){
        if(n%i==0){
            divisors.insert(i);
            if(i!=n/i){
                divisors.insert(n/i);
            }
        }
    }
}

set<ll> prime;//Map that saves how many each prime number came out in prime factorization

//O(√n)
//Aligned(map is automatically sorted by key)
void prime_factorize(ll n){
    if(n<=1) return;
    ll l=sqrt(n);
    FOR(i,2,l){
        if(n%i==0){
        prime_factorize(i);prime_factorize(ll(n/i));return;
        }
    }
    //Even if the key does not exist in the map, it will be built automatically.
    prime.insert(n);return;
}

signed main(){
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll t;cin>>t;
    REP(_,t){
        ll n;cin>>n;
        vector<ll> ans;
        divisors.clear();
        prime.clear();
        make_divisors(n);
        prime_factorize(n);
        if(SIZE(prime)==2 and (*prime.begin())*(*++prime.begin())==n){
            cout<<*prime.begin()<<" "<<*++prime.begin()<<" "<<n<<endl;
            cout<<1<<endl;
            continue;
        }
        for(auto i=prime.begin();i!=prime.end();i++){
            deque<ll> sub;
            ll l,r;l=*i;r=0;
            if(++i!=prime.end()){
                r=*i;
                sub.PB(l*r);
                divisors.erase(l*r);
            }
            --i;
            auto j=divisors.begin();
            while(j!=divisors.end()){
                if((*j)%(*i)==0){
                    sub.PB(*j);
                    j=divisors.erase(j);
                }else{
                    j++;
                }
            }
            while(SIZE(sub)){
                ll p=sub.back();
                sub.pop_back();
                ans.PB(p);
            }
        }
        ans.PB(n);
        if(SIZE(prime)==2 and (*prime.begin())*(*++prime.begin())==n){
            REP(i,SIZE(ans)){
                if(i!=SIZE(ans)-1)cout<<ans[i]<<" ";
                else cout<<ans[i]<<endl;
            }
            cout<<1<<endl;
        }else{
            REP(i,SIZE(ans)){
                if(i!=SIZE(ans)-1)cout<<ans[i]<<" ";
                else cout<<ans[i]<<endl;
            }
            cout<<0<<endl;
        }
    }
}

F problem

I will skip this time