View Attach (1) Info

Часовник#

Во оваа задача се бараше да напишеме програма која ќе го пресмета времетраењето на една активност (која нема да е подолга од 23 часа и 59 минути), ако ни се дадени забележаните времиња на почеток и крај на активноста.

Најлесен начин за решавање на оваа задача е доколку работиме само со минути (бидејќи знаеме дека еден час трае точно 60 минути, можеме лесно да ги префрлиме часовите во минути). Следи изворниот код на официјалното решение: 

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

int main()
{
    int hour1, minute1;
    int hour2, minute2;
    cin >> hour1 >> minute1;
    cin >> hour2 >> minute2;
    
    int total_minutes1 = hour1*60 + minute1;
    int total_minutes2 = hour2*60 + minute2;
    
    while (total_minutes2 < total_minutes1)
          total_minutes2 += 24 * 60;
          
    int result_hours = (total_minutes2-total_minutes1) / 60;
    int result_minutes = (total_minutes2-total_minutes1) % 60;
    
    cout << setfill('0');
    cout << setw(2) << result_hours << ":";
    cout << setw(2) << result_minutes << endl;
    
    return 0; //exit code zero
}

Решението дадено погоре има константна сложеност O(1).

Роденден#

Во оваа задача се бараше да напишеме програма која ќе одреди колку пакети од цифри (0-9) се потребни за да се формира некој број, доколку 6 и 9 можеме да ги заменуваме.

Решението оди вака: најпрвин во еден циклус броиме по колку пати се појавува секоја цифра, потоа пробуваме оптимално да ги поделиме (замениме) 6-ките и 9-ките така што најголемиот од нив да е што помал. Потоа само печатиме која цифра се појавила највеќе пати (колку пати се појавила). Следи изворниот кодот на официјалното решение: 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
     int years;
     cin >> years;
    
     int howmany[10];
     for (int i=0; i<10; i++)
        howmany[i] = 0;
        
     while (years > 0)
     {
         int lastDigit = years % 10;
         howmany[lastDigit] ++;
         
         years /= 10;             
     }
     
     howmany[6] += howmany[9]; //consider all as 6
     howmany[9] = 0;
     
     if (howmany[6] % 2 > 0)
        howmany[6] = howmany[6] / 2 + 1;
     else
        howmany[6] = howmany[6] / 2;
        
     int largest = 0;
     
     for (int i=0; i<10; i++)
        if (howmany[i] > largest)
           largest = howmany[i];
           
     cout << largest << endl;
     return 0; //exit code zero
}

Ова решение има сложеност О(log(N)), која зависи од големината на N, односно од бројот на цифри од кои е составен N.

Торта#

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

Решението се состои во определување на најмалата цена по која може да се купи пакет од 6 јајца, најмалата цена на 1 јајце, и потоа едноставно пробување која комбинација од групи и единечни јајца дава најмал резултат. Следи изворниот кодот на официјалното решение: 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int answer = 0, n, k;
    int bestPackagePrice = 32000;
    int bestSinglePrice = 320000;    
    
    cin >> n >> k;
    
    for (int i=0; i<k; i++)
    {
        int package, single;
        cin >> package >> single;
        
        if (package < bestPackagePrice)
           bestPackagePrice = package;
           
        if (single < bestSinglePrice)
           bestSinglePrice = single;
    }
    
    if (bestSinglePrice*6 <= bestPackagePrice)
    {
       //best to buy single eggs
       answer = (bestSinglePrice * n);
    }
    else
    {        
           
        int result = (n / 6) * bestPackagePrice;
        int remainingEggs = n % 6;
        
        if (remainingEggs * bestSinglePrice <= bestPackagePrice)
            answer = (result + remainingEggs * bestSinglePrice);
         else 
            answer = (result + bestPackagePrice);    
    }
    
    cout << answer << endl;
    return 0; //exit code 0
}

Ова решение има сложеност О(K), каде K го означува бројот на врсти на јајца.

Потоци#

Во оваа задача се бараше да напишеме програма која ќе го пронајде бројот во којшто одреден дигитален поток N за првпат ќе се сретне со некој од потоците 1, 3 или 9 (дефиницијата на дигитален поток е дадена во текстот на задачата).

Оваа задача може да се реши и со користење на некои напредни структури на податоци, но она решение што ние ќе го прикажеме тука се состои во едноставна симулација на она што го пишува во текстот на задачата (како се менуваат потоците). Следи изворниот кодот на официјалното решение: 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;        

int next_value(int number)
{
    int result = number;
    
    while (number > 0)
    {
          result += number%10;
          number /= 10;
    }
    
    return result;
}

int main()
{
    int river;
    cin >> river;

    int river1 = 1;
    int river3 = 3;
    int river9 = 9;
    
    while((river != river1) && (river != river3) && (river != river9)) 
    {
           while(river1 < river)
                 river1 = next_value(river1);
                 
           while(river3 < river)
                 river3 = next_value(river3);
                 
           while(river9 < river) 
                 river9 = next_value(river9);
           
           if((river != river1) && (river != river3) && (river != river9))
               river = next_value(river);
    }
    
    if (river1 == river) 
        cout << "1" << " " << river << endl;
    if (river3 == river) 
        cout << "3" << " " << river << endl;
    if (river9 == river) 
        cout << "9" << " " << river << endl;
        
    return 0; //exit code zero
}

Ова решение има неколку вгнездени while циклуси, но сепак работи доста брзо и ефикасно.

Бонбони#

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

Задачата се сведува на делење на бројот N постојано со 3, се додека тој не стане 0, и зависно од остатокот кој се јавува при тоа делење, додавање или на пакет во едниот дел или во другиот дел (доколку остатокот е 0, не додаваме нов пакет). Идејата најдобро се гледа на изворниот кодот на официјалното решение: 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
          int N;
          cin >> N;
          
          vector<int> nino; //empty array
          vector<int> tino; //empty array
          int currentFactor = 1;    
          
          nino.push_back(N);      
          
          while (N > 0)
          {
              if (N%3 == 0)
              {
                  N /= 3;
                  currentFactor *= 3;
                  continue; //While loop
              }
          
              if (N%3 == 1)
              {
                  N -= 1;  N /= 3;                  
                  tino.push_back(currentFactor);
                  currentFactor*=3;
                  continue;
              }
              
              if (N%3 == 2)
              {
                  N += 1; N /= 3;                  
                  nino.push_back(currentFactor);
                  currentFactor*=3;
                  continue;
              }
          }
          
          sort(nino.begin(), nino.end());
          sort(tino.begin(), tino.end());
          
          for (int i=0; i<nino.size(); i++)
              if (i == 0)
                 cout << nino[i];
              else
                 cout << " " << nino[i];
          
          cout << endl;
          
          for (int i=0; i<tino.size(); i++)
              if (i == 0)
                 cout << tino[i];
              else
                  cout << " " << tino[i];
          
          cout << endl;
          return 0; //exit code zero
}

На прв поглед, ова решение има сложеност O(NlogN), која следува од сортирањето (подредувањето на елементите), но по малку подетално разгледување на задачата, излегува дека во низите кои ги сортираме никогаш неможе да има повеќе од 20-тина елементи.

Друго решение е да го претвориме N во систем со основа 3, каде дозволените цифри се (-1,0,1) наместо (0,1,2). Размислете добро зошто функционира и ова решение?

Кастрење#

Во оваа задача се бараше да напишеме програма која за дадена листа од зборови, секој од нив ќе го "поткастри" од крајот така што ќе се најде најкраткиот префикс кој не е префикс и на некој од останатите зборови во листата.

Задачата се сведува на работа со стрингови (пронаоѓање на подниза, и наоѓање дали одреден стринг започнува со друг стринг). Следи изворниот кодот на официјалното решение: 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
  int n;
  cin >> n;
  
  vector<string> words;
  
  for (int i=0; i<n; i++)
  {
      string word;
      cin >> word;
      
      words.push_back(word);
  }
  
  for (int i=0; i<words.size(); i++)
  {
      //brute force each length
  	  int foundPrefix = 0;      
      
      for (int len=1; len<=words[i].size() && !foundPrefix; len++)
      {
           string check = words[i].substr(0, len);
           
           int ok = 1;
           for (int j=0; j<words.size(); j++)
              if (i!=j && words[j].find(check) == 0)
              {
                  //not a solution, because
                  //check is prefix of words[j]                                    
                  ok = 0; break; 
              }
              
          if (ok == 1)
          {
             //result for words[i]
             cout << check << endl;
             foundPrefix = 1;
          }                     
      }      
  }
  
  return 0;
}

Решенито има сложеност O(N2), каде N го означува бројот на зборови. Бидејќи максималната должина е 50, тој константен фактор не го додаваме на изразот.

Оро#

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

Решението е едноставно динамичко програмирање. Чуваме матрица dp[i][j], која ни означува дали можеме да бидеме на позиција j по правење на i групи од чекори. Следи изворниот кодот на официјалното решение: 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
   int p, m, n;
   vector<int> group;
   
   cin >> p >> m;    
   cin >> n;
   
   for (int i=0; i<n; i++)
   {
       int steps;
       cin >> steps;
       group.push_back(steps);
   }    
    
   //dp[i][j] is 1 if it's possible to
   //make group i, and end at position j           
   int dp[51][1001];
   
   //initially all are zeroes
   memset(dp, 0, sizeof(dp));
   
   dp[0][p] = 1;                                
   
   for (int i=0; i<group.size(); i++)
   {
       for (int j=0; j<=m; j++)
       {
           if (dp[i][j] == 1)
           {
               if (j - group[i] >= 0) dp[i+1][j-group[i]] = 1; //going left
               if (j + group[i] <= m) dp[i+1][j+group[i]] = 1; //going right                                                   
           }
       }
   }
   
   int finalResult = -1;
   for (int j=0; j<=m; j++)
      if (dp[group.size()][j] == 1)
         finalResult = j; //we can end at position j     
         
   cout << finalResult << endl;         
   return 0; //exit code 0
}

Решението има сложеност (N*M), каде N го означува бројот на групи на чекори, додека M ја означува широчината на сцената.

Тест случаи#

Тест случаите можете да ги симнете како .zip архива тука(info).
Текстот и решенијата дадени погоре можете слободно да ги коментирате на форумот.

Add new attachment

Only authorized users are allowed to upload new attachments.

List of attachments

Kind Attachment Name Size Version Date Modified Author Change note
zip
 testovi_regionalen_2010.zip 59.9 kB 1 20-Aug-2015 17:35 Bojan Kostadinov
« This page (revision-3) was last changed on 20-Aug-2015 17:35 by Bojan Kostadinov