Author |
Message |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 04/04/2011 18:21:08
|
FREEZX
   
Joined: 16/02/2010 19:32:31
Messages: 33
Offline
|
Ајмо ставајте ваши решенија за задачите од државен. Еве ги моите:
Одземање:
- #include <iostream>
- using namespace std;
-
- void bubblesort(string &a)
- {
- char tmp;
- for(int i=0; i<a.length(); i++)
- {
- for(int j=0; j<a.length()-1; j++)
- {
- if(a[j]>a[j+1])
- {
- tmp=a[j];
- a[j]=a[j+1];
- a[j+1]=tmp;
- }
- }
- }
- }
-
- void bubblesortrev(string &a)
- {
- char tmp;
- for(int i=0; i<a.length(); i++)
- {
- for(int j=0; j<a.length()-1; j++)
- {
- if(a[j]<a[j+1])
- {
- tmp=a[j];
- a[j]=a[j+1];
- a[j+1]=tmp;
- }
- }
- }
- }
-
- int main()
- {
- char min='9';
- string broj, minbroj;
- cin>>broj;
- minbroj=broj;
- bubblesort(minbroj);
- bubblesortrev(broj);
- for(int i=0; i<broj.length(); i++)
- {
- if(broj[i]-minbroj[i]+'0'<'0')
- {
- for(int j=i-1; j>=0; j--)
- {
- if(broj[j]-1>='0')
- {
- broj[j]--;
- break;
- }
- else
- {
- broj[j]='9';
- }
- }
- broj[i]=broj[i]-minbroj[i]+'9'+1;
- }
- else broj[i]=broj[i]-minbroj[i]+'0';
- }
- int loc=broj.length()-1;
- for(int i=0; i<broj.length(); i++)
- {
- if(broj[i]=='0')
- continue;
- else
- {
- loc=i;
- break;
- }
- }
- for(int i=loc; i<broj.length(); i++)
- {
- cout<<broj[i];
- }
- return 0;
- }
Прегледување:
- #include <iostream>
- using namespace std;
-
- int main()
- {
- int n, k, kv=0, minvreme=9999999, minkom=9999999;
- cin>>n>>k;
- for(int i=1; i<999999; i++)
- {
- for(int j=1; j<i; j++)
- {
- kv+=j;
- }
- if((n%i==0)&&(kv*k+n/i<minvreme))
- {
- minvreme=kv*k+n/i;
- }
- else if ((n%i!=0)&&(kv*k+n/i+1<minvreme))
- minvreme=kv*k+n/i+1;
-
- else break;
- kv=0;
- minkom=i;
- }
- cout<<minkom;
- return 0;
- }
|
|
 |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 04/04/2011 18:46:51
|
FREEZX
   
Joined: 16/02/2010 19:32:31
Messages: 33
Offline
|
Регистрација:
- #include <iostream>
- #include <sstream>
-
- using namespace std;
-
- int main()
- {
- stringstream ss;
- string a, rez, plus;
- int n, plu=1;
- cin>>a>>n;
- rez=a;
- string users[n];
- for(int i=0; i<n; i++)
- {
- cin>>users[i];
- }
- for(int i=0; i<n; i++)
- {
- if(users[i]==rez)
- {
- ss<<plu;
- ss>>plus;
- rez=a+plus;
- ss.str("");
- ss.clear();
- plu++;
- i=-1;
- }
- }
- cout<<rez;
- return 0;
- }
|
|
 |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 04/04/2011 19:49:11
|
FREEZX
   
Joined: 16/02/2010 19:32:31
Messages: 33
Offline
|
Финкимен:
- #include <iostream>
- using namespace std;
-
- int r, c, minpole=999999, minr, minc;
- int pole[50][50];
-
- bool check()
- {
- for(int i=0; i<r; i++)
- {
- for(int j=0; j<c; j++)
- {
- if(pole[i][j]!=-1)
- return false;
- }
- }
- return true;
- }
-
- void findmin()
- {
- for(int i=0; i<r; i++)
- {
- for(int j=0; j<c; j++)
- {
- if((pole[i][j]!=-1)&&(pole[i][j]<minpole))
- {
- minpole=pole[i][j];
- minr=i;
- minc=j;
- }
- }
- }
- }
-
- void fill(int x, int y)
- {
- int val=pole[x][y];
- pole[x][y]=-1;
- if((x+1<r)&&(pole[x+1][y]>=val)) fill(x+1, y);
- if((x-1>=0)&&(pole[x-1][y]>=val)) fill(x-1, y);
- if((y+1<c)&&(pole[x][y+1]>=val)) fill(x, y+1);
- if((y-1>=0)&&(pole[x][y-1]>=val)) fill(x, y-1);
- }
-
- int main()
- {
- int res=0;
- cin>>r>>c;
- for(int i=0; i<r; i++)
- {
- for(int j=0; j<c; j++)
- {
- cin>>pole[i][j];
- if(pole[i][j]<minpole)
- {
- minr=i;
- minc=j;
- minpole=pole[i][j];
- }
- }
- }
- while(check()==false)
- {
- fill(minr, minc);
- res++;
- minpole=999999;
- findmin();
- }
- cout<<res;
- return 0;
- }
|
|
 |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 04/04/2011 23:56:15
|
FREEZX
   
Joined: 16/02/2010 19:32:31
Messages: 33
Offline
|
Ајде камо open-source дух! Моиве решенија ги ставив на Wiki-то
|
|
 |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 05/04/2011 00:03:39
|
bedzo
   
Joined: 18/01/2011 02:05:03
Messages: 234
Offline
|
Odzemanje:
- #include<iostream>
- #include<string>
- #include<algorithm>
- using namespace std;
-
- int main()
- {
- string a;
- int a1[101],b[101],i,j=0,h[101],z=0,po[101],fe=0;
- cin>>a;
- for(i=0;i<a.size();i++)
- {
- a1[i]=a[i]-48;
- b[i]=a1[i];
- }
- sort(a1,a1+a.size());
- sort(b,b+a.size());
- reverse(b,b+a.size());
- for(i=a.size()-1;i>-1;i--)
- {
- if(b[i-1]<0)
- {
- b[i-1]+=10;
- b[i-2]-=1;
- }
- if(b[i]<a1[i])
- {
- b[i]+=10;
- b[i-1]-=1;
- if(b[i-1]<0)
- {
- b[i-1]+=10;
- b[i-2]-=1;
- }
- }
- h[i]=b[i]-a1[i];
- }
- while (h[fe]==0) fe++;
- if(fe==a.size()) cout<<"0";
- else
- {
- for(i=fe;i<a.size();i++)
- {
- cout<<h[i];
- }
- }
- return 0;
- }
This message was edited 2 times. Last update was at 05/04/2011 01:07:18
|
|
 |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 05/04/2011 20:04:40
|
obi1kenobi
   
Joined: 18/02/2010 20:01:33
Messages: 168
Offline
|
Задача Прекин, државен 2011 напредна група - задача 3.
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<stack>
- #include<vector>
- #include<algorithm>
- #include<map>
- #include<set>
- #include<list>
- #include<queue>
- #include<cmath>
- #include<ctime>
- #include<fstream>
- #include<string>
- #include<cstring>
- #include<climits>
-
- using namespace std;
-
- #define sz(x) (int)((x).size())
- #define all(c) (c).begin(),(c).end()
- #define DBGM(x,y) if(DEBUG) cout << #x << ' ' << #y << ": " << x << ' ' << y << '\n'
- #define MSI(x,y) memset((x),(y),sizeof(x));
-
- #define DEBUG true;
-
- class dijk
- {
- public:
- int nd,cost,orig;
- };
-
- bool operator<(dijk a,dijk b)
- {
- if(a.cost==b.cost) return a.nd>b.nd;
- return a.cost>b.cost;
- }
-
- list<int> bgn,en;
- int res;
- int remnr;
- int n,m;
- int taken;
-
- list<int> cnn[101];
- list<int> cost[101];
- bool vis[101],add;
- priority_queue<dijk> * que;
-
- void proc(dijk in)
- {
- if(vis[in.nd]) return;
-
- dijk tmp;
- list<int>::iterator it,it2;
-
- if(add)
- {
- bgn.push_back(in.orig);
- en.push_back(in.nd);
- }
-
- vis[in.nd]=true;
- taken++;
- res+=in.cost;
- it=cnn[in.nd].begin();
- it2=cost[in.nd].begin();
-
- while(it!=cnn[in.nd].end())
- {
- if(!vis[*it])
- {
- tmp.nd=*it;
- tmp.cost=*it2;
- tmp.orig=in.nd;
- que->push(tmp);
- }
- it++;
- it2++;
- }
-
- }
-
- int span()
- {
- MSI(vis,0);
- res=0;
- taken=0;
- dijk tmp;
- tmp.nd=0;
- tmp.cost=0;
- tmp.orig=-1;
-
- que->push(tmp);
-
- while(taken<n && !que->empty())
- {
- tmp=que->top();
- que->pop();
-
- proc(tmp);
- }
- if(taken<n)
- {
- return INT_MAX;
- }
- return res;
- }
-
- int main()
- {
- int a,b,c,i,j,ares,bres=INT_MAX;
- que=new priority_queue<dijk>;
- add=true;
-
- scanf("%d %d",&n,&m);
-
- for(i=0;i<m;i++)
- {
- scanf("%d %d %d",&a,&b,&c);
- a--;
- b--;
- cnn[a].push_back(b);
- cost[a].push_back(c);
- cnn[b].push_back(a);
- cost[b].push_back(c);
- }
-
- ares=span();
- add=false;
-
- list<int>::iterator ita,itb,itan,itbn,itc,itcn,itd,itdn;
-
- while(bgn.begin()!=bgn.end())
- {
- if(*bgn.begin()==-1 || *en.begin()==-1)
- {
- bgn.pop_front();
- en.pop_front();
- continue;
- }
-
- ita=cnn[*bgn.begin()].begin();
- itb=cost[*bgn.begin()].begin();
- itc=cnn[*en.begin()].begin();
- itd=cost[*en.begin()].begin();
- while(*ita!=*en.begin())
- {
- ita++;
- itb++;
- }
- itan=ita;
- itan++;
- cnn[*bgn.begin()].erase(ita);
- remnr=*itb;
- itbn=itb;
- itbn++;
- cost[*bgn.begin()].erase(itb);
-
- while(*itc!=*bgn.begin())
- {
- itc++;
- itd++;
- }
- itcn=itc;
- itcn++;
- itdn=itd;
- itdn++;
- cnn[*en.begin()].erase(itc);
- cost[*en.begin()].erase(itd);
-
- delete que;
- que=new priority_queue<dijk>;
-
- bres=min(bres,span());
-
- ita=itan;
- itb=itbn;
- itc=itcn;
- itd=itdn;
- cnn[*bgn.begin()].push_back(*en.begin());
- cnn[*en.begin()].push_back(*bgn.begin());
- cost[*bgn.begin()].push_back(remnr);
- cost[*en.begin()].push_back(remnr);
- bgn.pop_front();
- en.pop_front();
- }
- printf("%d %d\n",min(ares,bres),max(ares,bres));
-
- return 0;
- }
This message was edited 2 times. Last update was at 05/04/2011 20:06:06
|
|
 |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 05/04/2011 22:28:41
|
bedzo
   
Joined: 18/01/2011 02:05:03
Messages: 234
Offline
|
- #include<iostream>
- using namespace std;
- int main()
- {
- int m,n,i,sum1,sum=500000,raz=0;
- cin>>m>>n;
- for(i=1;i<500000;i++)
- {
- for(int j=1;j<i;j++)
- {
- raz+=j;
-
- }
- if((m%i==0) && (raz*n + m*i<sum))
- {
- sum = raz*n + m*i;
- }
- else if((m%i==0) && (raz*n + m*i+1<sum))
- {
- sum = raz*n + m*i +1;
- }
- else break;
- raz=0;
- sum1=i;
- }
- cout<<sum1;
- return 0;
- }
|
|
 |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 05/04/2011 22:45:47
|
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
|
|
 |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 05/04/2011 22:55:57
|
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
|
|
 |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 05/04/2011 23:55:21
|
FREEZX
   
Joined: 16/02/2010 19:32:31
Messages: 33
Offline
|
ова е уствари дфс решение, со тоа што секогаш се означува поминатото поле со -1. Почнуваш од минимална висини и се движиш кон поголемите колку што можеш после пак бараш друго минимално поле па и од тоа почнуваш, и така на крајот све ќе поминеш и ќе изброиш колку пати така требало да се бара минимум. секое поминување на еден дфс проверуваш дали сите членови се -1. Ако се, прекинуваш и печатиш решение
|
|
 |
![[Post New]](/jforum/templates/default/images/icon_minipost_new.gif) 06/04/2011 20:01:46
|
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 структура и алгоритам, ама сметам дека тоа е доста потешко од ова...
|
|
 |
|
|
|