[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Решенија државен 2011  XML
Forum Index » Задачи од национални натпревари
Author Message
FREEZX
*****


Joined: 16/02/2010 19:32:31
Messages: 33
Offline

Ајмо ставајте ваши решенија за задачите од државен. Еве ги моите:

Одземање:

  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4. void bubblesort(string &a)  
  5. {  
  6.     char tmp;  
  7.     for(int i=0; i<a.length(); i++)  
  8.     {  
  9.         for(int j=0; j<a.length()-1; j++)  
  10.         {  
  11.             if(a[j]>a[j+1])  
  12.             {  
  13.                 tmp=a[j];  
  14.                 a[j]=a[j+1];  
  15.                 a[j+1]=tmp;  
  16.             }  
  17.         }  
  18.     }  
  19. }  
  20.   
  21. void bubblesortrev(string &a)  
  22. {  
  23.     char tmp;  
  24.     for(int i=0; i<a.length(); i++)  
  25.     {  
  26.         for(int j=0; j<a.length()-1; j++)  
  27.         {  
  28.             if(a[j]<a[j+1])  
  29.             {  
  30.                 tmp=a[j];  
  31.                 a[j]=a[j+1];  
  32.                 a[j+1]=tmp;  
  33.             }  
  34.         }  
  35.     }  
  36. }  
  37.   
  38. int main()  
  39. {  
  40.     char min='9';  
  41.     string broj, minbroj;  
  42.     cin>>broj;  
  43.     minbroj=broj;  
  44.     bubblesort(minbroj);  
  45.     bubblesortrev(broj);  
  46.     for(int i=0; i<broj.length(); i++)  
  47.     {  
  48.         if(broj[i]-minbroj[i]+'0'<'0')  
  49.         {  
  50.             for(int j=i-1; j>=0; j--)  
  51.             {  
  52.                 if(broj[j]-1>='0')  
  53.                 {  
  54.                     broj[j]--;  
  55.                     break;  
  56.                 }  
  57.                 else  
  58.                 {  
  59.                     broj[j]='9';  
  60.                 }  
  61.             }  
  62.             broj[i]=broj[i]-minbroj[i]+'9'+1;  
  63.         }  
  64.         else broj[i]=broj[i]-minbroj[i]+'0';  
  65.     }  
  66.     int loc=broj.length()-1;  
  67.     for(int i=0; i<broj.length(); i++)  
  68.     {  
  69.         if(broj[i]=='0')  
  70.         continue;  
  71.         else  
  72.         {  
  73.             loc=i;  
  74.             break;  
  75.         }  
  76.     }  
  77.     for(int i=loc; i<broj.length(); i++)  
  78.     {  
  79.         cout<<broj[i];  
  80.     }  
  81.     return 0;  
  82. }  


Прегледување:
  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4. int main()  
  5. {  
  6.     int n, k, kv=0, minvreme=9999999, minkom=9999999;  
  7.     cin>>n>>k;  
  8.     for(int i=1; i<999999; i++)  
  9.     {  
  10.         for(int j=1; j<i; j++)  
  11.         {  
  12.             kv+=j;  
  13.         }  
  14.         if((n%i==0)&&(kv*k+n/i<minvreme))  
  15.         {  
  16.             minvreme=kv*k+n/i;  
  17.         }  
  18.         else if ((n%i!=0)&&(kv*k+n/i+1<minvreme))  
  19.             minvreme=kv*k+n/i+1;  
  20.             //minvreme=kv*k+n%i+n/i;  
  21.         else break;  
  22.         kv=0;  
  23.         minkom=i;  
  24.     }  
  25.     cout<<minkom;  
  26.     return 0;  
  27. }  


FREEZX
*****


Joined: 16/02/2010 19:32:31
Messages: 33
Offline

Регистрација:
  1. #include <iostream>  
  2. #include <sstream>  
  3.   
  4. using namespace std;  
  5.   
  6. int main()  
  7. {  
  8.     stringstream ss;  
  9.     string a, rez, plus;  
  10.     int n, plu=1;  
  11.     cin>>a>>n;  
  12.     rez=a;  
  13.     string users[n];  
  14.     for(int i=0; i<n; i++)  
  15.     {  
  16.         cin>>users[i];  
  17.     }  
  18.     for(int i=0; i<n; i++)  
  19.     {  
  20.         if(users[i]==rez)  
  21.         {  
  22.             ss<<plu;  
  23.             ss>>plus;  
  24.             rez=a+plus;  
  25.             ss.str("");  
  26.             ss.clear();  
  27.             plu++;  
  28.             i=-1;  
  29.         }  
  30.     }  
  31.     cout<<rez;  
  32.     return 0;  
  33. }  
FREEZX
*****


Joined: 16/02/2010 19:32:31
Messages: 33
Offline

Финкимен:
  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4. int r, c, minpole=999999, minr, minc;  
  5. int pole[50][50];  
  6.   
  7. bool check()  
  8. {  
  9.     for(int i=0; i<r; i++)  
  10.     {  
  11.         for(int j=0; j<c; j++)  
  12.         {  
  13.             if(pole[i][j]!=-1)  
  14.                 return false;  
  15.         }  
  16.     }  
  17.     return true;  
  18. }  
  19.   
  20. void findmin()  
  21. {  
  22.     for(int i=0; i<r; i++)  
  23.     {  
  24.         for(int j=0; j<c; j++)  
  25.         {  
  26.             if((pole[i][j]!=-1)&&(pole[i][j]<minpole))  
  27.             {  
  28.                 minpole=pole[i][j];  
  29.                 minr=i;  
  30.                 minc=j;  
  31.             }  
  32.         }  
  33.     }  
  34. }  
  35.   
  36. void fill(int x, int y)  
  37. {  
  38.     int val=pole[x][y];  
  39.     pole[x][y]=-1;  
  40.     if((x+1<r)&&(pole[x+1][y]>=val)) fill(x+1, y);  
  41.     if((x-1>=0)&&(pole[x-1][y]>=val)) fill(x-1, y);  
  42.     if((y+1<c)&&(pole[x][y+1]>=val)) fill(x, y+1);  
  43.     if((y-1>=0)&&(pole[x][y-1]>=val)) fill(x, y-1);  
  44. }  
  45.   
  46. int main()  
  47. {  
  48.     int res=0;  
  49.     cin>>r>>c;  
  50.     for(int i=0; i<r; i++)  
  51.     {  
  52.         for(int j=0; j<c; j++)  
  53.         {  
  54.             cin>>pole[i][j];  
  55.             if(pole[i][j]<minpole)  
  56.             {  
  57.                 minr=i;  
  58.                 minc=j;  
  59.                 minpole=pole[i][j];  
  60.             }  
  61.         }  
  62.     }  
  63.     while(check()==false)  
  64.     {  
  65.         fill(minr, minc);  
  66.         res++;  
  67.         minpole=999999;  
  68.         findmin();  
  69.     }  
  70.     cout<<res;  
  71.     return 0;  
  72. }  
FREEZX
*****


Joined: 16/02/2010 19:32:31
Messages: 33
Offline

Ајде камо open-source дух! Моиве решенија ги ставив на Wiki-то
bedzo
*****


Joined: 18/01/2011 02:05:03
Messages: 234
Offline

Odzemanje:
  1. #include<iostream>  
  2. #include<string>  
  3. #include<algorithm>  
  4. using namespace std;  
  5.   
  6. int main()  
  7. {  
  8.     string a;  
  9.     int a1[101],b[101],i,j=0,h[101],z=0,po[101],fe=0;  
  10.     cin>>a;  
  11.     for(i=0;i<a.size();i++)  
  12.     {  
  13.         a1[i]=a[i]-48;  
  14.         b[i]=a1[i];  
  15.     }  
  16.     sort(a1,a1+a.size());  
  17.     sort(b,b+a.size());  
  18.     reverse(b,b+a.size());  
  19.     for(i=a.size()-1;i>-1;i--)  
  20.     {  
  21.         if(b[i-1]<0)  
  22.             {  
  23.                 b[i-1]+=10;  
  24.                 b[i-2]-=1;  
  25.             }  
  26.         if(b[i]<a1[i])  
  27.         {  
  28.             b[i]+=10;  
  29.             b[i-1]-=1;  
  30.             if(b[i-1]<0)  
  31.             {  
  32.                 b[i-1]+=10;  
  33.                 b[i-2]-=1;  
  34.             }  
  35.         }  
  36.         h[i]=b[i]-a1[i];  
  37.     }  
  38.     while (h[fe]==0) fe++;  
  39.     if(fe==a.size()) cout<<"0";  
  40.     else  
  41.     {  
  42.     for(i=fe;i<a.size();i++)  
  43.     {    
  44.         cout<<h[i];  
  45.     }  
  46.     }  
  47.     return 0;  
  48. }  

This message was edited 2 times. Last update was at 05/04/2011 01:07:18

obi1kenobi
*****


Joined: 18/02/2010 20:01:33
Messages: 168
Offline

Задача Прекин, државен 2011 напредна група - задача 3.

  1. #include<iostream>  
  2. #include<cstdio>  
  3. #include<cstdlib>  
  4. #include<stack>  
  5. #include<vector>  
  6. #include<algorithm>  
  7. #include<map>  
  8. #include<set>  
  9. #include<list>  
  10. #include<queue>  
  11. #include<cmath>  
  12. #include<ctime>  
  13. #include<fstream>  
  14. #include<string>  
  15. #include<cstring>  
  16. #include<climits>  
  17.   
  18. using namespace std;  
  19.   
  20. #define sz(x) (int)((x).size())  
  21. #define all(c) (c).begin(),(c).end()  
  22. #define DBGM(x,y) if(DEBUG) cout << #x << ' ' << #y << ": " << x << ' ' << y << '\n'  
  23. #define MSI(x,y) memset((x),(y),sizeof(x));  
  24.   
  25. #define DEBUG true;  
  26.   
  27. class dijk  
  28. {  
  29.     public:  
  30.     int nd,cost,orig;  
  31. };  
  32.   
  33. bool operator<(dijk a,dijk b)  
  34. {  
  35.     if(a.cost==b.cost) return a.nd>b.nd;  
  36.     return a.cost>b.cost;  
  37. }  
  38.   
  39. list<int> bgn,en;  
  40. int res;  
  41. int remnr;  
  42. int n,m;  
  43. int taken;  
  44.   
  45. list<int> cnn[101];  
  46. list<int> cost[101];  
  47. bool vis[101],add;  
  48. priority_queue<dijk> * que;  
  49.   
  50. void proc(dijk in)  
  51. {  
  52.     if(vis[in.nd]) return;  
  53.   
  54.     dijk tmp;  
  55.     list<int>::iterator it,it2;  
  56.   
  57.     if(add)  
  58.     {  
  59.         bgn.push_back(in.orig);  
  60.         en.push_back(in.nd);  
  61.     }  
  62.   
  63.     vis[in.nd]=true;  
  64.     taken++;  
  65.     res+=in.cost;  
  66.     it=cnn[in.nd].begin();  
  67.     it2=cost[in.nd].begin();  
  68.   
  69.     while(it!=cnn[in.nd].end())  
  70.     {  
  71.         if(!vis[*it])  
  72.         {  
  73.             tmp.nd=*it;  
  74.             tmp.cost=*it2;  
  75.             tmp.orig=in.nd;  
  76.             que->push(tmp);  
  77.         }  
  78.         it++;  
  79.         it2++;  
  80.     }  
  81.   
  82. }  
  83.   
  84. int span()  
  85. {  
  86.     MSI(vis,0);  
  87.     res=0;  
  88.     taken=0;  
  89.     dijk tmp;  
  90.     tmp.nd=0;  
  91.     tmp.cost=0;  
  92.     tmp.orig=-1;  
  93.   
  94.     que->push(tmp);  
  95.   
  96.     while(taken<n && !que->empty())  
  97.     {  
  98.         tmp=que->top();  
  99.         que->pop();  
  100.   
  101.         proc(tmp);  
  102.     }  
  103.     if(taken<n)  
  104.     {  
  105.         return INT_MAX;  
  106.     }  
  107.     return res;  
  108. }  
  109.   
  110. int main()  
  111. {  
  112.     int a,b,c,i,j,ares,bres=INT_MAX;  
  113.     que=new priority_queue<dijk>;  
  114.     add=true;  
  115.   
  116.     scanf("%d %d",&n,&m);  
  117.   
  118.     for(i=0;i<m;i++)  
  119.     {  
  120.         scanf("%d %d %d",&a,&b,&c);  
  121.         a--;  
  122.         b--;  
  123.         cnn[a].push_back(b);  
  124.         cost[a].push_back(c);  
  125.         cnn[b].push_back(a);  
  126.         cost[b].push_back(c);  
  127.     }  
  128.   
  129.     ares=span();  
  130.     add=false;  
  131.   
  132.     list<int>::iterator ita,itb,itan,itbn,itc,itcn,itd,itdn;  
  133.   
  134.     while(bgn.begin()!=bgn.end())  
  135.     {  
  136.         if(*bgn.begin()==-1 || *en.begin()==-1)  
  137.         {  
  138.             bgn.pop_front();  
  139.             en.pop_front();  
  140.             continue;  
  141.         }  
  142.   
  143.         ita=cnn[*bgn.begin()].begin();  
  144.         itb=cost[*bgn.begin()].begin();  
  145.         itc=cnn[*en.begin()].begin();  
  146.         itd=cost[*en.begin()].begin();  
  147.         while(*ita!=*en.begin())  
  148.         {  
  149.             ita++;  
  150.             itb++;  
  151.         }  
  152.         itan=ita;  
  153.         itan++;  
  154.         cnn[*bgn.begin()].erase(ita);  
  155.         remnr=*itb;  
  156.         itbn=itb;  
  157.         itbn++;  
  158.         cost[*bgn.begin()].erase(itb);  
  159.   
  160.         while(*itc!=*bgn.begin())  
  161.         {  
  162.             itc++;  
  163.             itd++;  
  164.         }  
  165.         itcn=itc;  
  166.         itcn++;  
  167.         itdn=itd;  
  168.         itdn++;  
  169.         cnn[*en.begin()].erase(itc);  
  170.         cost[*en.begin()].erase(itd);  
  171.   
  172.         delete que;  
  173.         que=new priority_queue<dijk>;  
  174.   
  175.         bres=min(bres,span());  
  176.   
  177.         ita=itan;  
  178.         itb=itbn;  
  179.         itc=itcn;  
  180.         itd=itdn;  
  181.         cnn[*bgn.begin()].push_back(*en.begin());  
  182.         cnn[*en.begin()].push_back(*bgn.begin());  
  183.         cost[*bgn.begin()].push_back(remnr);  
  184.         cost[*en.begin()].push_back(remnr);  
  185.         bgn.pop_front();  
  186.         en.pop_front();  
  187.     }  
  188.     printf("%d %d\n",min(ares,bres),max(ares,bres));  
  189.      
  190.     return 0;  
  191. }  

This message was edited 2 times. Last update was at 05/04/2011 20:06:06

bedzo
*****


Joined: 18/01/2011 02:05:03
Messages: 234
Offline

  1. #include<iostream>  
  2. using namespace std;  
  3. int main()  
  4. {  
  5.     int m,n,i,sum1,sum=500000,raz=0;  
  6.     cin>>m>>n;  
  7.     for(i=1;i<500000;i++)  
  8.     {  
  9.         for(int j=1;j<i;j++)  
  10.         {  
  11.             raz+=j;  
  12.   
  13.         }  
  14.         if((m%i==0) && (raz*n + m*i<sum))  
  15.            {  
  16.                sum = raz*n + m*i;  
  17.            }  
  18.         else if((m%i==0) && (raz*n + m*i+1<sum))  
  19.         {  
  20.             sum = raz*n + m*i +1;  
  21.         }  
  22.         else break;  
  23.         raz=0;  
  24.         sum1=i;  
  25.     }  
  26.     cout<<sum1;  
  27.     return 0;  
  28. }  
FREEZX
*****


Joined: 16/02/2010 19:32:31
Messages: 33
Offline

може објаснување за Прекин?

This message was edited 1 time. Last update was at 05/04/2011 22:47:34

bedzo
*****


Joined: 18/01/2011 02:05:03
Messages: 234
Offline

frezeex koga ke imas vreme napisi objasnuvanje za finkimen.. Dupka sum u BFS & DFS..

This message was edited 1 time. Last update was at 06/04/2011 16:01:14

FREEZX
*****


Joined: 16/02/2010 19:32:31
Messages: 33
Offline

ова е уствари дфс решение, со тоа што секогаш се означува поминатото поле со -1. Почнуваш од минимална висини и се движиш кон поголемите колку што можеш после пак бараш друго минимално поле па и од тоа почнуваш, и така на крајот све ќе поминеш и ќе изброиш колку пати така требало да се бара минимум. секое поминување на еден дфс проверуваш дали сите членови се -1. Ако се, прекинуваш и печатиш решение
obi1kenobi
*****


Joined: 18/02/2010 20:01:33
Messages: 168
Offline

FREEZX wrote:може објаснување за Прекин?


Задачата ја решавам со алгоритам на Прим за наоѓање minimum spanning tree во граф. Тоа го прави функцијата span().

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

Прим има сложеност V log E, и во најлош случај се пушта E пати, така да сложеноста на ова решение е V * E * log E, што комотно поминува во дадените ограничувања.

Постои уште едно решение за 100 поени, со користење на Прим заедно со Union-Find структура и алгоритам, ама сметам дека тоа е доста потешко од ова...
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team