Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //problema Virgule
- #include <fstream>
- #include <cstring>
- using namespace std;
- ifstream cin("virgule.in");
- ofstream cout("virgule.out");
- char s[100];
- bool sol[100],poz[101],first=true;
- int gc,grd=0,n;
- bool cmp(char *s,int b1,int e1,int b2,int e2)
- {
- while(s[b1]=='0' && b1<e1)
- b1++;
- while(s[b2]=='0' && b2<e2)
- b2++;
- if(e1-b1!=e2-b2)
- return (e1-b1)>(e2-b2);
- while(s[b1]==s[b2] && b1<e1)
- {
- b1++;b2++;
- }
- return s[b1]>s[b2];
- }
- void verif(char *s)
- {
- if(first==true)
- {
- grd=gc;
- for(int i=0; i<n; i++)
- sol[i]=poz[i];
- first=false;
- }
- else if(gc==grd)
- {
- int b1=0,e1=1,b2=0,e2=1;
- while(e1<n && e2<n)
- {
- while(poz[e1]!=1 && e1<n)
- e1++;
- while(sol[e2]!=1 && e2<n)
- e2++;
- bool v1=cmp(s,b1,e1-1,b2,e2-1);
- bool v2=cmp(s,b2,e2-1,b1,e1-1);
- if(v1!=v2)
- {
- if(v1)
- {
- for(int i=0; i<n; i++)
- sol[i]=poz[i];
- }
- return;
- }
- else
- {
- b1=e1++;
- b2=e2++;
- }
- }
- }
- }
- void bckt(char *s,int b,int e)
- {
- if(b==0)
- {
- verif(s);
- return;
- }
- for(int i=b-1; i>=0; i--)
- {
- if(cmp(s,b,e,i,b-1)){
- poz[i]=1;
- bckt(s,i,b-1);
- poz[i]=0;
- }
- else
- break;
- }
- }
- void afisare(char *s)
- {
- cout<<s[0];
- for(int i=1; i<n; i++)
- {
- if(sol[i])
- cout<<',';
- cout<<s[i];
- }
- }
- int main()
- {
- cin.getline(s,100);
- n=strlen(s);
- for(int i=n-1; i>=0 && (first || s[i]=='0'); i--)
- {
- gc=n-1;
- poz[i]=1;
- bckt(s,i,n-1);
- poz[i]=0;
- }
- afisare(s);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement