Fişierul intrare/ieşire:squirrel.in, squirrel.outSursăRMI 2018
AutorCristian FrancuAdăugată delaurageorgescuLaura Georgescu laurageorgescu
Timp execuţie pe test5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Squirrel

Te afli în colţul (1,1) (stânga-sus) al unei reţele de N * M puncte. O veveriţă sare din punct în punct. Fiind o veveriţă pasionată de informatică, ea sare în aşa fel încât formează F fractali de... copaci bineînţeles! Cei F fractali arată ca cei din imagini:

Imaginile arată fractalii de dimensiunile 1, 2, 4 şi 8.

Veveriţa urmează următoarele reguli:
• Veveriţa începe dintr-un punct dat
• Apoi sare la nord P puncte, unde P este o putere dată de doi
• Apoi sare pe două diagonale de lungime P/2
• Apoi formează patru fractali de dimensiune P/2
• Continuă până când formează fractali de dimensiune 1

Veveriţa continuă să sară până când termină un fractal, apoi începe cu următorul fractal. În câte puncte poţi vedea veveriţa?

Date de intrare

Fişierul de intrare squirrel.in conţine pe prima linie 3 numere naturale N, M şi F. Următoarele F linii descriu cei F fractali. Fiecare linie conţine 3 întregi: coordonatele punctului de început pentru fractalul curent, urmate de dimensiunea fractalului.

Date de ieşire

În fişierul de ieşire squirrel.out se va afişa numărul de puncte în care se poate vedea veveriţa.

Clarificări

  • Poţi vedea veveriţa dacă nu există un alt punct (nu neaparat prin care a sarit veverita) între tine şi veveriţă.
  • Veveriţa se opreşte din făcut fractalul curent când termină toate săriturile, apoi începe următorul fractal.
  • Veveriţa nu va sari niciodată în poziţia ta (1, 1).
  • Veveriţa nu va ieşi niciodată din reţea.
  • Dacă veveriţa sare de mai multe ori în acelaşi punct vizibil, atunci punctul va fi numărat de mai multe ori în rezultat.

Restricţii

  • 2 ≤ N, M ≤ 50 000
  • 1 ≤ F ≤ 1 000
  • 1 ≤ dimensiunea fractalului ≤ 1 024 şi este o putere de doi.
  • Numărul total de sărituri este cel mult 300 milioane.
  • Pentru 15p, numărul total de sărituri este cel mult 40 milioane.
  • Pentru încă 10p, numărul total de sărituri este cel mult 65 milioane.
  • Pentru încă 25p, numărul total de sărituri este cel mult 125 milioane.
  • Limita de memorie este micsorata fata de cea din concurs!

Exemplu

squirrel.insquirrel.outExplicaţie
14 20 3
11 10 4
7 6 2
8 7 2
35

- Reţeaua are 14 linii şi 20 coloane.
- Veveriţa face 3 fractali: negru, verde şi roşu.
- Triunghiurile marchează punctele de început ale fractalilor.
- Cercurile marchează punctele care sunt vizibile din (1, 1).
- Cercurile îngroşate marchează punctele în care veveriţa sare de mai multe ori.
- Numărul total de puncte vizibile în care sare veveriţa este 35.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?