Gianni ha N palline, disposte in fila, numerate da 1 a N. Queste palline sono speciali,
perchè sono colorate o di nero o di bianco. In particolare la pallina i sarà bianca se
A[i] = 0 e sarà nera se A[i] = 1. Gianni ha in mente un numero K. Questo numero K è
particolare, perchè divide N (cioè la divisione N / K ha resto 0). Gianni ha a
disposizione tantissima vernice nera e bianca, ma è molto pigro. Si definisca come
distanza tra due palline i,j il valore assoluto della differenza della posizione della
pallina i e della pallina j. Si vuole che se due palline hanno distanza K, allora siano
dello stesso colore. Qual è il numero minimo di palline che Gianni deve colorare per
soddisfare suddetta condizione?
Input (input.txt)
La prima riga dell’input consiste in due numeri, N e K, separati da uno spazio. La
seconda riga dell’input consiste in una sequenza di N numeri, cioè i valori di A[0],
A[1], …, A[N].
Output (output.txt)
Il file di output dovrà contenere esattamente un numero, il numero minimo di palline
da colorare.
input.txt output.txt
10 2 3
1 0 1 1 0 1 1 0 1 1
SOLUZIONE
Partendo da un punto (0) si salta k palline e si contano quante sono nere e quante sono bianche. Il valore minimo fra bianche e nere è il numero minimo di palline da colorare di quella serie. Sommando i minimi di tutte le serie si ottiene il minor numero di palline da colorare:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <cstdlib> #include <iostream> #include <fstream> using namespace std; int n,k; int main() { ifstream in("input.txt"); ofstream out("output.txt"); in>>n>>k; int a[n]; for (int i=0;i<n;i++) in>>a[i]; int somma=0; for (int i=0;i<k;i++){ int bi=0,ne=0; for (int j=i;j<n;j+=k){ if( a[j] ==1) ne++; else bi++;} somma+=min(ne,bi);} out<<somma; return 0; } |
