Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2178
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2178
Blue Lagoon
By Thalyson Nepomuceno, UECE 
Brazil
Timelimit: 1
The Blue Lagoon is a round pond where several birds live quietly (or not so much). Bino, one facetious boy, wants to capture all the birds that live in the Blue Lagoon. There are P places in the pond where some bird can stay, as illustrated in the figure below for P = 8.
Each bird can perform a number of flights, after it, the bird gets too tired to fly again. Bino will start at position 0, and then walk always in a clockwise direction, until capture all the birds.
Each bird has an ordered list of places where it prefers to flee if Bino get to where it is. For example, for the first test case, there is only one bird which begins at site 1, when Bino comes, the bird escapes to site 2, when Bino comes, the bird escapes to site 3, and when Bino reaches 3, the bird is tired and the bird is captured.
Your task is to find out what the minimum amount of laps in the pond that Bino must take to capture all the birds. In a complete turn, Bino visits all locations, and returns to position 0 (revisiting the position 0).
It is guaranteed that no bird starts at position 0, and also that no bird try to escape to the same place where it is.
Input
The first line contains two integers A (1 < A ≤ 103) and P (1 < P ≤ 109), respectively representing the number of birds and the number of places. Then follow A lines. Each line will start with a integer Ni (1 ≤ Ni ≤ 103) representing the amount of places that the bird will try to escape, then follow Ni integers, representing the list of places where the bird will escape.
Output
Print a single line containing the minimum amount of laps in the pond that Bino must take to capture all the birds.
| Input Samples | Output Samples |
|
1 8 |
1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
using namespace std;
int voltas, a, p, n;
int main() {
scanf("%d %d", &a, &p);
while (a--) {
int atual = 0, davez = 0;
scanf("%d", &n);
while (n--) {
int agora;
scanf("%d", &agora);
if (agora < atual) davez++;
atual = agora;
}
if (atual != 0) davez++;
voltas = max(davez, voltas);
}
printf("%d\n", voltas);
return 0;
}
Input
3 1 2 3
Output