Codeforces Round 805 (Div. 3)


A. Round Down the Price
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
1
2
178
20
999999999
9000
987654321
Output
0
1
78
10
899999999
8000
887654321
----------------------------------------------------------------------------------------------------
B. Polycarp Writes a String from Memory
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
lollipops
stringology
abracadabra
codeforces
test
f
Output
2
4
3
4
1
1
----------------------------------------------------------------------------------------------------
C. Train and Queries
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
6 3
3 7 1 5 1 4
3 5
1 7
3 10
3 3
1 2 1
2 1
1 2
4 5
7 5
2 1 1 1 2 4 4
1 3
1 4
2 1
4 1
1 2
Output
YES
NO
NO
YES
YES
NO
NO
YES
YES
NO
YES
----------------------------------------------------------------------------------------------------
D. Not a Cheap String
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
abca
2
abca
6
codeforces
1
codeforces
10
codeforces
100
Output
aa
abc
cdc
codeforces
----------------------------------------------------------------------------------------------------
E. Split Into Two Sets
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
4
1 2
4 3
2 1
3 4
6
1 2
4 5
1 3
4 6
2 3
5 6
2
1 1
2 2
2
1 2
2 1
8
2 1
1 2
4 3
4 3
5 6
5 7
8 6
7 8
8
1 2
2 1
4 3
5 3
5 4
6 7
8 6
7 8
Output
YES
NO
NO
YES
YES
NO
----------------------------------------------------------------------------------------------------
F. Equate Multisets
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
4
2 4 5 24
1 4 6 11
3
1 4 17
4 5 31
5
4 7 10 13 14
2 14 14 26 42
5
2 2 4 4 4
28 46 62 71 98
6
1 2 10 16 64 80
20 43 60 74 85 99
Output
YES
NO
YES
YES
YES
----------------------------------------------------------------------------------------------------
G1. Passable Paths (easy version)
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
1 2
2 3
2 4
4 5
5
3
3 2 5
5
1 2 3 4 5
2
1 4
3
1 3 5
3
1 5 4
Output
YES
NO
YES
NO
YES
Input
5
1 2
3 2
2 4
5 2
4
2
3 1
3
3 4 5
3
2 3 5
1
1
Output
YES
NO
YES
YES
----------------------------------------------------------------------------------------------------
G2. Passable Paths (hard version)
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
1 2
2 3
2 4
4 5
5
3
3 2 5
5
1 2 3 4 5
2
1 4
3
1 3 5
3
1 5 4
Output
YES
NO
YES
NO
YES
Input
5
1 2
3 2
2 4
5 2
4
2
3 1
3
3 4 5
3
2 3 5
1
1
Output
YES
NO
YES
YES
----------------------------------------------------------------------------------------------------
