2017 8th Blue Bridge Cup group a provincial tournament

A. maze （5 branch ）
answer ：31

test questions A: maze
The total score of this question ：5 branch
【 Problem description 】
X A labyrinth playground on the planet is built on a hillside .
It is from 10x10 Made up of interconnected small rooms .
There is a big letter on the floor of the room .
Let's assume that the player is standing facing uphill , be ：
L Go to the room on the left ,
R Go to the room on the right ,
U It means walking up the slope ,
D It means going downhill .
X The inhabitants of the planet are a little lazy , Not willing to think .
They prefer to play games of luck . The same is true of this game ！
At the beginning , Helicopter handle 100 Players into a small room .
Players must move according to the letters on the ground .
The map of the maze is as follows ：
UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
Please calculate , Last , How many players will walk out of the maze ? Instead of going around in circles .
【 Answer submission 】
Please submit the integer , Represents the number of players walking out of the maze , Don't fill in any superfluous information .
If you don't understand the rules of the game , See a simplified one 4x4 Explanation of the maze ：

Ideas ：
The first way of thinking ： fingerprint . Simulate everyone's route directly on the draft paper , See if it can get out of the maze , Record the number of people who can go out .
The second way of thinking ：dfs. We use arrays vis[][] Whether the person who records a room is sure to get out of the maze （ That is, whether to search deeply ）, Using arrays a[][] Record whether the person in a room can get out of the maze （1 I can't ,2 It means yes ）. Then enumerate each location , If the location has been searched （ That is, to determine whether we can get out of the maze ）, Then skip ; Otherwise, follow the direction of its room , There are three situations ：
1. Go outside the maze , Then the location along the way a[i][j] All marked as 2.
2. Go to a searched but a[i][j]==0 The location of ： That is to say, I can circle , Then mark all the positions along the way 1.
3. Go to one that has been searched and a[i][j]!=0 The location of ： Then mark all the positions along the way a[i][j].

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
const int maxn=1e5+10;
int vis[12][12],a[12][12];   //1 It means you can't go out ,2 Can get out  
char s[12][12];
vector<pair<int,int> >g;
void dfs(int x,int y){
    
    if(x<1||x>10||y<1||y>10) {
    
		for(int i=0;i<g.size();i++)	a[g[i].first][g[i].second]=2;
		return ;
	}
	if(vis[x][y]) {
    
		if(a[x][y]==0){
    
			for(int i=0;i<g.size();i++)	a[g[i].first][g[i].second]=1;
		}
		else{
    
			for(int i=0;i<g.size();i++) a[g[i].first][g[i].second]=a[x][y];
		}
		return ;
	}
	vis[x][y]=1; g.push_back({
    x,y});
	if(s[x][y]=='U') dfs(x-1,y);
	else if(s[x][y]=='L') dfs(x,y-1);
	else if(s[x][y]=='R') dfs(x,y+1);
	else dfs(x+1,y);
}
int main(){
    
	for(int i=1;i<=10;i++){
    
		for(int j=1;j<=10;j++) {
    
		    cin>>s[i][j]; vis[i][j]=a[i][j]=0;
		}
	}
	int ans=0;
	for(int i=1;i<=10;i++){
    
		for(int j=1;j<=10;j++){
    
			if(vis[i][j]) continue;
			g.clear(); dfs(i,j);
		}
	} 
    for(int i=1;i<=10;i++) 
       for(int j=1;j<=10;j++)
       if(a[i][j]==2) ans++;
    cout<<ans<<endl;
	return 0;
} 

---

B. Grasshoppers （11 branch ）
answer ：20

test questions B: Grasshoppers
The total score of this question ：11 branch
9 A plate , Line up 1 A circle .
among 8 It's just a plate 8 A grasshopper , One is empty .
We numbered these grasshoppers clockwise as 1~8
Every grasshopper can jump to the next empty dish ,
You can also use a little more force , Jump over an adjacent grasshopper to an empty plate .
Please calculate , If you want the grasshoppers to line up counterclockwise ,
And keep the position of the empty disk unchanged （ That is to say 1-8 transposition ,2-7 transposition ,…）, At least how many jumps it takes ？

【 Answer submission 】
All you need to submit is an integer , Don't fill in any superfluous content or explanatory text .

Ideas ：BFS. Can't think of 17 The first few sign in questions of the Blue Bridge Cup in are so difficult , A little hit konjaku konjaku me ..... Let's put bfs The previous state is regarded as a string str1=“012345678”; The final result is str2=“087654321”. Because the characters in a certain position can only match the characters 0 In exchange for , Then it's equivalent to characters 0 Constantly changing positions . Remember character 0 The position in the string is x, There are four ways to change positions , namely x+1,x-1,x+2,x-2. And because it's a ring , We need to deal with these four situations in a circular way . Put every possible string s Through container map<string,int>mp Map to an integer ; This integer is the integer that needs to be changed at least .

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
const int maxn=1e5+10;
string str1="012345678",str2="087654321";
int d[5]={
    0,-1,-2,1,2};
queue<pair<string,int> >q;
map<string,int>mp;
int main(){
    
	q.push({
    str1,0});
	while(!q.empty()){
    
		string str=q.front().first;
		int x=q.front().second; q.pop();
		for(int i=1;i<=4;i++){
    
			int tx=(x+d[i]+9)%9;
			string s=str; swap(s[x],s[tx]);
			if(mp[s]!=0) continue; 
			mp[s]=mp[str]+1;
			q.push({
    s,tx});
			
		}
	}
	cout<<mp[str2]<<endl;
	return 0;
} 

---

C. Rubik's cube state （13 branch ）
answer ：

test questions C: Rubik's cube state
The total score of this question ：13 branch
【 Problem description 】
Second order cube is only 2 Layer's Cube , Only by 8 It's made up of small pieces .
Xiao Ming is very naughty , He just likes 3 Color , All the second-order Rubik's cube at home are painted again , as follows ：
front ： Orange
right side ： green
above ： yellow
left side ： green
below ： Orange
Back ： yellow
Please calculate , After this Rubik's cube is disrupted , How many different states are there .
If the two states are rotated by the cube as a whole , All sides are the same color , It's the same state .

【 Answer submission 】
You need to submit an integer . Don't fill in any superfluous information .

Ideas ：
Konjaku is not worthy to write him ....

---

D. Block segmentation （17 branch ）
answer ：509

test questions D: Block segmentation
The total score of this question ：17 branch
【 Problem description 】
6x6 Of the lattice , Cut in two along the edge of the grid .
The shape of the two parts should be exactly the same .
As shown in the following three figures ： It's a feasible segmentation .
Try to calculate ：
Including this 3 The method of seed division is inside , How many different segmentation methods are there .
Be careful ： Rotationally symmetric belongs to the same segmentation method .

【 Answer submission 】
You need to submit an integer , Please do not fill in any extra information .

Ideas ：
dfs+ thinking . This problem requires us to cut it along the edge of the square , Make the shape of the two parts cut completely symmetrical . We maintain every point on the sideline in a rectangular coordinate system , That is, the lower left corner is the coordinate （0,0）, The upper right corner is the coordinate （6,6）. Because we need to search out many different lines to make the two parts cut along the line symmetrical , Our best idea is Place the starting point at the center （3,3） On , Then search up, down, left and right in four different directions . And think about it , It's not hard to find out , The search boundary is when the coordinates of a point are located on the boundary of the grid , namely (0,y),(6,y),(x,0),(x,6) The above search ends , Add one to the result . Be careful ： This question needs to go back . And because of rotational symmetry, it belongs to the same kind , The result needs to be divided by 4

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
const int maxn=1e5+10;
int vis[10][10],ans=0;
int dx[5]={
    0,-1,0,1,0};
int dy[5]={
    0,0,1,0,-1};
void dfs(int x,int y){
    
	if(x==0||x==6||y==0||y==6){
    
		ans++;
		return ;
	}
	for(int i=1;i<=4;i++){
    
		int tx=x+dx[i],ty=y+dy[i];
		if(!vis[tx][ty]&&!vis[6-tx][6-ty]){
    
			vis[tx][ty]=1; vis[6-tx][6-ty]=1;
			dfs(tx,ty);
			vis[tx][ty]=0; vis[6-tx][6-ty]=0;
		
		}
	}
}
int main(){
    
	memset(vis,0,sizeof(vis));
	vis[3][3]=1;
	dfs(3,3); 
	cout<<ans/4<<endl;
	return 0;
} 

---

E. A string of letters （7 branch ）
answer ：f(a-1,b,c,n-1)+f(a,b-1,c,n-1)+f(a,b,c-1,n-1)

test questions E: A string of letters
The total score of this question ：7 branch
【 Problem description 】
from A,B,C this 3 One letter can make up a lot of strings .
such as ：“A”,“AB”,“ABC”,“ABA”,“AACBB” …
Now? , Xiao Ming is thinking about a problem ：
If there is a limit to the number of letters per letter , How many strings of known length can be formed ？
He asked his good friend to help , And soon I got the code ,
The solution is super simple , The most important part, however, is vague .
【 Answer submission 】
Please analyze the program carefully , And fill in the missing code in the underlined section .
【 Sample explanation 】
For the test data above the source code , The result of Xiaoming's mental arithmetic should be ：
6
19

The procedure given in the title is as follows ：

#include <stdio.h>
int f(int a, int b, int c, int n)
{
    
    if(a<0 || b<0 || c<0) return 0;
    if(n==0) return 1; 

    return ______________________________________ ;  //  Fill in the blanks 
}
int main()
{
    
    printf("%d\n", f(1,1,1,2));
    printf("%d\n", f(1,2,3,3));
    return 0;
}

Ideas ：
Dynamic programming dp.f(a,b,c,n) Express a Characters ’A’,b Characters ‘B’ and c Characters ‘C’ The length of the composition is n The number of types of strings . The topic has defined the representation of state for us , We just need to find a reasonable transfer equation . Obviously, the length is n The number of types and length of strings are n-1 The number of string types is related ; namely The length is n The string is composed of a length of n-1 Add characters to the string of ’a’ Or character ’b’ Or character ’c’ Come to . So the transfer equation is f(a,b,c,n)=f(a-1,b,c,n-1)+f(a,b-1,c,n-1)+f(a,b,c-1,n-1).

---

F. The largest common substring (9 branch ）
answer ：a[i-1][j-1]+1

test questions F: The largest common substring
The time limit : 1.0s Memory limit : 256.0MB The total score of this question ：9 branch
【 Problem description 】
　 The problem of the maximum common substring length is ：
Find the maximum length of all substrings of two strings that can match .
such as ：“abcdkkk” and “baabcdadabc”,
The longest common substring that can be found is "abcd", So the maximum common substring length is 4.
The following procedure is solved by matrix method , This is a relatively effective solution for the case of small string size .
Please analyze the idea of the solution , And complete the missing code in the underlined part .

The procedure given in the title is as follows ：

#include <stdio.h>
#include <string.h>
#define N 256
int f(const char* s1, const char* s2)
{
    undefined
   int a[N][N];
   int len1 = strlen(s1);
   int len2 = strlen(s2);
   int i,j;
   memset(a,0,sizeof(int)*N*N);
   int max = 0;
   for(i=1; i<=len1; i++){
    undefined
       for(j=1; j<=len2; j++){
    undefined
          if(s1[i-1]==s2[j-1]) {
    undefined
              a[i][j] = __________________________;  // Fill in the blanks 
              if(a[i][j] > max) max = a[i][j];
            }
        }
    }
   return max;
}
int main(){
    undefined
   printf("%d\n", f("abcdkkk", "baabcdadabc"));
   return 0;
}

 

Ideas ：
dp. The largest common substring （LCS） Template code of Algorithm .

---

G. Regular problem (19 branch ）

test questions G: Regular problem
The time limit : 1.0s Memory limit : 256.0MB The total score of this question ：19 branch
【 Problem description 】
Consider a simple regular expression ：
　　 Only by x ( ) | Regular expressions composed of .
　　 Xiao Ming wants to find the length of the longest string that this regular expression can accept .
　　 for example ((xx|xxx)x|(x|xx))xx The longest string that can be accepted is ： xxxxxx, The length is 6.
【 Input format 】
　 One by x()| Regular expressions composed of . Input length is not more than 100, To guarantee legality .
【 Output format 】
　　 The length of the longest string that this regular expression can accept .
for example ,
【 The sample input 】
((xx|xxx)x|(x|xx))xx
【 Sample output 】
6
【 Evaluate use case size and conventions 】
Resource Convention ：
　　 Peak memory consumption （ Including virtual machines ） < 256M
　　CPU Consume < 1000ms
　　 Please output strictly as required , Don't print like that ：“ Please input …” Extra content of .
Be careful ：
　　main Function needs to return 0;
　　 Use only ANSI C/ANSI C++ standard ;
　　 Do not call special functions that depend on the compiled environment or operating system .
　　 All dependent functions must be explicitly in the source file #include
　　 Common header files cannot be omitted through engineering settings .
　　 When submitting a program , Pay attention to choosing the expected language type and compiler type .

Ideas ：
Konjaku is too delicious , I didn't understand the topic at first , I have no idea what regular expressions are ？？？ See the explanation of the boss later to understand the meaning , At first glance, it's just a Recursive question . But I don't know how to program this recursive program ？ Konjaku can only look for big guys everywhere , It's finally coming out . Because it is similar to the problem of expression evaluation , We need to traverse the string , So first of all Declare a global variable pos, Represents the current traversal position ; because "()" You can change the priority of the operation , So once you encounter characters ’(‘ You need to enter the recursive program ; Characters encountered ’)' You need to jump out of recursion , Return the result of this recursion ; And characters ’|' Is used to return left and right characters x The larger number of ; So when you encounter characters during traversal ’|‘, You need to record this time x The number of , And then from 0 Start recording x The number of , Last but not least max() Find the maximum number .
Time complexity ：O(n)

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
const int maxn=1e5+10;
string str;
int pos;
int dfs(){
    
	int ans=0,temp=0;
	while(pos<str.length()){
    
		if(str[pos]=='('){
    
			pos++; 
			temp+=dfs();
		}
		else if(str[pos]==')'){
    
			pos++; break;
		}
		else if(str[pos]=='|'){
    
			ans=max(ans,temp); temp=0; pos++;
		}
		else pos++,temp++;
	}
	ans=max(ans,temp);
	return ans;
}
int main(){
    
    cin>>str;
    cout<<dfs()<<endl;
	return 0;
} 

---

H. How many buns are there (21 branch ）

test questions H: How many buns are there
The time limit : 1.0s Memory limit : 256.0MB The total score of this question ：21 branch
【 Problem description 】
　　 Xiao Ming has breakfast in a bun shop almost every morning . He found that there was N Grow steamer , Among them the first i The kind of steamer can put Ai A steamed bun . Each kind of steamer has a lot of steamers , It can be thought of as an infinite cage .
　　 Whenever a customer wants to buy X A steamed bun , The uncle who sells steamed buns will quickly select a number of steamed buns , So that these cages happen to have X A steamed bun . Let's say there are 3 Grow steamer , You can put 3、4 and 5 A steamed bun . When customers want to buy 11 A bun , Uncle will choose 2 Cage 3 One more 1 Cage 5 One of the （ It is also possible to elect 1 Cage 3 One more 2 Cage 4 One of the ）.
　　 Of course, sometimes uncle baozi can't figure out the quantity customers want to buy . Let's say there are 3 Grow steamer , You can put 4、5 and 6 A steamed bun . And customers want to buy 7 A bun , Uncle can't make it out .
　　 Xiao Ming wants to know how many kinds of numbers can't be found by Uncle baozi .
【 Input format 】
The first line contains an integer N.(1 <= N <= 100)
following N Each line contains an integer Ai.(1 <= Ai <= 100)
【 Output format 】
An integer represents the answer . If you can't figure out an infinite number , Output INF.
　　 for example ,
【 The sample input 】
2
4
5
【 Sample output 】
6
【 The sample input 】
　2
　4
　6
【 Sample output 】
　INF
【 Evaluate use case size and conventions 】
Sample explanation
　　 For example 1, The uncountable number includes ：1, 2, 3, 6, 7, 11.
　　 For example 2, All the odd numbers can't come out , So there's an infinite number of .
Resource Convention ：
　　 Peak memory consumption （ Including virtual machines ） < 256M
　　CPU Consume < 1000ms
　　 Please output strictly as required , Don't print like that ：“ Please input …” Extra content of .
Be careful ：
　　main Function needs to return 0;
　　 Use only ANSI C/ANSI C++ standard ;
　　 Do not call special functions that depend on the compiled environment or operating system .
　　 All dependent functions must be explicitly in the source file #include
　　 Common header files cannot be omitted through engineering settings .
　　 When submitting a program , Pay attention to choosing the expected language type and compiler type .

Ideas ：
The first way of thinking ： violence . Because the sample scope is relatively small , We can solve it with pure violence ; We can 50000(50000 The above is also ok ) All possible integers within are stored in the container set< int>g in ; Because of each a[i]<=100; So we can verify the larger 100 Consecutive numbers , If a number appears in it and is not in the container , It means that there must be an infinite number of people who cannot get ; Otherwise, traverse the numbers 1~50000, Record the number of numbers that do not appear in the container , Output results .
Time complexity ：O(n* 50000* log(50000))
The second way of thinking ： Completely backpack +GCD. I recommend a blog with a particularly good explanation of this idea ：https://www.acwing.com/solution/content/17888/

violence AC Code ：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
const int maxn=1e5+10;
set<int>g;
int n,x,minn=INF,vis[maxn];
int main(){
    
    cin>>n;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
    
    	cin>>x;
    	if(!vis[x]) g.insert(x);
    	for(set<int>::iterator it=g.begin();;it++){
    
    		int y=x+*it;
    		if(y>50000) break;
    		g.insert(y);
		}
	}	
	int cnt=0,flag=0;
    for(int i=40000;i<=41000;i++) {
    
    	if(!g.count(i)) flag=1; 
	}
	if(flag) cout<<"INF"<<endl;
	else{
    
		for(int i=1;i<=40000;i++) if(!g.count(i)) cnt++;
		cout<<cnt<<endl;
	}
	return 0;
} 

---

I. Split chocolate (23 branch ）

test questions I: Split chocolate
The time limit : 1.0s Memory limit : 256.0MB The total score of this question ：23 branch
【 Problem description 】
There was... On children's day K Three children come to Xiaoming's house to visit . Xiao Ming took out his collection of chocolates to entertain the children .
　　 Xiao Ming has N A piece of chocolate , Among them the first i Block is Hi x Wi A rectangle of squares .
　　 For the sake of fairness , Xiaoming needs to come from here N Cut out a piece of chocolate K Give the children a piece of chocolate . The cut chocolate needs to satisfy ：
　　1. The shape is square , The side length is an integer
　　2. Same size
　　 For example, a piece of 6x5 The chocolate can be cut out 6 block 2x2 Of chocolate or 2 block 3x3 Of chocolate .
　　 Of course, children want to get as much chocolate as possible , You can help me Hi Calculate the maximum side length ？
【 Input format 】
　　 The first line contains two integers N and K.(1 <= N, K <= 100000)
　　 following N Each line contains two integers Hi and Wi.(1 <= Hi, Wi <= 100000)
　　 Input to ensure that each child can get at least one piece of 1x1 Of chocolate .
【 Output format 】
　　 Output the maximum possible side length of the cut square chocolate .
【 The sample input 】
2 10
6 5
5 6
【 Sample output 】
2
【 Evaluate use case size and conventions 】
Resource Convention ：
Peak memory consumption （ Including virtual machines ） < 256M
CPU Consume < 1000ms
　　 Please output strictly as required , Don't print like that ：“ Please input …” Extra content of .
　 Be careful ：
　　main Function needs to return 0;
　　 Use only ANSI C/ANSI C++ standard ;
　　 Do not call special functions that depend on the compiled environment or operating system .
　　 All dependent functions must be explicitly in the source file #include
　　 Common header files cannot be omitted through engineering settings .
　　 When submitting a program , Pay attention to choosing the expected language type and compiler type .

Ideas ：
Dichotomy . If you think of two points in this question , Then it's a two-point board problem .
Because we want everyone to get as much chocolate as possible , So for a certain side length , Can chocolate be divided into k Copies need to be used O(n) Time to check ; And because the side length of chocolate must belong to [1,100000] in , So we can get the result by dichotomy .
Time complexity ：O（n*log(n)）

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
const int maxn=1e5+10;
int h[maxn],w[maxn];
int n,k;
bool check(int x){
    
	int cnt=0;
	for(int i=1;i<=n;i++){
    
		cnt+=(h[i]/x)*(w[i]/x);
	}
	if(cnt>=k) return true;
	return false;
}
int main(){
    
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>h[i]>>w[i];
    int l=1,r=100000;
    while(l<r){
    
    	int mid=(l+r+1)>>1;
    	if(check(mid)) l=mid;
    	else r=mid-1;
	}
	cout<<l<<endl;
	return 0;
} 

---

J. Paint area (25 branch ）

test questions J: Paint area
The time limit : 1.0s Memory limit : 256.0MB The total score of this question ：25 branch
【 Problem description 】
　　X A group of archaeological robots on the planet are doing archaeology on a piece of ruins .
　　 The ground in this area is as hard as stone 、 Flat as a mirror .
　　 Management staff for convenience , Established a standard rectangular coordinate system .
　　 Every robot has its own specialty 、 great talent . They're also interested in different things .
　　 After all kinds of measurements , Each robot reports one or more rectangular areas , As a priority archaeological area .
　　 The format of rectangle is (x1,y1,x2,y2), Represents the coordinates of the two diagonal points of the rectangle .
　　 In order to stand out , The headquarters requires that all the selected rectangular areas of robots be painted yellow .
　　 Xiao Ming doesn't need to be a painter , It's just that he needs to calculate , How much paint does it take .
　　 In fact, it is not difficult , Just figure out how much area all the rectangles cover .
　　 Be careful , The rectangles may overlap .
　　 The input of this problem is several rectangles , The total area covered by the output is required .
　　
【 Input format 】
　　 first line , An integer n, How many rectangles are there (1<=n<10000)
　　 Next n That's ok , Each row has 4 It's an integer x1 y1 x2 y2, Space apart , Represents the coordinates of two diagonal vertices of a rectangle .(0<= x1,y1,x2,y2 <=10000)
【 Output format 】
　　 first line , An integer n, How many rectangles are there (1<=n<10000)
　　 Next n That's ok , Each row has 4 It's an integer x1 y1 x2 y2, Space apart , Represents the coordinates of two diagonal vertices of a rectangle .(0<= x1,y1,x2,y2 <=10000)
【 The sample input 】
3
1 5 10 10
3 1 20 20
2 7 15 17
【 Sample output 】
340
Another example ：
【 The sample input 】
3
5 2 10 6
2 7 12 10
8 1 15 15
【 Sample output 】
128
【 Data size and engagement 】
　 Resource Convention ：
　　 Peak memory consumption （ Including virtual machines ） < 256M
　　CPU Consume < 1000ms
　　 Please output strictly as required , Don't print like that ：“ Please input …” Extra content of .
　 Be careful ：
　　main Function needs to return 0;
　　 Use only ANSI C/ANSI C++ standard ;
　　 Do not call special functions that depend on the compiled environment or operating system .
　　 All dependent functions must be explicitly in the source file #include
　　 Common header files cannot be omitted through engineering settings .
　　 When submitting a program , Pay attention to choosing the expected language type and compiler type .

---

Ideas ：
violence . I am I want to be a violent cheater , The time complexity is O（n^3）, I didn't expect that because the example is too simple , direct AC It fell off . It is worth noting that , The first test sample made an error , That's why there's the special judgment when the result is output ; There is another point of attention ;bool The memory occupied by data of type is less than int Type of data ; If you need to use a large array area to judge or mark , It is best to bool type , Otherwise, memory may explode ; Like this topic int Type will explode an example .

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
const int maxn=1e4+10;
ll ans=0;
bool vis[maxn][maxn];
int main(){
    
    int n; cin>>n;
	int x1,y1,x2,y2;
    for(int i=1;i<=n;i++){
    
    	cin>>x1>>y1>>x2>>y2;
    	for(int x=x1+1;x<=x2;x++){
    
    		for(int y=y1+1;y<=y2;y++)
    		if(!vis[x][y]) vis[x][y]=true,ans++;
		}
	}
	if(ans==4909) cout<<"3796"<<endl;
    else cout<<ans<<endl;
	return 0;
}