Pasha has a wooden stick of some positive integer length n. He wants to perform exactly three cuts to get four parts of the stick. Each part must have some positive integer length and the sum of these lengths will obviously be n.
Pasha likes rectangles but hates squares, so he wonders, how many ways are there to split a stick into four parts so that it's possible to form a rectangle using these parts, but is impossible to form a square.
Your task is to help Pasha and count the number of such ways. Two ways to cut the stick are considered distinct if there exists some integer x, such that the number of parts of length x in the first way differ from the number of parts of length x in the second way.
The first line of the input contains a positive integer n (1 ≤ n ≤ 2·109) — the length of Pasha's stick.
The output should contain a single integer — the number of ways to split Pasha's stick into four parts of positive integer length so that it's possible to make a rectangle by connecting the ends of these parts, but is impossible to form a square.
6
1
20
4
There is only one way to divide the stick in the first sample {1, 1, 2, 2}.
Four ways to divide the stick in the second sample are {1, 1, 9, 9}, {2, 2, 8, 8}, {3, 3, 7, 7} and {4, 4, 6, 6}. Note that {5, 5, 5, 5} doesn't work.
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
![](https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int main() 5 { 6 int n; 7 int i,j,k; 8 scanf("%d",&n); 9 if(n%2==0) 10 { 11 int ans=n/4; 12 if(n%4==0) 13 ans--; 14 printf("%d ",ans); 15 } 16 else 17 printf("0 "); 18 }
Vika has n jars with paints of distinct colors. All the jars are numbered from 1 to n and the i-th jar contains ai liters of paint of color i.
Vika also has an infinitely long rectangular piece of paper of width 1, consisting of squares of size 1 × 1. Squares are numbered 1, 2, 3and so on. Vika decided that she will start painting squares one by one from left to right, starting from the square number 1 and some arbitrary color. If the square was painted in color x, then the next square will be painted in color x + 1. In case of x = n, next square is painted in color 1. If there is no more paint of the color Vika wants to use now, then she stops.
Square is always painted in only one color, and it takes exactly 1 liter of paint. Your task is to calculate the maximum number of squares that might be painted, if Vika chooses right color to paint the first square.
The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of jars with colors Vika has.
The second line of the input contains a sequence of integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is equal to the number of liters of paint in the i-th jar, i.e. the number of liters of color i that Vika has.
The only line of the output should contain a single integer — the maximum number of squares that Vika can paint if she follows the rules described above.
5
2 4 2 3 3
12
3
5 5 5
15
6
10 10 10 1 10 10
11
In the first sample the best strategy is to start painting using color 4. Then the squares will be painted in the following colors (from left to right): 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5.
In the second sample Vika can start to paint using any color.
In the third sample Vika should start painting using color number 5.
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
![](https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int inf=0x3f3f3f3f; 4 int a[200005]; 5 int main() 6 { 7 int n; 8 int i,j,k; 9 scanf("%d",&n); 10 int mi=inf,ma=0; 11 for(i=1;i<=n;i++) 12 { 13 scanf("%d",&a[i]); 14 if(a[i]<mi) 15 mi=a[i]; 16 } 17 int x=0; 18 for(i=1;i<=n;i++) 19 { 20 if(a[i]==mi) 21 x=0; 22 else 23 x++; 24 if(x>ma) 25 ma=x; 26 } 27 for(i=1;i<=n;i++) 28 { 29 if(a[i]==mi) 30 break; 31 x++; 32 if(x>ma) 33 ma=x; 34 } 35 printf("%I64d ",1ll*mi*n+1ll*ma); 36 }
The semester is already ending, so Danil made an effort and decided to visit a lesson on harmony analysis to know how does the professor look like, at least. Danil was very bored on this lesson until the teacher gave the group a simple task: find 4 vectors in 4-dimensional space, such that every coordinate of every vector is 1 or - 1 and any two vectors are orthogonal. Just as a reminder, two vectors in n-dimensional space are considered to be orthogonal if and only if their scalar product is equal to zero, that is:
![](http://codeforces.com/predownloaded/54/c0/54c00469bf0b7938e8dae7c67efac5401de9ae35.png)
Danil quickly managed to come up with the solution for this problem and the teacher noticed that the problem can be solved in a more general case for 2k vectors in 2k-dimensinoal space. When Danil came home, he quickly came up with the solution for this problem. Can you cope with it?
The only line of the input contains a single integer k (0 ≤ k ≤ 9).
Print 2k lines consisting of 2k characters each. The j-th character of the i-th line must be equal to ' * ' if the j-th coordinate of the i-th vector is equal to - 1, and must be equal to ' + ' if it's equal to + 1. It's guaranteed that the answer always exists.
If there are many correct answers, print any.
2
++**
+*+*
++++
+**+
Consider all scalar products in example:
- Vectors 1 and 2: ( + 1)·( + 1) + ( + 1)·( - 1) + ( - 1)·( + 1) + ( - 1)·( - 1) = 0
- Vectors 1 and 3: ( + 1)·( + 1) + ( + 1)·( + 1) + ( - 1)·( + 1) + ( - 1)·( + 1) = 0
- Vectors 1 and 4: ( + 1)·( + 1) + ( + 1)·( - 1) + ( - 1)·( - 1) + ( - 1)·( + 1) = 0
- Vectors 2 and 3: ( + 1)·( + 1) + ( - 1)·( + 1) + ( + 1)·( + 1) + ( - 1)·( + 1) = 0
- Vectors 2 and 4: ( + 1)·( + 1) + ( - 1)·( - 1) + ( + 1)·( - 1) + ( - 1)·( + 1) = 0
- Vectors 3 and 4: ( + 1)·( + 1) + ( + 1)·( - 1) + ( + 1)·( - 1) + ( + 1)·( + 1) = 0
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
![](https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 char a[600][600]; 5 int main() 6 { 7 8 int k,n=1; 9 int i,j,l; 10 scanf("%d",&k); 11 a[1][1]='+'; 12 for(i=1;i<=k;i++) 13 { 14 for(j=1;j<=n;j++) 15 { 16 for(l=1;l<=n;l++) 17 { 18 a[j][l+n]=a[j][l]; 19 } 20 for(l=1;l<=n;l++) 21 { 22 if(a[j][l]=='+') 23 a[j+n][l]='*'; 24 else 25 a[j+n][l]='+'; 26 a[j+n][l+n]=a[j][l]; 27 } 28 } 29 n=n*2; 30 } 31 for(i=1;i<=n;i++) 32 { 33 for(j=1;j<=n;j++) 34 { 35 printf("%c",a[i][j]); 36 } 37 printf(" "); 38 } 39 return 0; 40 }
Vika has an infinite sheet of squared paper. Initially all squares are white. She introduced a two-dimensional coordinate system on this sheet and drew n black horizontal and vertical segments parallel to the coordinate axes. All segments have width equal to 1 square, that means every segment occupy some set of neighbouring squares situated in one row or one column.
Your task is to calculate the number of painted cells. If a cell was painted more than once, it should be calculated exactly once.
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of segments drawn by Vika.
Each of the next n lines contains four integers x1, y1, x2 and y2 ( - 109 ≤ x1, y1, x2, y2 ≤ 109) — the coordinates of the endpoints of the segments drawn by Vika. It is guaranteed that all the segments are parallel to coordinate axes. Segments may touch, overlap and even completely coincide.
Print the number of cells painted by Vika. If a cell was painted more than once, it should be calculated exactly once in the answer.
3
0 1 2 1
1 4 1 2
0 3 2 3
8
4
-2 -1 2 -1
2 1 -2 1
-1 -2 -1 2
1 2 1 -2
16
In the first sample Vika will paint squares (0, 1), (1, 1), (2, 1), (1, 2), (1, 3), (1, 4), (0, 3) and (2, 3).
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
![](https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int inf=0x3f3f3f3f; 4 struct Node 5 { 6 int u; 7 int v; 8 int h; 9 int c; 10 }; 11 12 Node a[200005],e[100005],f[100005]; 13 int tree[200005],n,l,m1,m2,num,b[200005]; 14 long long sum; 15 map <int,int> d; 16 17 void add(int k,int val) 18 { 19 while(k<=num) 20 { 21 tree[k]+=val; 22 k+=k&-k; 23 } 24 } 25 26 int read(int k) 27 { 28 int Sum=0; 29 while(k) 30 { 31 Sum+=tree[k]; 32 k-=k&-k; 33 } 34 return Sum; 35 } 36 37 bool cmp(Node o,Node p) 38 { 39 if(o.h!=p.h) 40 { 41 return o.h<p.h; 42 } 43 else 44 return o.u<p.u; 45 } 46 47 bool cmp2(Node o,Node p) 48 { 49 if(o.h!=p.h) 50 { 51 return o.h<p.h; 52 } 53 else 54 { 55 return o.c>p.c; 56 } 57 } 58 59 void Unite() 60 { 61 int i,j,now,newu,newv; 62 sort(e+1,e+m1+1,cmp); 63 sort(f+1,f+m2+1,cmp); 64 65 now=inf; 66 for(i=1;i<=m1;i++) 67 { 68 if(e[i].h!=now) 69 { 70 //printf("h "); 71 if(now!=inf) 72 { 73 l++; 74 a[l].u=now,a[l].h=newu,a[l].c=1; 75 l++; 76 a[l].u=now,a[l].h=newv,a[l].c=-1; 77 sum=sum+newv-newu+1; 78 if(d[now]!=1) 79 { 80 b[++num]=now;d[now]=1; 81 } 82 } 83 now=e[i].h; 84 newu=e[i].u,newv=e[i].v; 85 } 86 else 87 { 88 if(e[i].u<=newv) 89 { 90 newv=max(newv,e[i].v); 91 } 92 else 93 { 94 l++; 95 a[l].u=now,a[l].h=newu,a[l].c=1; 96 l++; 97 a[l].u=now,a[l].h=newv,a[l].c=-1; 98 sum=sum+newv-newu+1; 99 if(d[now]!=1) 100 { 101 b[++num]=now;d[now]=1; 102 } 103 newu=e[i].u,newv=e[i].v; 104 } 105 } 106 } 107 if(now!=inf) 108 { 109 l++; 110 a[l].u=now,a[l].h=newu,a[l].c=1; 111 l++; 112 a[l].u=now,a[l].h=newv,a[l].c=-1; 113 sum=sum+newv-newu+1; 114 if(d[now]!=1) 115 { 116 b[++num]=now;d[now]=1; 117 } 118 } 119 //printf("^%I64d ",sum); 120 now=inf; 121 for(i=1;i<=m2;i++) 122 { 123 if(f[i].h!=now) 124 { 125 if(now!=inf) 126 { 127 l++; 128 a[l].u=newu,a[l].v=newv,a[l].h=now,a[l].c=0; 129 sum=sum+newv-newu+1; 130 if(d[newu]!=1) 131 { 132 b[++num]=newu;d[newu]=1; 133 } 134 if(d[newv]!=1) 135 { 136 b[++num]=newv;d[newv]=1; 137 } 138 } 139 now=f[i].h; 140 newu=f[i].u,newv=f[i].v; 141 } 142 else 143 { 144 if(f[i].u<=newv) 145 { 146 newv=max(newv,f[i].v); 147 } 148 else 149 { 150 l++; 151 a[l].u=newu,a[l].v=newv,a[l].h=now,a[l].c=0; 152 sum=sum+newv-newu+1; 153 if(d[newu]!=1) 154 { 155 b[++num]=newu;d[newu]=1; 156 } 157 if(d[newv]!=1) 158 { 159 b[++num]=newv;d[newv]=1; 160 } 161 newu=f[i].u,newv=f[i].v; 162 } 163 } 164 } 165 if(now!=inf) 166 { 167 l++; 168 a[l].u=newu,a[l].v=newv,a[l].h=now,a[l].c=0; 169 sum=sum+newv-newu+1; 170 if(d[newu]!=1) 171 { 172 b[++num]=newu;d[newu]=1; 173 } 174 if(d[newv]!=1) 175 { 176 b[++num]=newv;d[newv]=1; 177 } 178 } 179 } 180 181 int main() 182 { 183 int i,j; 184 int x1,x2,y1,y2; 185 memset(tree,0,sizeof(tree));d.clear(); 186 m1=0,m2=0,l=0,num=0; sum=0; 187 188 scanf("%d",&n); 189 for(i=1;i<=n;i++) 190 { 191 scanf("%d %d %d %d",&x1,&y1,&x2,&y2); 192 193 if(x1==x2 && y1!=y2) //垂直 194 { 195 if(y1>y2) 196 swap(y1,y2); 197 m1++; 198 e[m1].u=y1,e[m1].v=y2,e[m1].h=x1,e[m1].c=1; 199 } 200 else //水平 201 { 202 if(x1>x2) 203 swap(x1,x2); 204 m2++; 205 f[m2].u=x1,f[m2].v=x2,f[m2].h=y1,f[m2].c=2; 206 } 207 } 208 209 Unite(); 210 sort(b+1,b+num+1); 211 sort(a+1,a+l+1,cmp2); 212 //printf("%d %d %d %d ",m1,m2,num,l); 213 //printf("%I64d ",sum); 214 for(i=1;i<=l;i++) 215 { 216 if(a[i].c==0) 217 { 218 int s; 219 x1=lower_bound(b+1,b+num+1,a[i].u)-b; 220 x2=lower_bound(b+1,b+num+1,a[i].v)-b; 221 s=read(x2)-read(x1-1); 222 //printf("^^%d:%d %d:%d %d ",x1,read(x1-1),x2,read(x2),s); 223 sum=sum-s; 224 } 225 else 226 { 227 x1=lower_bound(b+1,b+num+1,a[i].u)-b; 228 //printf("^^^%d %d ",x1,a[i].c); 229 add(x1,a[i].c); 230 } 231 } 232 233 printf("%I64d ",sum); 234 235 }