Today we are going to attempt to solve the Codeforces problem 467A - George and Accommodation. Alright! so let's begin.
Table Of Contents
The Question
Problem Statement
George has recently entered the BSUCP (Berland State University for Cool Programmers). George has a friend Alex who has also entered the university. Now they are moving into a dormitory.
George and Alex want to live in the same room. The dormitory has n rooms in total. At the moment the i-th room has pi people living in it and the room can accommodate qi people in total (pi ≤ qi). Your task is to count how many rooms has free place for both George and Alex.
Input
The first line contains a single integer n (1 ≤ n ≤ 100) — the number of rooms.
The i-th of the next n lines contains two integers pi and qi (0 ≤ pi ≤ qi ≤ 100) — the number of people who already live in the i-th room and the room's capacity.
Output
Print a single integer — the number of rooms where George and Alex can move in.
My Analysis with Sample Examples
Now, as per the question we need to check if a room, say ri
has enough space left for 2 people, i.e. George and Alex. So putting this in the form of a condition, we get (assuming we start counting the rooms from 1):
qi - pi ≥ 2, ∀ i ∈ [1, n]
Now let's try out our logic on the examples given in the problem:
Example-1
Input
3
1 1
2 2
3 3
Here, it's clearly visible that each and every room in the dormitory is full, so there is no space for our two friends 😢. Hence the answer will be 0.
Output
0
Example-2
Input
3
1 10
0 10
10 10
Here, we see that the first room with capacity 10 and number of occupants 1, and the second room with capacity 10 and number of occupants 0 have more than enough space for our 2 friends 😊. Great! So that gives us the answer of 2 rooms in the dormitory.
Output
2
Code and Complexity
Alright, so now we know mathematically what we need to check for each room in the dormitory and we have verified our logic over the examples as well. Let's now translate this logic into code. For this I'll be using modern C++ (C++11 and beyond), so that it's easier to get the big picture logic which is implemented in the code.
Another interesting reason to use modern C++ is that some of its features make the code more readable and similar looking to Python code (many people consider this a plus).
/**
* @file 467A-George_and_Accommodation.cpp
* @author Rishit Chaudhary (@rishitc)
* @version 1.0
* @date 2021-06-19
*
* @copyright Copyright (c) 2021
*
*/
#include <iostream>
int main()
{
int n;
int p, q;
int count{0};
const int Space_for_George_and_Alex{2};
std::cin >> n;
while (n--)
{
std::cin >> p >> q;
if (q - p >= Space_for_George_and_Alex)
{
++count;
}
}
std::cout << count << "\n";
}
Complexity
Complexity Type | Answer |
---|---|
Time Complexity | O(n) |
Space Complexity | O(1) |
Difficulty (subjective value) | Easy |
Links and References
- Link to the problem: https://codeforces.com/problemset/problem/467/A
- Link to my submission: https://codeforces.com/contest/467/submission/120009560
- Link to the solution at my GitHub Repository: https://github.com/rishitc/Codeforces-Codes/blob/main/467A-George_and_Accommodation.cpp
Discussion (0)