3399 - Semarun

Enunt

Pentru că este un bun sportiv și poate alerga constant cu x metri pe secundă, Gigel și-a propus să câștige competiția semarun. Această competiție începe la momentul 0 și constă în parcurgerea unui traseu de n metri, ce conține k semafoare. Pentru fiecare semafor se cunosc: - distanța la care este poziționat față de punctul de start, exprimată în metri – d; - numărul de secunde pentru care acesta indică culoarea roșu – r; - numărul de secunde pentru care acesta indică culoarea verde – v. La începutul competiției toate semafoarele indică culoarea roșu, apoi alternează între roșu și verde. La întâlnirea unui semafor, participanții trebuie să aștepte dacă acesta este roșu sau își schimbă culoarea din verde în roșu, și pot trece dacă acesta este verde sau își schimbă culoarea din roșu în verde. Este desemnat câștigător cel care parcurge distanța de la linia de start pană la final în cel mai scurt timp și fără a depăși s secunde de la începutul competiției. Este important de știut faptul că înainte de începerea competiției, fiecare participant trebuie să-și aleagă momentul (exprimat în secunde trecute de la începerea competiției) la care va începe parcurgerea traseului astfel încât să ajungă la final într-un interval de timp cat mai scurt.

Cerinţa

Deoarece Gigel știe că nu este important să ajungă primul la final, ci să parcurgă traseul într-un timp cat mai scurt, vă roagă să îl ajutați cu următoarea cerință: determinați momentele de timp pe care Gigel ar putea sa le aleagă pentru a începe parcurgerea traseului astfel încât să nu se oprească la niciun semafor și atunci când ajunge la final să nu fi trecut mai mult de s secunde de la începutul competiției (momentul 0).

Date de intrare

Pe prima linie a fișierului de intrare semarun.in se află numerele naturale n, x și s. Pe a doua linie se află numărul natural k, iar pe următoarele k linii se specifică pentru fiecare semafor numerele naturale d, r și v.

Date de ieșire

Pe prima linie a fișierului de ieșire semarun.out se va scrie numărul de soluții pentru cerința lui Gigel, iar pe a doua linie se vor scrie soluțiile separate printr-un spațiu, ordonate crescător.

Restricții și prec

Restricţii şi precizări

• 1 ≤ d ≤ n ≤ 100.000
• 1 ≤ x ≤ 12
• 1 ≤ s ≤ 864.000
• 1 ≤ k ≤ 70.000
• 1 ≤ r, v ≤ 5
• Se garantează că pentru datele din fișierul de intrare există cel puțin o soluție.
• Toate soluțiile din fișierul de ieșire trebuie să fie numere naturale pozitive.

Exemplul 1

semarun.in

 400 10 60 
 3
 30 2 2
 60 3 3
 90 4 4 

semarun.out

 3
 3 4 11

Explicație

Momentele de timp pe care Gigel le poate alege astfel încât să respecte cerința sunt: 3, 4 sau 11 secunde de la începerea competiției. Dacă Gigel începe parcurgerea traseului după 3 secunde de la start, acesta o să ajungă la cele trei semafoare în secundele 6, 9 și 12, fix când acestea își schimbă culoarea din roșu în verde. La final acesta o sa ajungă în secunda 43, încadrându-se în limita a 60 de secunde. Pentru orice altă alegere față de cele trei menționate mai sus, Gigel ar întâlni cel puțin un semafor care ar indica culoarea roșu sau și-ar schimba culoarea din verde în roșu la întâlnirea acestuia, ori nu s-ar încadra în limita de timp.

Rezolvare

<syntaxhighlight lang="python" line> def possible_start_times(n, x, s, k, semaphores):

   start_times = []
   for i in range(k):
       d, r, v = semaphores[i]
       if r >= s or v >= s:
           continue
       red_circles = (d // (x + r)) * r
       red_start = d // (x + r) * (x + r)
       green_circles = (d // (x + r)) * v
       green_start = (d // (x + r) + 1) * (x + r)
       if red_circles + green_circles <= s:
           start_times.append(red_start + 1)
           start_times.append(green_start + 1)
   return start_times

def read_input(file_name):

   with open(file_name, 'r') as file:
       n, x, s = map(int, file.readline().split())
       k = int(file.readline())
       semaphores = [list(map(int, file.readline().split())) for _ in range(k)]
   return n, x, s, k, semaphores

def write_output(file_name, result):

   with open(file_name, 'w') as file:
       file.write(str(len(result)) + '\n')
       file.write(' '.join(map(str, result)))

def main():

   n, x, s, k, semaphores = read_input("semarun.in")
   result = possible_start_times(n, x, s, k, semaphores)
   write_output("semarun.out", result)

if __name__ == "__main__":

   main()

</syntaxhighlight>