Beautiful Badges
Practice
4 (4 votes)
Algorithms
Approved
Graphs
Hard
Matching
Open
Problem
87% Success 722 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Lucy has got the task to create badges for all students of the school. A badge is created by superimposing two squares. The bottom square should be of blue colour and top square should be of yellow colour. The squares must be rotated in such a way that the projection of the badge displays 8 distinguishable vertices.

Please help Lucy find out the maximum number of badges she can make with available n squares.

Input Format:
The first line of input file contains integer n. Each of the next n lines contain two space separated integers, ci and di. ci is the colour number and di is the length of side of square

Output Format:
Print the maximum number of badges that can be made.

Constraints:
1 <= n <= 100000
1 <= di <= 1000
1 <= ci <= 2

Notes:
- ci = 1 denotes blue color and vice-versa.

Problem Statement in native Language: http://hck.re/xepWPj

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
1 votes
Tags:
AlgorithmsApprovedDinic's algorithmGraphsHardOpen