3014 - Ceva cu Liste

Se dau 2 liste, L1 și L2. L1 e formata din bile, iar L2 din numere. La început, în lista L1 sunt N bile. Lista L2 conține mereu M numere. O iterație presupune modificarea listei L1 în felul următor: se scot instantaneu și în același timp toate bilele din lista L1 aflate pe pozițiile date de elementele din lista L2. O bilă este pe poziția i dacă înaintea bilei, în lista L1, se află i-1 bile. Astfel, la fiecare iterație, L1 se modifică, dar L2 NU se modifică. Iterațiile se pot aplica până când în lista L1 nu se mai găsesc bile sau până când nu se mai pot scoate bile din L1.

De menționat ca unele bile își schimbă poziția pe parcursul efectuării iterațiilor. De exemplu, dacă L1=[$,$,$] și L2=[1], după prima iterație bila de pe poziția 1 va fi scoasă din lista L1 și bilele de pe pozițiile 2 și 3 vor ajunge pe pozițiile 1 și respectiv 2. În a doua iterație, prima bilă se va scoate (cea care inițial a fost bila de pe poziția 2) iar bila de pe poziția 2 (inițial 3) trece pe prima poziție. În ultima iterație bila de pe poziția 1 se scoate (inițial 3) și lista devine goală.

Cerință

Să se determine numărul de iterații care se pot efectua.

Date de intrare

Fișierul de intrare cevaculiste.in conține pe prima linie două numere naturale nenule N și M, reprezentând lungimea listei L1 și respectiv lungimea listei L2. Pe următoarea linie se află M numere în ordine crescătoare reprezentând elementele listei L2.

Date de ieșire

Fișierul de ieșire cevaculiste.out trebuie să conțină răspunsul pentru cerință, adică numărul de iterații care se pot efectua până când nu mai putem face nicio ștergere.

Restricții și precizări

• 1 ≤ N ≤ 10^18
• 1 ≤ M ≤ 10^5
• 1 ≤ L2[i] ≤ 10^18
• Elementele listei L2 sunt distincte.
• Pentru teste în valoare de 20 de puncte N ≤ 2*10^4 , M ≤ 10^4
• Pentru alte teste în valoare de 30 de puncte N ≤ 10^7 , M ≤10^5
• Problema va fi evaluată pe teste în valoare de 90 de puncte
• Se vor acorda 10 puncte pe exemple

Exemplu

cevaculiste.in

10 3
1 3 5

cevaculiste.out

5

Explicație

Notăm: $ ca bilă și ca bilă ce se va scoate în momentul

efectuării următoarei iterații.

Avem la început L1: [$,$,$,$,$,$,$,$,$,$]

Înainte de prima iterație: [ ,$, ,$, ,$,$,$,$,$]

După prima iterație și înainte de a 2-a: [ ,$, ,$, ,$,$]

După a 2-a iterație și înainte de a 3-a: [ ,$, ,$]

După a 3-a iterație și înainte de a 4-a: [ ,$]

După a 4-a iterație și înainte de a 5-a: [ ]

După a 5-a iterație: []

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python" line="1">

1. Framework: None
2. Technology stack: None

fin = open("cevaculiste.txt", "r") fout = open("cevaculiste.txt", "w")

n, m = map(int, fin.readline().split()) v = [0] * 100001 c = 0

for i in range(1, m + 1):

   v[i] = int(fin.readline())

while m:

   if v[m] <= n:
       c += (n - v[m]) // m + 1
       n -= ((n - v[m]) // m + 1) * m
   # Simply skip the ones I don't need
   while m and v[m] > n:
       m -= 1

fout.write(str(c)) fin.close() fout.close() </syntaxhighlight>