Editing 2961 - Deminare (section)

= Exemplul: =
<code>deminare.in</code>
 1
 4 5
 8
 1 2
 1 5
 2 1
 3 2
 3 5
 4 3
 4 4
 4 5
<code>deminare.out</code>
 4

=== Explicație ===
<code>V = 1</code>, deci se rezolvă doar cerința 1. <code>L = 4</code>, <code>C = 5</code>, <code>M = 8</code>.

Minele sunt plasate la pozițiile <code>(1,2)</code>, <code>(1,5)</code>, <code>(2,1)</code>, <code>(3,2)</code>, <code>(3,5)</code>, <code>(4,3)</code>, <code>(4,4)</code> și <code>(4,5)</code>.

Pe linia <code>1</code> sunt amplasate <code>2</code> mine;

Pe linia <code>2</code> este amplasată <code>1</code> mină;

Pe linia <code>3</code> sunt amplasate <code>2</code> mine;

Pe linia <code>4</code> sunt amplasate <code>3</code> mine;

Deci, există o singură linie pe care sunt amplasate un număr maxim de mine și anume linia <code>4</code>.

<syntaxhighlight lang="python" line="1">
def citire_date():
    L, C, M = map(int, input().split())
    mine = []
    for _ in range(M):
        x, y = map(int, input().split())
        mine.append((x-1, y-1))  # Ajustare la indexare zero-based
    return L, C, M, mine

def linii_cu_cele_mai_multe_mine(L, mine):
    count_per_line = [0] * L
    for (x, y) in mine:
        count_per_line[x] += 1
    max_mine = max(count_per_line)
    linii_max = [i + 1 for i, count in enumerate(count_per_line) if count == max_mine]
    return linii_max

def mutari_minime(L, C, mine):
    mine_set = set(mine)
    mine_positions = [(x, y) for x, y in mine]
    
    def mine_in_rect(x1, y1, x2, y2):
        count = 0
        for x in range(x1, x2 + 1):
            for y in range(y1, y2 + 1):
                if (x, y) in mine_set:
                    count += 1
        return count
    
    min_moves = float('inf')
    for x1 in range(L):
        for y1 in range(C):
            for x2 in range(x1, L):
                for y2 in range(y1, C):
                    total_in_rect = mine_in_rect(x1, y1, x2, y2)
                    if total_in_rect == len(mine):
                        min_moves = 0
                        break
                    current_moves = len(mine) - total_in_rect
                    min_moves = min(min_moves, current_moves)
    
    return min_moves

def main():
    L, C, M, mine = citire_date()
    linii_max = linii_cu_cele_mai_multe_mine(L, mine)
    min_mutari = mutari_minime(L, C, mine)
    
    print("Linii cu cele mai multe mine:", " ".join(map(str, linii_max)))
    print("Număr minim de mine mutate:", min_mutari)

if __name__ == "__main__":
    main()
</syntaxhighlight>