D. Sea Battle

D. Sea Battle-solution-1.pl

#!perl
use v5.20;
use strict;
use warnings;
use Class::Struct;
struct (
  Interval => [
    length => '$',
    cntShip => '$',
    endPos => '$'
  ]
);
while (<>) {
  my ($n, $aa, $bb, $k) = split ' ';
  my ($s, @str);
  chomp($s = <>);
  @str = split '', $s;
  my ($cnt, $i, @room);
  $cnt = 0;
  for $i ( 0..$#str ) {
    if (!$str[$i]) {
      ++$cnt;
    }
    else {
      if ($cnt) {
        push @room, Interval->new(
          length => $cnt,
          cntShip => int($cnt/$bb),
          endPos => $i-1
          );
      }
      $cnt = 0;
    }
  }
  if ($cnt) {
      push @room, Interval->new(
        length => $cnt,
        cntShip => int($cnt/$bb),
        endPos => $#str
        );
  }
  @room = sort { $a->length <=> $b->length } @room;

  #for $i ( 0..$#room ) {
  #  say '(', $room[$i]->length,
  #  ' ', $room[$i]->cntShip,
  #  ' ', $room[$i]->endPos, ')';
  #}

  my ($result, @postSum, $sum);
  $sum = 0;
  for ($i = $#room; $i >= 0; --$i) {
    $sum += $room[$i]->cntShip;
    $postSum[$i] = $sum;
  }
  my (@positions);
  for $i ( 0..$#room ) {
    if ($i != $#room && $postSum[$i+1] >= $aa) {
    #// remaining is enough.
      my $start = $room[$i]->endPos - ($room[$i]->length - 1);
      my $pos = $room[$i]->endPos;
      while ($pos >= $start + $bb - 1) {
      #say "start= ", $start, " pos= ", $pos;
        $pos -= ($bb - 1);
        push @positions, $pos+1;
        $pos--;
      }
    }
    elsif ($i != $#room && $postSum[$i+1] < $aa) {
    #// remaining is not enough, current interval is the last.
      my $remaining = $aa - $postSum[$i+1];
      my $cnt = $room[$i]->cntShip - $remaining + 1;
      my $pos = $room[$i]->endPos;
      while ($cnt--) {
        $pos -= ($bb - 1);
        push @positions, $pos+1;
        $pos--;
      }
      last;
    }
    else {
      my $cnt = $room[$i]->cntShip - $aa + 1;
      my $pos = $room[$i]->endPos;
      while ($cnt--) {
        $pos -= ($bb - 1);
        push @positions, $pos+1;
        $pos--;
      }
    }
  }
  say scalar @positions;
  say join ' ', @positions;
}

D. Sea Battle-solution-2.pl

#!perl
use strict;
use warnings;
use v5.18;
while (<>) {
	my ($n, $a, $b, $k) = split;
	my $s = <>; chomp $s;
	$s = '1' . $s . '1';
	my @str = split '', $s;
	my @positions;
	my $q;
	for ( my $i = 0; $i < $#str; $i = $q ) {
		my $j = $i;
		while ($j < $#str && 1 == $str[$j]) { $j++; }
		$q = $j;
		while ($q < $#str && 0 == $str[$q]) { $q++; }
		for (my $pos = $j - 1 + $b; $pos < $q; $pos += $b) {
			if ($a == 1) { push @positions, $pos }
			else { $a--; }
		}
	}
	say scalar @positions;
	say join ' ', @positions;
}