#include <iostream> using namespace std; int main() { int t; cin>>t; int wynik[t]; for(int prz=0; prz<t; prz++) { char ch; int n; cin>>n; int a[n+2], b[n+2]; a[0]=a[n+1]=2; for(int i=1; i<n+1; i++) { cin>>ch; a[i]=ch-'0'; } int mi=1; while(mi!=0) { int k=0,j,m=0; //m - max, mi - max_index mi = 0; while(a[k]!=0 && k<n+2) k++; while(k<n+2) //szukanie optymalnego { j=k; while(a[k]==0) k++; if(a[j-1]==1 && a[k]==1 && k-j>m) { mi=j; m=k-j; } if(a[j-1]==1 && a[k]==2 && k-j+1>m) { mi=j; m=k-j+1; } if(a[j-1]==2 && a[k]==1 && k-j+1>m) { mi=k-1; m=k-j+1; } while(a[k]!=0 && k<n+2) k++; } if(mi!=0) { a[mi]=2; //szczepienie for(int i=1; i<n+1; i++) { if(a[i]==2) b[i]=2; else if(a[i-1]==1 || a[i]==1 || a[i+1]==1) b[i]=1; else b[i]=0; } for(int i=1; i<n+1; i++) a[i] = b[i]; } } wynik[prz]=0; for(int i=1; i<n+1; i++) if(a[i]==1) wynik[prz]++; } for(int prz=0; prz<t; prz++) cout<<wynik[prz]<<endl; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include <iostream> using namespace std; int main() { int t; cin>>t; int wynik[t]; for(int prz=0; prz<t; prz++) { char ch; int n; cin>>n; int a[n+2], b[n+2]; a[0]=a[n+1]=2; for(int i=1; i<n+1; i++) { cin>>ch; a[i]=ch-'0'; } int mi=1; while(mi!=0) { int k=0,j,m=0; //m - max, mi - max_index mi = 0; while(a[k]!=0 && k<n+2) k++; while(k<n+2) //szukanie optymalnego { j=k; while(a[k]==0) k++; if(a[j-1]==1 && a[k]==1 && k-j>m) { mi=j; m=k-j; } if(a[j-1]==1 && a[k]==2 && k-j+1>m) { mi=j; m=k-j+1; } if(a[j-1]==2 && a[k]==1 && k-j+1>m) { mi=k-1; m=k-j+1; } while(a[k]!=0 && k<n+2) k++; } if(mi!=0) { a[mi]=2; //szczepienie for(int i=1; i<n+1; i++) { if(a[i]==2) b[i]=2; else if(a[i-1]==1 || a[i]==1 || a[i+1]==1) b[i]=1; else b[i]=0; } for(int i=1; i<n+1; i++) a[i] = b[i]; } } wynik[prz]=0; for(int i=1; i<n+1; i++) if(a[i]==1) wynik[prz]++; } for(int prz=0; prz<t; prz++) cout<<wynik[prz]<<endl; } |