| Fişierul intrare/ieşire: | fotbal3.in, fotbal3.out | Sursă | Algoritmiada 2018 Runda Finala |
| Autor | Eugenie Daniel Posdarascu | Adăugată de | |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Fotbal3
Fotbalistul profesionist Bossanip a decis sa joace niste fotbal recreational cu grupul sau de N prieteni, fiecare fiind dotat cu o anumita valoare distincta de valoarea oricarui alt prieten.
Mai intai, cei N prieteni se aseaza intr-o linie de la 1 la N, iar apoi Bossanip va alege echipa adversa, formata din orice interval compact de prieteni de ai sai. Cum stim cu totii, in fotbal, precum in viata, conteaza unitatea echipei, lipsa diviziunilor intre cei tari si cei slabi -- iar Bossanip vrea ca echipa adversa sa fie usoara de invins. Astfel, ajutati-l pe Bossanip sa numere cate echipe ar putea selecta unde valoarea membrului cu cea mai mica valoare divide valoarea membrului cu cea mai mare valoare.
Date de intrare
Fişierul de intrare fotbal3.in va contine, pe prima linie, numarul N
Pe cea de a doua linie vom gasi valoarea celor N prieteni, in ordinea in care s-au asezat, separate de spatiu alb.
Date de ieşire
În fişierul de ieşire fotbal3.out se va gasi numarul cerut.
Restricţii
- 1 ≤ N ≤ 100 000
- Valorile prietenilor sunt distincte.
- 1 ≤ valoarea unui prieten ≤ 300 000
- Pentru teste in valoare de 22 de puncte 1 ≤ N ≤ 1 000
Exemplu
| fotbal3.in | fotbal3.out |
|---|---|
| 6 1 2 3 4 5 6 | 14 |
| 10 25 4 89 200 100 10 8 31 178 40 | 36 |
Explicaţie
In primul exemplu, intervalele [1], [2], [3], [4], [5], [6], [1,2], [1,2,3], [1,2,3,4], [1,2,3,4,5], [1,2,3,4,5,6], [2,3,4], [2,3,4,5,6], [3,4,5,6] satisfac conditia.
