Fişierul intrare/ieşire:manhattan.in, manhattan.outSursăLot 2017 Baraj 1
AutorZoltan SzaboAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.3 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Manhattan

În primul cadran al sistemului cartezian se defineşte o zonă notată cu Z(x,y,u,v), ca o mulţime de puncte laticeale ce aparţin unui dreptunghi definit prin două puncte diagonal opuse (x,y) şi (u,v) cu x ≤ u şi y ≤ v. În caz particular o zonă poate să conţină punctele de pe un segment când x = u sau y = v. De asemenea o zonă poate fi formată dintr-un singur punct când x = u şi y = v.
Un traseu dintre două puncte laticeale se defineşte ca un număr minim de segmente de lungime 1 orizontale sau verticale, ce unesc cele două puncte.

Cunoscând două zone Z1 şi Z2 ce nu se intersectează în nici un punct, să se calculeze numărul traseelor distincte modulo 666013 care pornesc din zona Z1 şi se termină în zona Z2.

Pentru zonele Z1 şi Z2 avem 7 trasee distincte.

Date de intrare

Fişierul de intrare manhattan.in conţine pe prima linie opt numere naturale a,b,c,d,e,f,g,h cu semnificaţiile de mai sus.

Date de ieşire

Fişierul manhattan.out va conţine pe prima linie numărul traseelor distincte modulo 666013.

Restricţii

  • Coordonatele zonelor sunt numere naturale mai mici sau egale cu 100 000.
  • Pentru teste în valoare de 10 puncte coordonatele zonelor sunt mai mici sau egale cu 30.
  • Pentru teste în valoare de 30 puncte coordonatele zonelor sunt mai mici sau egale cu 300.
  • Pentru teste în valoare de 50 puncte coordonatele zonelor sunt mai mici sau egale cu 1000.
  • Pentru teste în valoare de 50 de puncte proiecţiile pe axele Ox şi Oy ale zonelor sunt disjuncte.

Exemplu

manhattan.inmanhattan.outExplicaţie
1 1 1 2 2 2 3 2
7
Studiaţi exemplul de mai sus
1 1 2 2 2 3 3 4
53
Numărul traseelor distincte este 53
8 4 13 7 2 3 6 8
44702
Numărul traseelor distincte modulo 666013 este 44702
80 40 130 70 20 30 60 80
145267
Numărul traseelor distincte modulo 666013 este 145267.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?