InfoAs Atlas

<- Go back View preview

Problema Alinieri

Identification properties

🔒 The following are read-only properties. If you wish to change them, please create a new problem.

Name

Content ID

Hash Note: The hash is stored in the filesystem.

Content properties

Task

Se consideră modelul unui sistem solar format din `N` planete care se rotesc în jurul unei stele `S`, în sens trigonometric. Traiectoriile planetelor se consideră circulare și de raze diferite, iar vitezele de rotație ale planetelor în jurul stelei sunt numere naturale și sunt exprimate în grade pe zi (`°/zi`).

## Cerință

Cunoscând numărul de planete `N` și vitezele lor de rotație `Vi`, `1 ≤ i ≤ N` precum și două numere naturale `P` și `Z`, să se determine numărul `A` de alinieri a câte minimum `P` planete, pe o dreaptă ce trece prin centrul stelei `S`, după trecerea celor `Z` zile. Evoluția sistemului solar începe cu toate planetele așezate orizontal, în dreapta stelei `S`. 
 
De exemplu, pentru `n = 4, p = 3, z = 365, v = (20, 11, 8, 6)`, aliniearea a minimum `3` planete din cele `4` se va face la finalul zilelor `60, 90, 120, 180, 240, 270, 300, 360`. După `365` de zile vor exista `A = 8` alinieri. 
 
![Imagine](https://i.ibb.co/JBkd8DW/image.png)
## Date de intrare

Fișierul de intrare `alinieri.in` conține pe prima linie, în această ordine, numerele naturale `N`, `P` și `Z`, iar pe-a doua linie, `N` numere naturale `Vi`, `1 ≤ i ≤ N` cu semnificația de mai sus. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.
## Date de ieșire

Fișierul de ieșire `alinieri.out` va conține pe prima linie numărul `A`, cu semnificația de mai sus.
## Restricții și precizări

* `2 ≤ P ≤ N ≤ 105`
 * `1 ≤ Z ≤ 106`
 * `1 ≤ Vi ≤ 103`, `1 ≤ i ≤ N`
 * Pentru teste în valoare de aproximativ 33% din punctajul total `1 ≤ Z ≤ 1000`
 * Pentru teste în valoare de aproximativ 33% din punctajul total `1 ≤ N ≤ 100`
 * Pentru teste în valoare de aproximativ 33% din punctajul total `2 ≤ P ≤ 9`
 * Se vor lua în considerare doar alinierile de la sfârșitul fiecărei zile (ora `24:00`), când planetele și-au încheiat parcursul zilnic.

Examples

[{"input": "4 3 365 \n20 11 8 6", "output": "8", "explanation": "Pentru primul exemplu: <code>N = 4</code>, <code>P = 3</code>, <code>Z = 365</code> \u0219i <code>V = [20, 11, 8, 6]</code>. Prima aliniere a minimum <code>3</code> planete dintre cele <code>4</code> planete are loc dup\u0103 <code>60</code> de zile (conform figurii din exemplul de mai sus). Evolu\u021bia celor <code>4</code> planete este urm\u0103toarea:\n<ul>\n<li>planeta <code>1</code> efectueaz\u0103 <code>3</code> rota\u021bii complete \u0219i \u00eenc\u0103 <code>120°</code>;</li>\n<li>planeta <code>2</code> efectueaz\u0103 <code>1</code> rota\u021bie complet\u0103 \u0219i \u00eenc\u0103 <code>300°</code>;</li>\n<li>planeta <code>3</code> efectueaz\u0103 <code>1</code> rota\u021bie complet\u0103 \u0219i \u00eenc\u0103 <code>120°</code>;</li>\n<li>planeta <code>4</code> efectueaz\u0103 exact <code>1</code> rota\u021bie.</li>\n</ul>\nUrm\u0103toarele alinieri a minimum <code>3</code> din cele <code>4</code> planete au loc dup\u0103 <code>90, 120, 180, 240, 270, 300, 360</code> zile. Deci \u00een <code>365</code> zile vor avea loc <code>8</code> alinieri. \nRa\u021bionamentul este similar pentru celelalte dou\u0103 exemple."}, {"input": "7 3 2020 \n10 20 10 15 20 10 20 ", "output": "3928", "explanation": "Pentru primul exemplu: <code>N = 4</code>, <code>P = 3</code>, <code>Z = 365</code> \u0219i <code>V = [20, 11, 8, 6]</code>. Prima aliniere a minimum <code>3</code> planete dintre cele <code>4</code> planete are loc dup\u0103 <code>60</code> de zile (conform figurii din exemplul de mai sus). Evolu\u021bia celor <code>4</code> planete este urm\u0103toarea:\n<ul>\n<li>planeta <code>1</code> efectueaz\u0103 <code>3</code> rota\u021bii complete \u0219i \u00eenc\u0103 <code>120°</code>;</li>\n<li>planeta <code>2</code> efectueaz\u0103 <code>1</code> rota\u021bie complet\u0103 \u0219i \u00eenc\u0103 <code>300°</code>;</li>\n<li>planeta <code>3</code> efectueaz\u0103 <code>1</code> rota\u021bie complet\u0103 \u0219i \u00eenc\u0103 <code>120°</code>;</li>\n<li>planeta <code>4</code> efectueaz\u0103 exact <code>1</code> rota\u021bie.</li>\n</ul>\nUrm\u0103toarele alinieri a minimum <code>3</code> din cele <code>4</code> planete au loc dup\u0103 <code>90, 120, 180, 240, 270, 300, 360</code> zile. Deci \u00een <code>365</code> zile vor avea loc <code>8</code> alinieri. \nRa\u021bionamentul este similar pentru celelalte dou\u0103 exemple."}, {"input": "6 3 658903 \n17 24 12 150 200 12 ", "output": "58568", "explanation": "Pentru primul exemplu: <code>N = 4</code>, <code>P = 3</code>, <code>Z = 365</code> \u0219i <code>V = [20, 11, 8, 6]</code>. Prima aliniere a minimum <code>3</code> planete dintre cele <code>4</code> planete are loc dup\u0103 <code>60</code> de zile (conform figurii din exemplul de mai sus). Evolu\u021bia celor <code>4</code> planete este urm\u0103toarea:\n<ul>\n<li>planeta <code>1</code> efectueaz\u0103 <code>3</code> rota\u021bii complete \u0219i \u00eenc\u0103 <code>120°</code>;</li>\n<li>planeta <code>2</code> efectueaz\u0103 <code>1</code> rota\u021bie complet\u0103 \u0219i \u00eenc\u0103 <code>300°</code>;</li>\n<li>planeta <code>3</code> efectueaz\u0103 <code>1</code> rota\u021bie complet\u0103 \u0219i \u00eenc\u0103 <code>120°</code>;</li>\n<li>planeta <code>4</code> efectueaz\u0103 exact <code>1</code> rota\u021bie.</li>\n</ul>\nUrm\u0103toarele alinieri a minimum <code>3</code> din cele <code>4</code> planete au loc dup\u0103 <code>90, 120, 180, 240, 270, 300, 360</code> zile. Deci \u00een <code>365</code> zile vor avea loc <code>8</code> alinieri. \nRa\u021bionamentul este similar pentru celelalte dou\u0103 exemple."}]

Default code

Summary

Editorial

**Soluția 1.** Având în vedere că vitezele de rotație ale planetelor sunt numere naturale, atunci cu siguranță putem afirma că după un număr de `360` de zile toate planetele se vor găsi aliniate în punctul de unde au plecat, deoarece `360 * k` este multiplu de `360`, pentru `k` număr natural.

Să observăm în continuare că planetele se pot alinia pe o dreaptă care trece prin centrul stelei `S` atât de o parte cât și de cealaltă a stelei, ceea ce înseamnă că sunt suficiente `180` de zile pentru ca toate planetele să fie cu siguranță aliniate. În această situație o planetă se poate găsi ori în punctul inițial de plecare ori decalată cu `180o`, adică de cealaltă parte a stelei `S`.

Așadar în intervalul cuprins între `1` și `180` de zile un număr de `P` planete vor fi cu siguranță aliniate. Pentru a afla exact zilele în care loc aceste alinieri vom folosi un vector de contorizări și pentru fiecare zi, cuprinsă între `1` și `180`, vom determina poziția exactă a fiecărei planete, ținând cont că această poziție este dată de un unghi cuprins între `1` și `180`. Așadar această simulare determină, pentru fiecare zi, câte planete sunt aliniate și pe ce poziții. Se determină apoi câte astfel de alinieri se fac într-un interval de `360` zile și acest număr se înmulțeste cu numărul `Z / 360`. Se mai determină separat câte alinieri mai au loc în `Z % 360` și se adună la totalul anterior.

**Soluția 2.** La cele explicate în varianta anterioară putem face observația că analizand datele de intrare și anume că vitezele sunt numere naturale `≤ 103` și că sunt în total maxim `105` planete este clar că vor fi planete care au aceeași viteză și se comportă similar.

Deci putem de la început să grupăm planetele care au aceeași viteză `%180` utilizând încă un vector de frecvență. Această soluție obține 100 puncte.

Solution

Contributor ID

Author

File name	Description	Updated at	Size	Actions
hash.txt	Special file The hash of all the content of a problem. Autogenerated.	10 January 2025 21:26	64 B	View
manifest.json	Special file Metadata for the problem. Autogenerated.	10 January 2025 21:26	1 KB	View
0-alinieri.in	/ 100	10 January 2025 21:26	15 B	View
0-alinieri.ok	/ 100	10 January 2025 21:26	1 B	View
1-alinieri.in	/ 100	10 January 2025 21:26	50 B	View
1-alinieri.ok	/ 100	10 January 2025 21:26	1 B	View
2-alinieri.in	/ 100	10 January 2025 21:26	386 B	View
2-alinieri.ok	/ 100	10 January 2025 21:26	1 B	View
3-alinieri.in	/ 100	10 January 2025 21:26	41 B	View
3-alinieri.ok	/ 100	10 January 2025 21:26	2 B	View
4-alinieri.in	/ 100	10 January 2025 21:26	46 KB	View
4-alinieri.ok	/ 100	10 January 2025 21:26	1 B	View
5-alinieri.in	/ 100	10 January 2025 21:26	380 KB	View
5-alinieri.ok	/ 100	10 January 2025 21:26	5 B	View
6-alinieri.in	/ 100	10 January 2025 21:26	189 KB	View
6-alinieri.ok	/ 100	10 January 2025 21:26	4 B	View
7-alinieri.in	/ 100	10 January 2025 21:26	95 KB	View
7-alinieri.ok	/ 100	10 January 2025 21:26	5 B	View
8-alinieri.in	/ 100	10 January 2025 21:26	395 B	View
8-alinieri.ok	/ 100	10 January 2025 21:26	7 B	View
9-alinieri.in	/ 100	10 January 2025 21:26	325 B	View
9-alinieri.ok	/ 100	10 January 2025 21:26	5 B	View
In total: 22 files 714 KB

Problema Alinieri

Identification properties

Content properties

Technical properties

Delete all files