Форум Всеукраїнської інтернет-олімпіади NetOI

#include <iostream>
#include<cstring>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ul;
typedef long double ld;

ull fast_pow(ull x,ull power)
{
    ull res=1;
    while(power)
    {
        if(power%2)res*=x;
        x*=x;
        power>>=1;
    }
    return res;
}

int countL3(int n)                              //Рішення для одноцифрових випадків
{
    if(n>=9)return 3;
    if(n>=3)return 2;
    if(n>=1)return 1;
    return 0;
}

ull like3(char* a,int t,bool first=true)       //а - масив цифр числа, t - довжина числа
{
    if(t<=0)return 0;                           
    if(t==1)return countL3(a[0]);
    ull res=(countL3(a[0]-1))*fast_pow(3,t-1);  //Кількість триподібних такої-ж довжини, як і початкове число, у яких старший розряд менший, ніж у даного
    int i=1;
    if(first)while(t-i)res+=fast_pow(3,t-i),i++;//Якщо функція викликана не рекурсивно, то до розв’язку додаємо кількість триподібних, коротших за дане число
    if(9%a[0])return res;                       //Якщо перша цифра числа не 3-подібна, то відповідь уже знайдено
    if(a[1])res+=like3(a+1,t-1,false);          //Інакше до відповіді треба додати рішення для усих цифр числа, крім першої(за умови, що друга цифра - не нуль)
    return res;
}

ull solve(char* a, char *b)                         //Функція, що перетворюе рядок ANSI-символів у масив "звичайних" цифр,            
{                                                   //Вирішує задачу окремо для першого та другого числа, а потім повертає відповідь.
    int a_len=strlen(a),b_len=strlen(b),i=0;
    bool f=true;
    while(a[i])a[i]-='0',f=f&&a[i]!=0&&!(9%a[i]),i++;
    i=0;
    while(b[i])b[i]-='0',i++;
    return like3(b,b_len)-like3(a,a_len)+f;
}

int main()
{
    char a[42],b[42];
    cin>>a>>b;
    cout<<solve(a,b)<<endl;
}

#include <iostream>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ul;
typedef long double ld;

ull solve(ull n,ull cur_max=1, int start_prime=0)
{
    static const ull primes[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131};
    static const int N_PRIMES=16;
    static const ld EPS=1e-6;
    static ul times_used[N_PRIMES]={0};
    static ull max=0;
    for(int i=start_prime;i<N_PRIMES;++i)
    {
        if((ld)primes[i]*cur_max-(ld)n>EPS)
        {
            ull ts=1;
            for(int i=0;i<N_PRIMES;++i)ts*=times_used[i]+1;
            if(ts>max)max=ts;
        }
        else if(!i||times_used[i-1]>=times_used[i]+1)
        {
            times_used[i]++;
            solve(n,cur_max*primes[i],i);
            times_used[i]--;
        }
    }
    return max;
}

int main()
{
    ull n;
    cin>>n;
    cout<<solve(n)<<endl;
}

#include <queue>
#include <utility>
#include <cstdio>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ul;
typedef long double ld;

//bicycles begin
template<typename _Tp>
  inline _Tp*
  __addressof(_Tp& __r)
  {
    return reinterpret_cast<_Tp*>
      (&const_cast<char&>(reinterpret_cast<const volatile char&>(__r)));
  }
template<class T>
struct myList
{
    struct node
    {
        T data;
        node *prev, *next;
        node():prev(0x0),next(0x0){}
    };
    struct iterator
    {
        node *p;
        T& operator *(){return p->data;}
        T* operator ->(){return ::__addressof(p->data);}
        iterator& operator ++(){p=p->next;return *this;}
        iterator& operator --(){p=p->prev;return *this;}
        bool operator ==(iterator const &rhs)const{return p==rhs.p;}
        bool operator !=(iterator const &rhs)const{return !(this->operator ==(rhs));}
        iterator():p(0x0){}
    };
    iterator _beg;
    iterator _end;
    int _sz;
    iterator begin()
    {
        return _beg;
    }
    iterator end()
    {
        return _end;
    }
    int size()
    {
        return _sz;
    }
    void push_back(const T& x)
    {
        if(!_sz)
        {
            _beg.p=new node;
            _end.p=new node;
            _beg.p->prev=0x0;
            _end.p->next=0x0;
            _beg.p->next=_end.p;
            _end.p->prev=_beg.p;
            _end.p=_beg.p;
        }
        *_end=x;
        node* t=_end.p;
        _end.p->next=new node;
        ++_end;
        _end.p->prev=t;
        _end.p->next=0x0;
        _sz++;
    }
    myList():_sz(0){}
    iterator erase(iterator i)
    {
        node* t=i.p;
        if(i.p->prev)i.p->prev->next=i.p->next;
        else ++_beg;
        if(i.p->next)i.p->next->prev=i.p->prev;
        else --_end;
        ++i;
        delete t;
        _sz--;
        if(!_sz)i.p=0x0;
        return i;
    }
};

//bicycles end

struct tree
{
    int id;
    pair<tree*,int> parent;
    myList<pair<tree*,int> > child;
    int max,nMax;
    int neighborsConsidered;
    bool f;
    tree():parent(pair<tree*,int>((tree*)0x0,-1)),max(0),nMax(0),neighborsConsidered(0),f(0){}
};

inline pair<int,int> gen_tree(tree* station,int N)
{
    int max=0, nMax=0;
    tree *root;
    queue<int> q;
    for(int i=0;i<N;++i)
        if(station[i].child.size()==1)q.push(i),station[i].nMax=1;
    while(!q.empty())
    {
        int current=q.front();
        q.pop();
        if(station[current].f)continue;
        if(station[current].neighborsConsidered<(int)station[current].child.size()-1)
        {
            q.push(current);
            continue;
        }
        station[current].f=true;
        myList<pair<tree*,int> >::iterator i;
        for(i=station[current].child.begin();i!=station[current].child.end();++i)
            if(!station[i->first->id].f)break;
        if(i==station[current].child.end())
        {
            root=&station[current];
            station[current].parent.first=0x0;
            station[current].parent.second=-1;
        }
        else
        {
            station[current].parent=*i;
            station[current].child.erase(i);
            station[current].parent.first->neighborsConsidered++;
            q.push(station[current].parent.first->id);
        }
        int tMax=-1,nTMax=0,curMax,nCurMax,nMaxBranches=0;
        for(myList<pair<tree*,int> >::iterator i=station[current].child.begin();i!=station[current].child.end();++i)
        {
            if(i->first->max+i->second>station[current].max)
            {
                tMax=station[current].max;
                nTMax=station[current].nMax;
                station[current].max=i->first->max+i->second;
                station[current].nMax=i->first->nMax;
                nMaxBranches=1;
            }
            else if(i->first->max+i->second==station[current].max)
                station[current].nMax+=i->first->nMax,nMaxBranches++;
            else if(i->first->max+i->second>tMax)
            {
                tMax=i->first->max+i->second;
                nTMax=i->first->nMax;
            }
            else if(i->first->max+i->second==tMax)
                nTMax+=i->first->nMax;
        }
        if(station[current].child.size()==1)continue;
        if(nMaxBranches==1)
        {
            curMax=station[current].max+tMax;
            nCurMax=2*station[current].nMax*nTMax;
        }
        else
        {
            curMax=2*station[current].max;
            nCurMax=0;
            for(myList<pair<tree*,int> >::iterator i=station[current].child.begin();i!=station[current].child.end();++i)
            {
                if(i->first->max+i->second!=station[current].max)continue;
                nCurMax+=(station[current].nMax-i->first->nMax)*(i->first->nMax);
            }
        }
        if(curMax>max)
        {
            max=curMax;
            nMax=nCurMax;
        }
        else if(curMax==max)
            nMax+=nCurMax;
    }
    return pair<int,int>(max,nMax);
}

int main()
{
    srand(time(0));
    int N;
    scanf("%d",&N);
    int src,dst,price;
    static tree station[100000];
    for(int i=0;i<N;i++)
        station[i].id=i;
    if(N==2)
    {
        int res,a;
        scanf("%d%d%d",&a,&a,&res);
        printf("%d 2\n",res);
        return 0;
    }
    for(int i=0;i<N-1;i++)
    {
        scanf("%d%d%d",&temp.src,&temp.dst,&temp.price);
        src--, dst--;
        station[src].child.push_back(pair<tree*,int>(&station[dst],price));
        station[dst].child.push_back(pair<tree*,int>(&station[src],price));
    }
    pair<int,int> res=gen_tree(station,N);
    printf("%d %d\n",res.first,res.second);
}

#include <iostream>
#include <cmath>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ul;
typedef long double ld;

ull fast_pow(ull n,ull power)
{
    ull res=1;
    while(power)
    {
        if(power&1)
            res*=n;
        n*=n;
        power>>=1;
    }
    return res;
}

ull n_digits_count(ull n)
{
    if(n==1)return 9;
    return 9*fast_pow(10,n-1);
}

ull str_len(ull n)
{
    ull res=0;
    ull t=ceil(log10(n+1));
    for(ull i=1;i<t;++i)
    {
        res+=i*n_digits_count(i);
    }
    res+=t*(n-fast_pow(10,t-1)+1);
    return res;
}

ull get_ith_digit(ull n,ull i,ull t)
{
    return (n/fast_pow(10,t-i))%10;
}

ull consecutive_repeats(ull n,ull t,bool init=1)
{
    if(n<10&&t<2)return 0;
    ull res=0;
    ull threshold=fast_pow(10,t-1);
    ull first,second;
    if(n>=threshold)
    {
        first=get_ith_digit(n,1,t);
        second=get_ith_digit(n,2,t);
    }
    else if(n>=threshold/10)
    {
        first=0;
        second=get_ith_digit(n,1,t-1);
    }
    else first=second=0;
    res+=(first-init)*fast_pow(10,t-2)*(t-1);
    if(second>first)res+=fast_pow(10,t-2);
    else if(second==first)res+=n%fast_pow(10,t-2)+1;
    return res+consecutive_repeats(n%fast_pow(10,t-1),t-1,0);
}

ull repeats_count(ull n)
{
    if(n<10)return 0;
    ull t=ceil(log10(n+1));
    ull first=get_ith_digit(n,1,t),last=get_ith_digit(n,t,t);
    ull res=(first-1)*fast_pow(10,t-2)+(n/10)%fast_pow(10,t-2)+(last>first)+(first==9);
    return res+consecutive_repeats(n,t)+repeats_count(fast_pow(10,t-1)-1);
}

ull solver(ull n)
{
    return str_len(n)-repeats_count(n);
}

ull bin_search(ull l, ull r, ull query, ull(*f)(ull))
{
    for(ull i=0;i<200&&l<r;++i)
    {
        ull mid=l+((r-l)>>1);
        if(f(mid)<query)l=mid;
        else r=mid;
    }
    return query==f(l)?l:r;
}

int main()
{
    ull n;
    cin>>n;
    cout<<bin_search(1,fast_pow(10,19),n,solver)<<endl;
}