Среќна сметка#

Во оваа задача се бараше да напишеме програма која од стандарден влез ќе прочита еден цел број N, и на стандарден излез ќе го отпечати најмалиот среќен број поголем од N. За еден број велиме дека е среќен доколку тој содржи само среќни цифри (цифрите 7 и 9). Решението се сведување на читање на бројот N и негово зголемување на 1, се додека не пронајдеме среќен број (број кој ги содржи само цифрите 7 и 9) - нека го означиме овој број со S. Очигледно, поради тоа што сме ги изминале сите цели броеви помеѓу N и S, S ќе биде бараниот *најмал* среќен број поголем од N. Следи изворниот код на официјалното решение:

#include <iostream>
using namespace std;

int main()
{
    int n, ans;
    cin >> n;

    for (int i=n+1; ; i++)
    {
        int cur = i, lucky = 1, digit;
        
        while (cur > 0)
        {
              digit = cur%10;
              cur/=10;
              
              if (digit!=7 && digit!=9)
                 lucky = 0;
        }
        
        if (lucky == 1)
        {
                  ans = i;
                  break;
        } 
    }
    
    cout << ans << endl;
    return 0;
}

Иако немаше потреба да се имплементира некој посложен алгоритам (бидејќи вредностите кои што може да ги добие N се мали), важно е да се напомене дека постојат и решенија кои работат побрзо од даденото (се со помала сложеност).

Прости броеви#

Во оваа задача се бараше да напишеме програма која од стандарден влез ќе прочита два цели броја L и R, и потоа, на стандарден излез ќе го отпечати збирот на сите прости броеви кои се наоѓаат помеѓу L и R.

Решението се сведува на изминување на сите броеви помеѓу L и R, и проверување, за секој од нив, дали е тој прост или не. Според дефиницијата дадена во текстот на задачата, за еден природен број N велиме дека прост доколку тој има точно два (различни) делители – бројот 1 и самиот тој број N. Следи изворниот кодот на официјалното решение:

#include <iostream>
using namespace std;

bool prime(int n)
{
     int divisors = 0;
     
     for (int i=1; i<=n; i++)
         if (n%i==0)
            divisors++;
            
     return (divisors == 2);
}

int main()
{
    int l, r;
    cin >> l >> r;
    
    int sum = 0;
    
    for (int i=l; i<=r; i++)
    {
        if (prime(i))
           sum += i;
    }
    
    cout << sum << endl;
    return 0;
}

Како и кај претходната задача, така и кај оваа, важно е да се напомене дека можеме значително да го намалиме времето на извршување (да ја намалиме сложеноста) на функцијата за проверување дали еден број е прост или не. Размислете како?! Дали мораме, со циклусот со кој броиме колку делители има N, да се движиме до N, или можеме да се движиме до некој помал број?

Тест случаи#