9/2/25, 10:27 AM Problem - 2004B - Codeforces
|
stdfloat | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP RAYAN
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Educational Codeforces Round 169
B. Game with Doors (Rated for Div. 2)
Finished
time limit per test: 2 seconds
memory limit per test: 256 megabytes Practice
There are 100 rooms arranged in a row and 99 doors between them; the i -th door connects rooms i and i + 1.
Each door can be either locked or unlocked. Initially, all doors are unlocked.
We say that room x is reachable from room y if all doors between them are unlocked. → Virtual participation
Virtual contest is a way to take part in past contest,
You know that: as close as possible to participation on time. It is
supported only ICPC mode for virtual contests. If
Alice is in some room from the segment [l, r]; you've seen these problems, a virtual contest is not
for you - solve these problems in the archive. If you
Bob is in some room from the segment [L, R] ; just want to solve some problem from a contest, a
virtual contest is not for you - solve this problem in
Alice and Bob are in different rooms. the archive. Never use someone else's code, read
the tutorials or communicate with other person
during a virtual contest.
However, you don't know the exact rooms they are in.
Start virtual contest
You don't want Alice and Bob to be able to reach each other, so you are going to lock some doors to prevent that.
What's the smallest number of doors you have to lock so that Alice and Bob cannot meet, regardless of their starting
positions inside the given segments?
→ Clone Contest to Mashup
Input
4
The first line contains a single integer t (1 ≤ t ≤ 10 ) — the number of test cases. → Submit?
The first line of each test case contains two integers l and r (1 ≤ l < r ≤ 100 ) — the bounds of the segment of
Language: GNU G++20 13.2 (64 bit, winlibs)
rooms where Alice is located.
Choose
The second line of each test case contains two integers L and R (1 ) — the bounds of the Choose File No file chosen
≤ L < R ≤ 100 file:
segment of rooms where Bob is located.
Submit
Output
For each test case, print a single integer — the smallest number of doors you have to lock so that Alice and Bob
cannot meet, regardless of their starting positions inside the given segments. → Last submissions
Submission Time Verdict
Example
Aug/15/2024
276567626 Accepted
input Copy 17:46
4
1 2 → Problem tags
3 4
2 5
brute force greedy *1000
2 5
No tag edit access
3 7
6 7
4 5
2 8 → Contest materials
output Copy
Announcement
1 Tutorial #1
3
2 Tutorial #2 (en)
3
Tutorial #3 (en)
Note
In the first test case, it is sufficient to lock the door between rooms 2 and 3 .
→ CF GetRating
In the second test case, the following doors have to be locked: (2, 3), (3, 4), (4, 5).
*1000
In the third test case, the following doors have to be locked: (5, 6) and (6, 7).
Show All Tags
Contest Standings
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/02/2025 [Link]UTC+5 (h1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by
[Link] 1/2
9/2/25, 10:27 AM Problem - 2004B - Codeforces
[Link] 2/2
