Zoznam úloh

7. Mining

Zadanie

Keď Andrej robil pravidelnú údržbu KSP-áckich agentov, zistil jednu hroznú vec. Každý z nich má taký procesor, ktorý má prvočíselný počet jadier! Takáto architektúra je už dávno zastaraná. Dnes sa takmer vždy používajú procesory, ktorých počet jadier je zložené číslo, pretože dokážu oveľa efektívnejšie paralelizovať úlohy.

Andrej teda nemá inú možnosť, ako nakúpiť do eráru nových agentov. Lenže čo urobí s tými starými? Krtko mu našťastie poradil výborný nápad: niektoré z nich môže použiť na ťaženie bitcoinu a zvyšné predať na Bazoši.

Úloha

Za každý počítač, čo predá, zarobí Trojsten toľko peňazí, koľko mal ten počítač jadier. Zároveň, celkový výkon počítačov, ktoré ťažia bitcoin, je súčin počtov jadier v každom počítači. Keďže Andrej je pedant, nepripustí, aby zárobok z predaja bol iný ako výkon na ťaženie. Zároveň je zjavné, že všetci chcú aby bol zárobok (a teda aj celkový výkon) čo najväčší. Aký najväčší môže byť?

Formát vstupu

V prvom riadku vstupu je číslo $t$ ($1 \leq t \leq 100$) udávajúce počet testov. Nasleduje $t$ testov, pričom každý má nasledujúci formát:

V prvom riadku testu je číslo $n$ ($1 \leq n \leq 95$). Nasleduje $n$ riadkov, pričom na $i$-tom z nich je prvočíslo $p_i$ ($p_i \leq 499$), a celé číslo $k_i$ ($1 \leq k_i \leq 10^{15}$), ktoré vyjadrujú, že v erári je $k_i$ agentov s $p_i$-jadrovým procesorom.

Označme $k$ celkový počet počítačov, $m$ celkový počet jadier a $P$ najväčší počet jadier v počítači. Formálne: $$ k = \sum_{i=1}^{n} k_i $$ $$ m = \sum_{i=1}^{n} p_i k_i $$

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4
$1 \leq k \leq$ $15$
$1 \leq m \leq$ $1\,000$ $2\times 10^4$ $10^7$ $10^{18}$

Formát výstupu

Na vstup vypíšte $t$ riadkov. Pre každý test vypíšte maximálny možný zárobok (rovnaký ako výkon), ktorý sa dá dosiahnuť alebo $0$, ak počítače nemožno rozdeliť tak, aby bol zárobok rovný výkonu.

Príklad

Vstup

4
5
2 2
3 1
5 2
7 1
11 1
1
17 2
2
2 2
3 1
1
2 7

Výstup

25
17
0
8

V prvom teste je optimálne riešenie predať počítače s procesormi $2+2+3+7+11=25$ a bitcoin ťažiť s procesormi $5 \times 5 = 25$.

V druhom teste jeden počítač predáme a druhý necháme ťažiť.

V treťom teste neexistuje spôsob, ako rozdeliť počítače tak, aby zárobok a výkon bol rovnaký (musíme sa zbaviť všetkých počítačov).

V štvrtom predáme $4$ počítače a zvyšné $3$ ťažia: $2+2+2+2=2 \times 2 \times 2$.

Bruteforce

Úlohou je nájsť najlepší spôsob, ako rozdeliť počítače na dve skupiny. Najpriamejší spôsob, ako toto docieliť je vyskúšať všetky spôsoby a zistiť, ktorý je najlepší. Budeme si pamätať, aký najlepší výsledok dokážeme dosiahnuť (na začiatku to bude $0$).

Každý z počítačov môže buď ťažiť alebo ho predáme. To sú dve možnosti na každý počítač, teda celkový počet spôsobov, ako rozdeliť počítače je $2^k$. Pre každý z nich sa pozrieme, aký je celkový zárobok (súčet predaných počítačov) a celkový výkon (súčin ťažiacich počítačov). Pokiaľ sú tieto dve čísla rôzne, tak ideme na ďalší spôsob. Ak sú rovnaké, tak vieme, že tento spôsob je vhodný, a teda aktualizujeme najlepší výsledok, ktorý si pamätáme.

Keďže celkový počet spôsobov je $2^k$ a pre každý sa pozeráme na $k$ počítačov, celková časová zložitosť je $O(k 2^k)$. Pamäťová zložitosť takéhoto prístupu je $O(k)$, lebo pre každý počítač si pamätáme, do ktorej skupiny patrí.

Niečo lepšie

O každom čísle vieme, že existuje práve jeden spôsob, ako ho rozdeliť na súčin prvočísel1. Keby sme si teda “tipli” odpoveď, tak vieme ľahko skontrolovať, či je “správna”. Presnejšie povedané, vieme zistiť, či sa dajú počítače rozdeliť tak, aby bol zárobok aj výkon rovnaký ako toto číslo $x$.

Aby bol výkon rovný $x$, tak vždy existuje iba jeden spôsob, ako môže vyzerať sada počítačov, ktoré ťažia. Tú nájdeme tak, že zistíme prvočíselný rozklad čísla $x$. V prvom rade overíme, či máme dosť počítačov, na dosiahnutie tohoto výkonu. Potom všetky ostatné počítače musíme predať, tak zistíme zárobok (ich súčet). Nakoniec overíme, či aj zárobok je $x$ a podľa toho rozhodneme, či toto $x$ vyhovuje.

Keď vieme, ako overiť jednu odpoveď, tak stačí len overiť všetky možné odpovede. Všimnime si, že maximálny možný zárobok je $m$. Skúšať $x$ väčšie ako $m$ teda nemá zmysel, lebo to určite nemôže byť odpoveď. Stačí teda vyskúšať všetky čísla od $1$ po $m$.

Prvočíselný rozklad sa dá jednoducho nájsť v čase $O(\sqrt{m})$. Potom v $O(n)$ môžeme zistiť, či máme z každého prvočísla dostatočný počet počítačov, a zároveň zistiť zárobok z ostatných počítačov. Celková časová zložitosť teda bude $O(m (\sqrt{m} + n))$. Pamäťová zložitosť je $O(n)$.

Zaujímavá myšlienka

Označme $$ P = \max_{i=1}^{n} p_i $$

Ako sme už zistili, zárobok a teda aj výkon nemôžu byť väčšie ako $m$. Teraz skúsime odhadnúť zhora súčet počítačov, ktoré ťažia. Keďže každý má aspoň $2$ jadrá, tak ich môže byť nanajvýš $\log_2(m)$. Zároveň, každý z nich má nanajvýš $p$ jadier, čo znamená, že ich súčet môže byť nanajvýš $T \leq P \log_2(m)$.

Uvedomme si ale, že celkový počet jadier sa nedá zmeniť. Z toho vyplýva, že ak opäť označíme $x$ zárobok (súčet predaných počítačov), tak platí $$ x + T = m $$ $$ x = m - T \geq m - P \log_2(m) $$

Vidíme, že $x$ je ohraničené aj zdola, teda môže nadobudnúť nanajvýš $P \log_2(m)$ hodnôt. Menšie $x$ sa už neoplatí skúšať, lebo ako sme zistili, už nemôžu vyhovovať.

Optimálne riešenie

Túto myšlienku môžeme ľahko zakomponovať do nášho lepšieho riešenia. Postup bude rovnaký, len nebudeme skúšať všetky $x$ od $1$ po $m$, ale začneme na $m - P \log_2(m)$. Ešte je tu ale jeden problém, a to že hľadať prvočíselný rozklad čísel rádu $m \approx 10^{17}$ nie je jednoduché.

My však nepotrebujeme hľadať celý rozklad, pretože keby malo byť toto číslo deliteľné prvočíslom väčším ako $P$ (alebo ľubovoľným iným, ktoré nemáme k dispozícii), tak už nemôže vyhovovať, lebo by sme aj tak nedokázali vyskladať takýto výkon. Teda stačí robiť niečo ako štandardný prvočíselný rozklad, ale rozkladané číslo budeme skúšať deliť iba $n$ prvočíslami zo vstupu, ktoré reprezentujú počty jadier daných počítačov. To bude mať časovú zložitosť $O(n+\log_2(m))$

Overiť jedno číslo vieme teda v čase $O(n + \log_2(m))$, čiže celková časová zložitosť je $O( P \log_2(m) (n + \log_2(m)))$. Pamäťová zložitosť je stále $O(n)$.

import math

MP = 500

primes = []
for i in range(2, MP):
    for p in primes:
        if i % p == 0: break
    else: primes.append(i)

def factorize(x):
    result = [0] * MP
    for p in primes:
        while x % p == 0:
            x //= p
            result[p] += 1
        if x == 1: break
    if x > 1:
        return None
    return result

def main():
    n = int(input())

    total = 0
    maxp = 0
    possible = [0] * MP

    for i in range(n):
        p, m = map(int, input().split())
        possible[p] = m
        total += m * p
        if m != 0: maxp = p

    maxoffset = math.ceil(math.log2(total)) * maxp

    for candidate in range(total, max(total - maxoffset, 1), -1):
        fact = factorize(candidate)
        if fact is None: continue

        realSum = 0
        for p in primes:
            if possible[p] < fact[p]:
                break
            realSum += p * (possible[p] - fact[p])
        else:
            if realSum == candidate:
                print(candidate)
                return

    print(0)

for i in range(int(input())):
    main()

# casova zlozitost je O( p (p + log(s)) log(p s) )
#include <bits/stdc++.h>

using namespace std;

long long MP = 500;
typedef vector<long long> vec;

vec primes;

vec factorize(long long x)
{
    vec result(MP, 0);
    for(long long p: primes)
    {
        while(x % p == 0)
        {
            x /= p;
            result[p]++;
        }
    }
    if(x != 1) result[0]++;
    return result;
}

void solve()
{
    long long n;
    cin >> n;

    long long total = 0;
    vec possible(MP, 0);

    for(long long i = 0; i < n; i++)
    {
        long long p, m;
        cin >> p >> m;
        possible[p] = m;
        total += m * p;
    }

    for(long long c = total; c > max(total - 30000ll, 0ll); c--)
    {
        auto fact = factorize(c);
        if(fact[0] != 0) continue;
        long long realSum = 0;
        for(long long p: primes)
        {
            if(possible[p] < fact[p])
            {
                realSum = -1;
                break;
            }
            realSum += p * (possible[p] - fact[p]);
        }
        if(realSum == c)
        {
            cout << c << endl;
            return;
        }
    }

    cout << 0 << endl;
}

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

    for(long long i = 2; i < MP; i++)
    {
        bool isPrime = true;
        for(long long p: primes)
        {
            if(i % p == 0)
            {
                isPrime = false;
                break;
            }
        }
        if(isPrime) primes.push_back(i);
    }

    for(long long i = 0; i < t; i++) solve();
}

  1. Tento fakt je známy ako základná veta aritmetiky. ↩

Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty