Selecting Guard (I)
Author: QuwsarOhi
Problem Setter: Maruf Ahmed RahadIntake 35, Department of CSE.
BUBT is a famous university. It’s CSE department is very advanced and they produce good programmers nowadays. They arrange a programming contest every semester. But this time the programmers don’t want to participate in the contest by risking their lives. That’s why Dipu sir set some students to guard the linear street (which is in front of BUBT) for the programmers’ safety. There are lots of stations in the street.
The students have to
guard all the stations and roads between stations. Students can be placed on
stations and they guard the roads and stations adjacent to it. But the students
are not well behaved. If a road is guarded by multiple students they start
fighting. So Dipu sir asked Zabir to write a program that finds the minimum number
of students to guard all the stations and roads. Since Zabir is not a good
programmer he needs your help.
In the above figure, if
you place a student in station 4, he will guard the two roads connected to
station 4 and station 3 and 5 as well.
Input Format
The first line of the
input is a single integer T (T<=100) which denotes the number of
test cases. Then the next T lines
contain a single integer N (N<=100) number of stations of the
road.
Output Format
For each test
case output in a single line, the minimum number of students needed to guard
all the stations and roads.
Samples
Input
Output
Language | Time | Memory |
GNU C 11 | 1s | 512MB |
GNU C++ 14 | 1s | 512MB |
GNU C++ 11 | 1s | 512MB |