[PYTHON] J'ai participé à AtCoder (édition ABC169)

salut! C'est le domaine de Roadrice, étudiant en master de bioinformatique! Cela fait un moment que je ne suis pas mort de la dernière fois, mais depuis que j'ai participé à ABC169, veuillez noter l'entrée.

Problème A

La multiplication jusqu'à 3 chiffres est apprise par la 3e année de l'école élémentaire selon les directives pédagogiques actuelles.

Ma réponse

A.py

A,B = map(int, input().split())
print(A*B)

Problème B

Je l'ai implémenté exactement comme il a été écrit une fois.

B.py

N = int(input())
A = list(map(int, input().split()))

ans = 1
for i in range(N):
    ans *= A[i]

if ans <= 1e18: print(ans)
else: print(-1)

Le résultat est "TLE". Les nombres sont gros, non?

S'il y a 0 dans l'entrée, la réponse est 0 à ce moment, donc s'il est jugé s'il y a d'abord 0 dans l'entrée, "0" est sorti sans multiplication et le processus se termine, 10 ^{18 pendant le calcul. Je pensais que ce serait plus rapide si je le cassais et que je produisais -1 s'il dépasse </ sup>, alors j'ai écrit comme suit.}

B.py

N = int(input())
A = list(map(int, input().split()))

ans = 1
flg = True

if 0 in A: print(0)
else:
    for i in range(N):
        ans *= A[i]
        if ans > 1e18:
            flg = False
            break

    if flg: print(ans)
    else: print(-1)

En passant, cela a réduit le temps de calcul du maximum de «2206 ms» à «56 ms». Il sera considérablement plus rapide avec un peu d'ingéniosité.

Problème C

Je savais que c'était une histoire en virgule flottante, mais cela n'a pas fonctionné ... Je n'ai pas suffisamment étudié les technologies de l'information ...

Problème D

J'ai utilisé C ++ pour ce problème. Vous pouvez maximiser le nombre d'opérations en procédant comme suit.

Tout d'abord, nous factorisons le * N * donné.

N = a^{6} \times b^{4} \times c^{3}  

Soit z = a ^{1 </ sup>. Remplacez N par N / z. Comme le même z ne peut pas être sélectionné, le plus petit suivant a 2 < Sélectionnez / sup> pour z. Remplacez N par N / z.}

N = a^{3} \times b^{4} \times c^{3}  

Il se divise toujours à z = a ^{3 </ sup>. Remplacez N par N / z.}

N = b^{4} \times c^{3}  

Ensuite, divisez par z = b ^{1 </ sup> ...}

Divisez à plusieurs reprises par les 1ère, 2ème et 3ème puissances des facteurs premiers, et si les facteurs premiers sont épuisés en * N *, divisez par les 1ère, 2ème et 3ème puissances des facteurs premiers suivants. Il vous suffit de répéter le processus.

Ma réponse

D.cpp

#include<bits/stdc++.h>
using namespace std;

vector<long long> pri_fac(long long N){
    vector<long long> yakusu;
    long long now = 0; 
    long long a = 2;
        while(N >= a*a){
            if(N%a == 0){
                yakusu.push_back(a);
                 N /= a;
            }else{
                a++;
            }
        } 
    if(N != 1) yakusu.push_back(N);
    return yakusu;
}

int main(){
    long long N;
    cin >> N;

    vector<long long> vec_all;
    vec_all = pri_fac(N);

    if(N == 1) cout << 0 << endl;
    else if(vec_all.size() == 1) cout << 1 << endl;
    else{
        long long now;
        now = vec_all[0];
        vector<long long> unique_count;
        unique_count.push_back(1);
        for(long long i=1;i<vec_all.size();i++){
            if(vec_all[i] != now) unique_count.push_back(1);
            else unique_count[unique_count.size()-1]++;
            now = vec_all[i];
        }

        long long ans = 0;

        for(long long i=0;i<unique_count.size();i++){
            long long j = 1;
            while(j <= unique_count[i]){
                ans++;
                unique_count[i] -= j;
                j++;
            } 
        }

        cout << ans << endl;
    }
    return 0;
}

Quand * N * est 1 ou un nombre premier, je ne voulais pas de bogue, donc je gère d'abord les exceptions. Pri_fac est une fonction qui effectue la décomposition des facteurs premiers et renvoie les facteurs premiers au vecteur.