Rezumat problemă

Benzinarii1

#2537

În Piatra Neamț sunt N+2 locații numerotate de la 0 la N+1, de la stânga la dreapta. Distanța dintre două locații i si j este egală cu |i – j|. La început, în locațiile 0 și N+1, sunt construite benzinării, și în celelalte locații sunt case. Compania BuildNT a decis sa construiască N benzinării, una în fața fiecărei case.

Înainte să construiască o benzinărie, constructorii calculează valoarea S egală cu suma distanțelor de la fiecare casă la cea mai apropiată benzinărie, si adaugă această sumă la suma totală T. După, ei aleg o casă, la cea mai mare distanță de orice benzinărie, în fața căreia construiesc o nouă benzinărie. Casele sunt alese în așa fel încât, după construirea benzinăriilor, valoarea S recalculată sa fie minimă. Dacă sunt mai multe case ce respectă această regulă, se alege prima din stânga.
Desigur, după ce toate benzinăriile au fost construite, suma S va deveni 0 și suma totală T nu se va mai schimba.

Calculați T pentru o valoare dată N.

Olimpiada internațională pe Echipe, 2018

Consola Pracsiu Dan (dnprx) Adrian Panaete concurs

Clasa 10 Structuri de date liniare Coada

Rezolvă

Detalii

Problema	Benzinarii1	Operații I/O	tastatură/ecran
Limita timp	0.1 secunde	Limita memorie	Total: 64 MB / Stivă 8 MB
Id soluție	#42265781	Utilizator	Iosif Andrei Stefan (Iosif_Andrei_Stefan)
Fișier	benzinarii1.cpp	Dimensiune	1.19 KB
Data încărcării	26 Februarie 2023, 14:45	Scor/rezultat	100 puncte

Evaluare

Mesaj compilare

benzinarii1.cpp: In function 'int main()':
benzinarii1.cpp:16:48: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
 #define sub(n) 1LL * (n >> 1) * (1 + (n >> 1)) + (n & 1 ? ((n >> 1) + 1) : 0)

                                                ^
benzinarii1.cpp:36:18: note: in expansion of macro 'sub'
             k2 = sub(lg >> 1) << 1;

                  ^
benzinarii1.cpp:38:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
             k2 = sub((lg >> 1) - 1) + sub(lg >> 1);

                                ^
benzinarii1.cpp:16:23: note: in definition of macro 'sub'
 #define sub(n) 1LL * (n >> 1) * (1 + (n >> 1)) + (n & 1 ? ((n >> 1) + 1) : 0)

                       ^
benzinarii1.cpp:38:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
             k2 = sub((lg >> 1) - 1) + sub(lg >> 1);

                                ^
benzinarii1.cpp:16:39: note: in definition of macro 'sub'
 #define sub(n) 1LL * (n >> 1) * (1 + (n >> 1)) + (n & 1 ? ((n >> 1) + 1) : 0)

                                       ^
benzinarii1.cpp:38:32: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
             k2 = sub((lg >> 1) - 1) + sub(lg >> 1);

                                ^
benzinarii1.cpp:16:51: note: in definition of macro 'sub'
 #define sub(n) 1LL * (n >> 1) * (1 + (n >> 1)) + (n & 1 ? ((n >> 1) + 1) : 0)

                                                   ^
benzinarii1.cpp:38:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
             k2 = sub((lg >> 1) - 1) + sub(lg >> 1);

                                ^
benzinarii1.cpp:16:61: note: in definition of macro 'sub'
 #define sub(n) 1LL * (n >> 1) * (1 + (n >> 1)) + (n & 1 ? ((n >> 1) + 1) : 0)

                                                             ^

Rezultat evaluare

Cum funcționează evaluarea?