France - IOI

Densité la plus proche

PROBLEMELorsquedes clients vous demandent des blocs de plastique d'une densité dontvous ne disposez pas, vous souhaitez pouvoir leur proposer un blocd'une densité proche.Ecrivez un programme qui lit la description de votre bloc, puisrépond aux questions de vos clients, en indiquant la densité deplastique la plus proche de celui demandé, pour lequel vous disposezd'au moins un bloc. S'il y a plusieurs densités aussi proches l'une quel'autre que celle demandée, donnez la plus petite (cela vous coûtemoins cher). LIMITES DE TEMPS ET DE MEMOIRE

• Temps : 2 s sur une machine à 1Ghz.
• Mémoire : 8000 Ko.

CONTRAINTES

• 1 <= N <= 100 000, où N est le nombre de blocs de plastique que vous avez en stock.
• 1 <= D <= 10⁸, où D est une densité en grammes par mètre cube.
• 1 <= Q <= 100 000 où Q est le nombre de questions posées par des clients.

ENTREELa première ligne de l'entrée contient un entier : le nombre N de blocs de plastique de votre stock.La deuxième ligne de l'entrée contient N entiers séparés par des espaces : les densités des blocs.La troisième ligne contient un entier Q : le nombre de questions posées par vos clients.Chacune des Q lignes suivantes contient un entier : la densité demandée par un client.SORTIEVous devez afficher Q lignes sur la sortie, contenantchacune la réponse à une question, sous la forme d'un entier : ladensité la plus proche de celle demandée par le client, pour laquellevous disposez d'un bloc dans votre stock. Les réponses doivent êtrefournies dans l'ordre dans lequel les questions sont placées dansl'entrée.Vous devez bien sûr répondre aux questions au fur et à mesure où lesclients les posent, donc afficher la réponse à une question avant delire la question suivante. EXEMPLE(S) D'ENTREE / SORTIEExemple 1 : en entrée ... </table> en sortie ... 8172411

7 41 32 11 17 24 8 16 4 9 20 28 11

_________________
00011100101001111000111110012.....