Aдреса - Тест Натпревар

This message was edited 1 time. Last update was at 25/03/2012 16:47:09

http://mendo.mk/Task.do?id=108

Некоја идеја за задачата?

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

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{

int n,br=0,res=0;
    cin>>n;
    int k=n;
    vector<int>cifri;
    while(k>0)
    {
          int a=k%10;
          cifri.push_back(a);
          k/=10;
          br++;
    }
    reverse(cifri.begin(),cifri.end());
    int i,j,l;
      for(i=1;i<=3;i++)
      {
            for(j=i+1;j<=br-2;j++)
            {
                  for(l=j+1;l<=br-1;l++)
                  {
                        int q=1,tmp=0;
                        bool b=true;
                        for(int x=j-1;x>=i;x--)
                        {
                              tmp+=cifri[x]*q;
                              q*=10;
                              if(tmp>=256)
                              b=false;
                              if(tmp>=10&&cifri[i-1]==0)
                              b=false;
                        }
                        q=1;tmp=0;
                        for(int x=l-1;x>=j;x--)
                        {
                              tmp+=cifri[x]*q;
                              q*=10;
                              if(tmp>=256)
                              b=false;
                              if(tmp>=10&&cifri[j-1]==0)
                              b=false;
                        }
                        q=1;tmp=0;
                        for(int x=br-1;x>=l;x--)
                        {
                              tmp+=cifri[x]*q;
                              q*=10;
                              if(tmp>=256)
                              b=false;
                              if(tmp>=10&&cifri[l-1]==0)
                              b=false;
                        }
                        q=1;tmp=0;
                        for(int x=0;x<i;x++)
                        {
                              tmp+=cifri[x]*q;
                              q*=10;
                              if(tmp>=256)
                              b=false;
                        }
                        if(b)
                        {
                              res++;
                              //cout<<i><<" "<<j><<" "<<l><<endl;
                        }
                  }
            }
      }
cout<<res><<endl;
    return 0;
}

Aj ako moze nekoj neka vidi shto e problemot so mojot kod?

This message was edited 1 time. Last update was at 25/03/2012 22:38:28

@filip_bujaroski: не ти чини проверката на првиот дел (А) од адресата "A.B.C.D", бидејќи ги земаш цифрите во обратен редослед - наместо од 0 до i-1, треба да се движиш од i-1 до 0. Исто, имаш грешка во проверката на тоа дали еден дел од адресата почнува со 0. Еве го (средениот) код:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{

int n,br=0,res=0;
    cin>>n;
    int k=n;
    vector<int>cifri;
    while(k>0)
    {
          int a=k%10;
          cifri.push_back(a);
          k/=10;
          br++;
    }
    reverse(cifri.begin(),cifri.end());
    int i,j,l;
      for(i=1;i<=3;i++)
      {
            for(j=i+1;j<=br-2;j++)
            {
                  for(l=j+1;l<=br-1;l++)
                  {
                        int q=1,tmp=0;
                        bool b=true;
                        for(int x=j-1;x>=i;x--)
                        {
                              tmp+=cifri[x]*q;
                              
                              if(cifri[i]==0 && q>1) //SMENETO
                                 b=false;
                              
                              q*=10;
                              if(tmp>=256)
                              b=false;
                              
                        }
                        q=1;tmp=0;
                        for(int x=l-1;x>=j;x--)
                        {
                              tmp+=cifri[x]*q;
                              
                              if(cifri[j]==0 && q>1) //SMENETO
                                 b=false;
                              
                              q*=10;
                              if(tmp>=256)
                              b=false;                              
                        }
                        q=1;tmp=0;
                        for(int x=br-1;x>=l;x--)
                        {
                              tmp+=cifri[x]*q;
                              
                              if(cifri[l]==0 && q>1) //SMENETO
                                 b=false;
                              
                              q*=10;
                              if(tmp>=256)
                              b=false;
                        }
                        q=1;tmp=0;
                        for(int x=i-1;x>=0;x--)
                        {
                              tmp+=cifri[x]*q;
                              q*=10;
                              if(tmp>=256)
                              b=false;
                        }
                        if(b)
                        {
                              res++;
                              //cout<<i><<" "<<j><<" "<<l><<endl;
                        }
                  }
            }
      }
cout<<res<<endl;
    return 0;
}

Инаку, кодот делува некако несреден. Пробај да користиш функции - имаш делови од кодот кој се повторуваат по неколку пати.

Tochno deka imam greshka za proverkata na A od stringot, megjutoa, ne sfakjam zoshto imam greshka vo proverkata za 0?

Ако не му е мака на некој, ќе можи да го образложи кодот на Филип?

Ќе ти објаснам јас како ја решив задачата. Доста слично е, затоа.
Со три for-циклуса ќе го одредуваш местото на точките (имаш 3 точки)
Првата точка може да биде после првата цифра, после првите две или после првите три цифри (четирицифрените броеви формираат невалидна адреса). Втората точка почнува од првата+1, а третата од втората+1.
После тоа ги земаш броевите кои се наоѓаат помеѓу точките и за сите четири броја проверуваш дали ги исполнуваат условите дадени во задачата (да бидат во интервалот [0,255], да немаат водечки нули ако се повеќецифрени итн.)

Се надевам дека ти помогнав

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

@vikjan94 Да ми помогна, фала..

Kade mi e greskata pri proverkata za 0?

Izvinete shto gi prasuvam po 2 pati istite prasanja, ama ne dobiv odgovor prethodniot pat

This message was edited 1 time. Last update was at 30/03/2012 01:12:11

filip_bujaroski wrote:Kade mi e greskata pri proverkata za 0?
Izvinete shto gi prasuvam po 2 pati istite prasanja, ama ne dobiv odgovor prethodniot pat

Па, еве да видиме за еден дел од адресата (другите треба слично да ги поправиш):

треба да биде

(q>10) е проверка за тоа дали има повеќе од 2 цифри во овој дел од адресата (да не е делчето точно '0')
cifri[i]==0 (ти имаш cifri[i-1]==0 ??) е проверка за тоа дали првата цифра е 0

Ти проверуваш, на пример, за адресата A.B.C.D, дали B>=10 (tmp >= 10), но тоа е комплетно неважно - 9.05.05.05 не е добра адреса.

Tachno

Sfativ sega

fala mnogu

@bedzo може да го постираш решението со дфс за задачава? Имам проблем со имплементација на дфс во вакви задачи

shellcode wrote:@bedzo може да го постираш решението со дфс за задачава? Имам проблем со имплементација на дфс во вакви задачи