DEV Community

Rishit Chaudhary
Rishit Chaudhary

Posted on • Updated on

Solving Codeforces Problem: 467A - George and Accommodation

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]
Enter fullscreen mode Exit fullscreen mode

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";
}

Enter fullscreen mode Exit fullscreen mode

Complexity

Complexity Type Answer
Time Complexity O(n)
Space Complexity O(1)
Difficulty (subjective value) Easy

Links and References

  1. Link to the problem: https://codeforces.com/problemset/problem/467/A
  2. Link to my submission: https://codeforces.com/contest/467/submission/120009560
  3. Link to the solution at my GitHub Repository: https://github.com/rishitc/Codeforces-Codes/blob/main/467A-George_and_Accommodation.cpp

Top comments (0)