Messages posted by: bedzo

8 од интернационални е исто така многу лесна.

#include <iostream>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
#define DBL_MAX 1.7976931348623158e+308
int n;
int dp[5005]; // nizata za dinamickoto, dp[i] oznacuva so kolku operacii mozeme da stigneme do i
int mat[100000]; // niza kade vmetnuvam vrednosta na broevite(operaciite)
int main()
{
    string g; // gi zimam broevite sto mozam da gi koristam vo string
    int z=0; //brojacot na kombinaciite od broevi
    int b; //sumata do kade treba da se stigne
    memset(dp,-1,sizeof(dp)); // ja popolnuvam cela niza so -1
    cin>>g>>b; //input
    dp[b]=0;// pocetnoto mu stavame 0.
    vector<int> t,a; // vo t gi oznacuvam koristenite cifri, vo a gi stavam site mozni broevi sto mozat da se dobijat od cifrite
    int i,j,k,l;
    for(i=0;i<g.size();i++)
    {
        t.push_back(g[i]-'0'); // dodavanje na cifrite edna po edna vo vektor od stringot
    }
    for(i=0;i<g.size();i++) // dobivanje na site 4-cifreni broevi so dadenite cifri
    {
        if(g[i]==0) continue;
        a.push_back(t[i]);
        mat[z++]=2; // na ednocifrenite broevi im davame vrednost 2. brojot na cifri vnatre + znakot(+,*)
        for(j=0;j<g.size();j++)
        {
            a.push_back(t[i]*10+t[j]);
            mat[z++]=3; // na dvocifrenite im davame vrednost 3. brojot na cifri vnatre + znakot (+,*)
            for(k=0;k<g.size();k++)
            {
                a.push_back(t[i]*100+t[j]*10+t[k]);
                mat[z++]=4;
                for(l=0;l<g.size();l++)
                {
                    a.push_back(t[i]*1000+t[j]*100+t[k]*10+t[l]);
                    mat[z++]=5;
                }
            }
        }
    }
    // uspesno gi generira site broevi i im dava vrednosti
    if(b==5000) // resenie za 5000...
    {
        if(t[0]>6) cout<<"5"<<endl;
        else if(t[0]>2) cout<<"6"<<endl;
        else if(t[0]>1) cout<<"7"<<endl;
        else cout<<"24"<<endl;
        return 0;
    }
    // dinamickoto raboti od nazad nanapred, i namesto sobiranje koristam odzimanje,namesto mnozenje koristam delenje
        for(i=b;i>0;i--) // b e sumata kade sto treba da stigneme
        {
            if(dp[i]!=-1)
            {
                for(j=0;j<a.size();j++) // gi pominuvame site mozni broevi od cifrite
                {
                    if(i-a[j]>=0) // ako odzimanjeto e vo granici
                    {
                        if(dp[i-a[j]]==-1) dp[i-a[j]]=dp[i]+mat[j]; // ako ne sum dobil vrednost za dp[i-a[j]] ja stavam po default
                        else dp[i-a[j]]=min(dp[i-a[j]],dp[i]+mat[j]);// ako ne, gledam pooptimalnata
                    }
                    if(a[j]!=0){ // so 0 ne se deli
                    if(i%a[j]==0) // ako se deli
                    {
                        if(dp[i/a[j]]==-1) dp[i/a[j]]=dp[i]+mat[j]; //ako ne sum dobil vrednost
                        else dp[i/a[j]]=min(dp[i/a[j]],dp[i]+mat[j]);//ako ne, ja zimam pooptimalnata
                    }
                    }
                }
            }
        }
    cout<<dp[0]-1<<endl;//pecatam dp[0]-1 bidejki za prviot element ne treba da go brojam znakot kako karakter vo nizata mat
    return 0;
}

ми дава 10/20.
А на примерите што паѓа дава помал резултат од колку што чека програмата... Решение?

deklariraj b="", bidejki dava nekoja vrednost na stringot ako go nemas deklarirano prazen string.

A mozhebi kje treba da go deklariras stringot b so a.size() prazni mesta. Proveri, neznam taka od oko kako ke raboti i ne ti ja znam ideata

14,20,23,41,49,64,70,81,98

Под реден број, во групата [ Национални ]

int int_sqrt(int x)
{
return (int)(round(sqrt(x)));
}

Oва ти е функција која за квадратен број ти дава цел број, наместо реален. Го заокружува реалниот број и го враќа како цел.

Не ти го разгледав кодот,но пишувам да ти кажам дека и brute-force поминува...

Проблемот е knapsack(максимален збир) со 1 повторување...
Има сложеност N*M... Незнам каде се буниш за да ти објаснам...

Еве, направи матрица [N][10000] каде што N ти е бројот на земени луѓе, а другото ти е јачината.

Поточно матрица[2][30] ти означува дали со 2ца можеш да стигнеш до јачина 30.

Потоа само го гледаш редот N/2 и бараш кое решение е најблиско до средината...

Може некој да даде идеа за задачата?

Јас имам решение со дфс, после секое точка пуштам дфс за да земе 1,2 или 3 цифри од адресата. Ако првата цифра е 0, пуштам само да земе 1 цифра.

Brute-force.
Проби ги сите комбинации за ИП адреси.

Може да ги ставите задачите во тренинг?

stefan5andonov1 wrote:Dali nie koi sme vo osnovna grupa mozeme da gi resavame zadacite od trening koi se nameneti za pocetnici?

Da.

Дај нека остави некој код од 4та.. Сум испуштил еден свап во циклус и не поминала цела :/

Ау ама сум се зафркнал со ова координатите... Благодарам на забелешката