Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Eliminare

Adăugată de :
sorynsoo
Sursă :
XOR2013
Autor :
-
Grupă :
Mică
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
500 ms
Limită memorie :
8192 kbytes

Considerăm şirul numerelor naturale nenule: 1, 2, 3, 4, ... Din acest şir se elimină N numere naturale distincte. De exemplu, dacă eliminăm 3 numere, fie acestea 2, 7, 9, atunci şirul este acum: 1, 3, 4, 5, 6, 8, 10, 11, 12, ...

 

Cerinţa

Trebuie să răspundeţi la Q întrebări de forma: Pe ce poziţie se află numărul x în şir după eliminarea celor N numere?

 

Date de intrare

Fişierul de intrare conţine pe prima linie numerele naturale N şi Q separate printr-un spaţiu, pe a doua linie se găsesc, separate prin spaţii şi în ordine crescătoare, cele N numere naturale care se elimină din şirul numerelor naturale. Pe următoarele Q linii se află câte un număr natural xi ce reprezintă o întrebare: „Pe ce poziţie se află numărul xi în şir după eliminarea celor N numere?”

 

Date de iesire

Fişierul de iesire va conţine exact Q linii. Pe linia i se află un singur număr natural pi reprezentând poziţia pe care se află xi. Dacă xi a fost eliminat din şir, atunci poziţia afişată va fi 0.

 

Restricţii şi precizări:

  • 1 <= N <= 100 000
  • 1 <= Q <= 100 000
  • numerele care se elimină din şirul numerelor naturale sunt numere naturale mai mici sau egale cu 2 000 000 000
  • 0 < xi <= 2 000 000 000, pentru orice i între 1 şi Q

 

Exemplu

 Date de intrare

 Date de iesire 

 Explicaţii

 3 5

 2 7 9

 3

 2

 70

 4

 10000

 2

 0

 67

 3

 9997

 Se elimină din şirul numerelor naturale valorile 2, 7, 9. Deci acum şirul este: 1, 3, 4, 5, 6, 8, 10, 11, 12, 13, ...

 Sunt 5 întrebări. Prima întrebare este: Pe ce poziţie se află numărul 3 în şir? Răspunsul este 2. A doua întrebare este: Pe ce poziţie se află numărul 2 în şir? Răspunsul este 0, pentru că 2 a fost eliminat din şir. Celelalte întrebări se referă la numerele 70, 4, 10000, iar răspunsurile sunt 67, 3, respectiv 9997.


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Nu există indicații de rezolvare



Comentarii

Adauga un comentariu: Click !