P3320【Small Challenge】Lost Beads
Time limit: 20000 MS Space limit: 2500 KB
Problem Description
Boss He has a box of beads.
n
n
n pieces, number
1
1
1 to
n
n
n. He accidentally knocked the box over and all the beads fell to the ground. He picked up the beads one by one, recording the number of the current bead each time he picked one up. After picking it up, I found that two beads were missing. Please quickly find out which two beads are missing.
Input format
The first line, an integer
n
n
n
The next line,
n
?
2
n-2
n? An integer separated by 2 spaces, indicating the number of the beads picked up by Boss He.
Output format
A row of two integers arranged from small to large, representing the numbers of the two missing beads.
Sample input 1
7 4 1 7 2 5
Sample output 1
3 6
Sample input 2
10 4 5 8 3 9 7 1 2
Sample output 2
6 10
hint
For 30% of the data, there are n<=1,000
For 100% of the data, there are n<=1,000,000
For those who like to use cin to read, adding ios::sync_with_stdio(false); at the beginning of the main function of the program can greatly improve the reading efficiency of the program.
Summary of the question
Find out from
1
1
1 to
n
n
Two missing numbers in n
Problem analysis
When I saw this title, the first thing that came to my mind was violence.
How violent?
First a loop, read in
n
?
2
n-2
n? 2 numbers, another cycle, check whether each bead has been picked up
#include<bits/stdc + + .h>
using namespace std;
int n,x;
bool flag[1000010];
int main(){<!-- -->
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n-2;i + + ){<!-- -->
cin>>x;
flag[x]=1;
}
for(int i=1;i<=n;i + + ) if(!flag[i]) cout<<i<<" ";
return 0;
}
Calculate the time complexity:
O
(
n
?
2
)
+
O
(
n
)
O(n-2) + O(n)
O(n?2) + O(n) is approximately equal to
O
(
2
n
)
O(2n)
O(2n), that is
O
(
2
,
000
,
000
)
O(2,000,000)
O(2,000,000), it will not explode.
Let’s count the space:
1
,
000
,
000
B
=
1
,
000
K
B
1,000,000B=1,000KB
1,000,000B=1,000KB, question limit
2500
K
B
2500KB
2500KB, (little T handed it in as soon as his head was hot), the result?
It turns out that processing other operations still takes up space, so we have to think of another way.
If the question is stuck in space and does not allow us to open an array, then we will consider…
Math question!
If we build a
s
u
m
sum
The sum variable records the sum of all beads. Every time one is picked up, its number is subtracted. The remainder is the sum of the numbers of the two missing beads.
Let the lost number be
a
,
b
a,b
a, b, that is
a
+
b
=
s
u
m
?
o
t
h
e
r
(
The sum of the numbers picked up
)
a + b=sum-other (sum of picked up numbers)
a + b=sum?other (the sum of the numbers picked up).
An equation, two unknowns, Pythagoras tells you: it is impossible to solve.
Then we need another equation to form a system of equations in two variables.
So,
Where does the rest of the equation come from?
Assume a variable
q
d
t
qdt
qdt, records the sum of squares. Similarly, every time one is picked up, the sum of squares of its number is subtracted.
Then we get:
a
2
a^2
a2
+
+
+
b
2
=
q
d
t
?
o
t
h
e
r
2
b^2=qdt-other^2
b2=qdt?other2.
Then we get a system of equations of two variables, which can be solved
a
,
b
a,b
a, b.
Example code
#include<bits/stdc + + .h>
using namespace std;
long long n,x,sum,qdt;
int main() {<!-- -->
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);//Quick reading
cin>>n;
sum=n*(n + 1)/2,qdt=n*(n + 1)*(2*n + 1)/6;
for(int i=1; i<=n-2; i + + ) {<!-- -->
cin>>x;
sum-=x;
qdt-=x*x;
}
for(int i=1; i<=sum; i + + )
if(i*i + (sum-i)*(sum-i)==qdt) {<!-- -->//Solving equations, enumeration
cout<<i<<" "<<sum-i;
return 0;
}
return 0;
}
No array, just a Maths Question!
The next step is to expand the extension section
…
Then, in order to check whether it was correct or not, I wrote a comparison.
That is, you can create samples yourself and test them yourself. When generating samples, you must keep the format consistent.
You need to use the rand() function here, which is included in the
Generating random time seeds requires the use of the time() function. Different times will generate different numbers, which are included in the
Shooting requires a correct solution code, a violent code, and a program to generate samples
Example
//ZhengJie.cpp
#include<bits/stdc + + .h>
#define int long long
using namespace std;
int n,x,sum,poq;
signed main() {<!-- -->
freopen("Data.in","r",stdin);
freopen("ZhengJie.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
sum=n*(n + 1)/2,poq=n*(n + 1)*(2*n + 1)/6;
for(int i=1; i<=n-2; i + + ) {<!-- -->
cin>>x;
sum-=x;
poq-=x*x;
}
for(int i=1; i<=sum; i + + ) if(i*i + (sum-i)*(sum-i)==poq) {<!-- -->
cout<<i<<" "<<sum-i;
return 0;
}
return 0;
}
//Baoli.cpp
#include<bits/stdc + + .h>
using namespace std;
int n,x;
bool flag[1000010];
int main(){<!-- -->
freopen("Data.in","r",stdin);
freopen("Baoli.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n-2;i + + ){<!-- -->
cin>>x;
flag[x]=1;
}
for(int i=1;i<=n;i + + ) if(!flag[i]) cout<<i<<" ";
return 0;
}
//MakeData.cpp
#include<bits/stdc + + .h>
using namespace std;
bool flag[1000010];
int main() {<!-- -->
freopen("Data.in","w",stdout);
srand(time(NULL));
int n=rand() 00000 + 1;
printf("%d\
",n);
for(int i=1; i<=n-2; i + + ) {<!-- -->
int x=rand()%n + 1;
while(1){<!-- -->
if(!flag[x]) break;
x=rand()%n + 1;
}
flag[x]=1;
printf("%d ",x);
}
return 0;
}
//Data.in (display 1 group)
74
12 40 31 8 69 26 51 2 45 57 20 60 17 29 14 64 22 7 47 35 70 62 65 1 10 63 41 37 52 3 55 30 11 28 23 5 15 58 49 43 34 36 59 50 6 74 32 54 4 27 66 18 25 53 44 46 38 73 13 61 9 56 39 68 42 48 67 72 71 21 19 24
After generating the sample, use freopen() to read the data, save it in a .out file, and finally write a .bat program .
What should be written in the program?
@echo off :loop MakeData.exe ZhengJie.exe Baoli.exe fc ZhengJie.out Baoli.out if not errorlevel 1 goto loop pause :end
Finally close it and double-click it to open it for comparison.
You can see that the output of your brute force program and the correct solution program are inconsistent, thus helping you debug the code.
This method is what we call counter-shooting.