Oggi, 13 Settembre cade il Programmer’s Day, in coincidenza con il 256simo giorno dell’anno (256 = 2 elevato ad 8), giornata dedicata a tutti i programmatori del mondo.
La giornata va dedicata al retrocomputing, codare piccoli programmini, bere e divertirsi!
Visto che siamo in tema vi propongo un problema per veri programmatori, tratto dal Google Code Jam Practice Problem 2007:
Ti sei appena trasferito a Big City, e inizi il tuo lavoro presso il nuovo ufficio di Google, Google BC, la cosa che ti colpisce è l’incredibile skyline della città. Seduto su una collina, a 10 miglia di distanza, guardando i grossi palazzi rettangolari che compongono la città ti ritorna in mente la tua infanzia.
Da bambino costruivi città giocattolo con dei blocchi rettangolari. Ogni costruzione era fatta con più blocchi e ogni blocco poteva far parte di più edifici. Guardando lo skyline ti chiedi:"Qual’è il più grande blocco possibile che possa far parte dello skyline di Big City?"
Scrivi un programma che prenda come input la descrizione dello skyline e dia in input l’area del rettangolo più grande possibile. L’esecuzione del programma deve non deve superare i 4 minuti su un Pc con processore da 2Ghz e 512Mb di RAM, anche per l’input più grande che si possa dare.
Input:
La città è formata da edifici rettangolari tutti gli uni vicini agli altri. L’input consiste quindi in un intero N indicante il numero degli edifici seguito da N coppie di numeri w e h che indicano la laghezza e l’altezza dell’edificio in ordine da sinistra a destra. La dimensione degli edifici sarà inferiore a 100.000.000
Facile: 0 < N < 1.000
Difficile: 0 < N < 10.000.000
Output:
Un numero indicante l’area del più grande blocco possibile
input: 5, 5 7, 1 20, 3 5, 6 3, 2 10
output: 120
spiegazione: il blocco più grande è quello colorato di nero
non mi resta che augurarvi buon divertimento!
