2 seconds
256 megabytes
standard input
standard output
Two players play a game.
Initially there are
n
n
integers
a
1
,
a
2
,
…
,
a
n
a1,a2,…,an
written on the board. Each turn a player selects one number and erases it from the board. This continues until there is only one number left on the board, i. e.
n
−
1
n−1
turns are made. The first player makes the first move, then players alternate turns.
The first player wants to minimize the last number that would be left on the board, while the second player wants to maximize it.
You want to know what number will be left on the board after
n
−
1
n−1
turns if both players make optimal moves.
The first line contains one integer
n
n
(
1
≤
n
≤
1000
1≤n≤1000
) — the number of numbers on the board.
The second line contains
n
n
integers
a
1
,
a
2
,
…
,
a
n
a1,a2,…,an
(
1
≤
a
i
≤
10
6
1≤ai≤106
).
Print one number that will be left on the board.
3 2 1 3
2
3 2 2 2
2
In the first sample, the first player erases
3
3
and the second erases
1
1
.
2
2
is left on the board.
In the second sam
ple,
2
2
is left on
the board regardless of the actions of the players.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
int a[1005];
cin>>n;
memset(a,0,sizeof(a));
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
if(n%2==0)
cout<<a[n/2-1]<<endl;
else
cout<<a[n/2]<<endl;
return 0;
}B. Minesweeper
1 second
256 megabytes
standard input
standard output
One day Alex decided to remember childhood when computers were not too powerful and lots of people played only default games. Alex enjoyed playing Minesweeper that time. He imagined that he saved world from bombs planted by terrorists, but he rarely won.
Alex has grown up since then, so he easily wins the most difficult levels. This quickly bored him, and he thought: what if the computer gave him invalid fields in the childhood and Alex could not win because of it?
He needs your help to check it.
A Minesweeper field is a rectangle
n
×
m
n×m
, where each cell is either empty, or contains a digit from
1
1
to
8
8
, or a bomb. The field is valid if for each cell:
-
if there is a digit
k
k
in the cell, then exactly
k
k
neighboring cells have bombs.
-
if the cell is empty, then all neighboring cells have no bombs.
Two cells are neighbors if they have a common side or a corner (i. e. a cell has at most
8
8
neighboring cells).
Input
The first line contains two integers
n
n
and
m
m
(
1
≤
n
,
m
≤
100
1≤n,m≤100
) — the sizes of the field.
The next
n
n
lines contain the description of the field. Each line contains
m
m
characters, each of them is ”
.
” (if this cell is empty), ”
*
” (if there is bomb in this cell), or a digit from
1
1
to
8
8
, inclusive.
Output
Print ”
YES
“, if the field is valid and ”
NO
” otherwise.
You can choose the case (lower or upper) for each letter arbitrarily.
Examples
input
Copy
3 3
111
1*1
111
output
Copy
YES
input
Copy
2 4
*.*.
1211
output
Copy
NO
Note
In the second example the answer is ”
NO
” because, if the positions of the bombs are preserved, the first line of the field should be
*2*1
.
You can read more about Minesweeper in
Wikipedia’s article
.
#include<bits/stdc++.h>
using namespace std;
int main()
{
char mp[200][200];
int n,m;
int mp1[200][200];
int mp2[200][200];
cin>>n>>m;
{
memset(mp1,0,sizeof(mp1));
memset(mp2,0,sizeof(mp2));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
if(mp[i][j]=='*')
{
mp1[i][j]=-9999;
mp2[i][j]=-9999;
mp1[i+1][j]+=1;
mp1[i+1][j+1]+=1;
mp1[i-1][j]+=1;
mp1[i-1][j-1]+=1;
mp1[i][j-1]+=1;
mp1[i][j+1]+=1;
mp1[i+1][j-1]+=1;
mp1[i-1][j+1]+=1;
}
else if(mp[i][j]=='.')
{
mp2[i][j]=0;
}
else
{
mp2[i][j]+=mp[i][j]-'0';
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp1[i][j]>=0&&mp2[i][j]>=0){
if(mp1[i][j]!=mp2[i][j])
{
cout<<"NO"<<endl;
return 0;
}
}
}
}
cout<<"YES"<<endl;
}
return 0;
}C. Finite or not?
1 second
256 megabytes
standard input
standard output
You are given several queries. Each query consists of three integers
p
p
,
q
q
and
b
b
. You need to answer whether the result of
p
/
q
p/q
in notation with base
b
b
is a finite fraction.
A fraction in notation with base
b
b
is finite if it contains finite number of numerals after the decimal point. It is also possible that a fraction has zero numerals after the decimal point.
Input
The first line contains a single integer
n
n
(
1
≤
n
≤
10
5
1≤n≤105
) — the number of queries.
Next
n
n
lines contain queries, one per line. Each line contains three integers
p
p
,
q
q
, and
b
b
(
0
≤
p
≤
10
18
0≤p≤1018
,
1
≤
q
≤
10
18
1≤q≤1018
,
2
≤
b
≤
10
18
2≤b≤1018
). All numbers are given in notation with base
10
10
.
Output
For each question, in a separate line, print
Finite
if the fraction is finite and
Infinite
otherwise.
Examples
input
Copy
2
6 12 10
4 3 10
output
Copy
Finite
Infinite
input
Copy
4
1 1 2
9 36 2
4 12 3
3 5 4
output
Copy
Finite
Finite
Finite
Infinite
Note
6
12
=
1
2
=
0
,
5
10
612=12=0,510
4
3
=
1
,
(
3
)
10
43=1,(3)10
9
36
=
1
4
=
0
,
01
2
936=14=0,012
4
12
=
1
3
=
0
,
1
3
412=13=0,13
#include<bits/stdc++.h>
#define _max 5000
using namespace std;
long long gcd(long long a,long long b){
return b==0?a:gcd(b,a%b);
}
int main(){
ios::sync_with_stdio(false);//这个会提高速度，不加会tl
int n;
cin>>n;
while(n--){
long long p,q,b;
cin>>p>>q>>b;
long long g=gcd(p,q);
q/=g;
b=gcd(q,b);
while(b!=1){
while(q%b==0)q/=b;
b=gcd(q,b);
}
if(q==1) cout<<"Finite"<<endl;
else cout<<"Infinite"<<endl;
}
}
D. XOR-pyramid
2 seconds
512 megabytes
standard input
standard output
For an array
b
b
of length
m
m
we define the function
f
f
as
f
(
b
)
=
{
b
[
1
]
if
m
=
1
f
(
b
[
1
]
⊕
b
[
2
]
,
b
[
2
]
⊕
b
[
3
]
,
…
,
b
[
m
−
1
]
⊕
b
[
m
]
)
otherwise,
f(b)={b[1]if m=1f(b[1]⊕b[2],b[2]⊕b[3],…,b[m−1]⊕b[m])otherwise,
where
⊕
⊕
is
bitwise exclusive OR
.
For example,
f
(
1
,
2
,
4
,
8
)
=
f
(
1
⊕
2
,
2
⊕
4
,
4
⊕
8
)
=
f
(
3
,
6
,
12
)
=
f
(
3
⊕
6
,
6
⊕
12
)
=
f
(
5
,
10
)
=
f
(
5
⊕
10
)
=
f
(
15
)
=
15
f(1,2,4,8)=f(1⊕2,2⊕4,4⊕8)=f(3,6,12)=f(3⊕6,6⊕12)=f(5,10)=f(5⊕10)=f(15)=15
You are given an array
a
a
and a few queries. Each query is represented as two integers
l
l
and
r
r
. The answer is the maximum value of
f
f
on all continuous subsegments of the array
a
l
,
a
l
+
1
,
…
,
a
r
al,al+1,…,ar
.
Input
The first line contains a single integer
n
n
(
1
≤
n
≤
5000
1≤n≤5000
) — the length of
a
a
.
The second line contains
n
n
integers
a
1
,
a
2
,
…
,
a
n
a1,a2,…,an
(
0
≤
a
i
≤
2
30
−
1
0≤ai≤230−1
) — the elements of the array.
The third line contains a single integer
q
q
(
1
≤
q
≤
100
000
1≤q≤100000
) — the number of queries.
Each of the next
q
q
lines contains a query represented as two integers
l
l
,
r
r
(
1
≤
l
≤
r
≤
n
1≤l≤r≤n
).
Output
Print
q
q
lines — the answers for the queries.
Examples
input
Copy
3
8 4 1
2
2 3
1 2
output
Copy
5
12
input
Copy
6
1 2 4 8 16 32
4
1 6
2 5
3 4
1 2
output
Copy
60
30
12
3
Note
In first sample in both queries the maximum value of the function is reached on the subsegment that is equal to the whole segment.
In second sample, optimal segment for first query are
[
3
,
6
]
[3,6]
, for second query —
[
2
,
5
]
[2,5]
, for third —
[
3
,
4
]
[3,4]
, for fourth —
[
1
,
2
]
[1,2]
.
#include<bits/stdc++.h>
#define _max 5000
using namespace std;
int a[_max],dp[_max][_max],ans[_max][_max];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
dp[i][i]=a[i];
ans[i][i]=a[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j+i<=n;j++){
int t=i+j;
dp[j][t]=dp[j+1][t]^dp[j][t-1];
ans[j][t]=max(dp[j][t],max(ans[j+1][t],ans[j][t-1]));
}
}
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
cout<<ans[l][r]<<endl;
}
return 0;
}3 seconds
256 megabytes
standard input
standard output
You work in a big office. It is a
9
floor building with an elevator that can accommodate up to
4
people. It is your responsibility to manage this elevator.
Today you are late, so there are queues on some floors already. For each person you know the floor where he currently is and the floor he wants to reach. Also, you know the order in which people came to the elevator.
According to the company’s rules, if an employee comes to the elevator earlier than another one, he has to enter the elevator earlier too (even if these employees stay on different floors). Note that the employees are allowed to leave the elevator in arbitrary order.
The elevator has two commands:
-
Go up or down one floor. The movement takes
1
second. -
Open the doors on the current floor. During this operation all the employees who have reached their destination get out of the elevator. Then all the employees on the floor get in the elevator in the order they are queued up while it doesn’t contradict the company’s rules and there is enough space in the elevator. Each employee spends
1
second to get inside and outside the elevator.
Initially the elevator is empty and is located on the floor
1
.
You are interested what is the minimum possible time you need to spend to deliver all the employees to their destination. It is not necessary to return the elevator to the floor
1
.
The first line contains an integer
n
(
1 ≤
n
≤ 2000
) — the number of employees.
The
i
-th of the next
n
lines contains two integers
a
i
and
b
i
(
1 ≤
a
i
,
b
i
≤ 9
,
a
i
≠
b
i
) — the floor on which an employee initially is, and the floor he wants to reach.
The employees are given in the order they came to the elevator.
Print a single integer — the minimal possible time in seconds.
2 3 5 5 3
10
2 5 3 3 5
12
正在解决