вторник, 1 января 2013 г.

Facebook interviews again

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);