N friends are playing a game. Each of them has a list of numbers in front of himself. Each of N friends chooses a number from his list and reports it to the game administrator. Then the game administrator sorts the reported numbers and shouts the K-th largest number.
You want to know the count all possible numbers that the game administrator can shout.
Input Format:
First line of the input contain an integer T, the number of testcases. Then follow T testcases. For each test case the input is of the following format. In the first line there are two numbers N and K. In each of next N lines there is an integer a_i followed by a_i integers, ith line describes the list for ith person. All the numbers in all the lists are unique.
My code solves it problem:
#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;
open(my $f, "test") or die "$!";
my $nums = [];
my (undef, $k) = split(/\s/, <$f>);
while (my $line = <$f>) {
my ($s, @arr) = split(/\s/, $line);
@arr = sort {$a <=> $b} @arr;
push(@$nums, \@arr);
}
my $all = 0;
for (my $i=0; $i<@$nums; $i++) {
for (my $j=0; $j<@{$nums->[$i]}; $j++) {
my $number = $nums->[$i]->[$j];
my $s = 0;
my $addit = 0;
my @arr = ();
L:
for (my $l=0; $l<@$nums; $l++) {
next if $l == $i;
if ($nums->[$l]->[-1] < $number) {
$s++;
} elsif($nums->[$l]->[0] > $number) {
# we cannot encrease
} else {
$addit++;
}
}
if ( $s == $k - 1) {
$all++;
} elsif (($s < $k - 1) && ($s + $addit) >= $k - 1) {
$all++;
}
}
}
print "Answer: " . ( $all ) . "\n";
close($f);
