Acrobats


Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 250M

Author:
Problem type
Allowed languages
C, C++, Java, Python

Les équipes d'acrobates font partie de la culture marocaine, elles jouaient dans les marchés traditionnels pour distraire les gens. Une des scènes les plus incroyables est quand ils se mettent debout les uns au dessus des autres pour former une sorte de pyramide.

Une pyramide de hauteur \(L\) est formée de la manière suivante : Une personne au sommet se tient debout sur les épaules d'une autre personne, qui elle tient debout sur les épaules de deux autres personnes, puis 3 et ainsi de suite.

une Pyramide de hauteur 4 :

enter image description here

On souhaite savoir quel est le nombre d'acrobates qu'il faut pour former une pyramide de hauteur \(L\).

Format d'entrée

La première ligne du fichier d'entrée contient un entier \(T\) : le nombre de cas de tests. Chaque cas de test est donné dans une ligne avec un seul entier \(L\) décrit précédemment(\( 1 \leq L \leq 10^{18}\)).

Format de sortie

Pour chaque cas de test afficher une seule ligne avec un seul entier : le nombre de personnes dans la pyramide de hauteur \(L\).

Ce nombre peut être assez grand, affichez le modulo \(10^9+7\).

Scoring

  1. \(L \leq 10\) (10 points).
  2. \(L \leq 1000\) (30 points).
  3. Pas de contrainte additionnelle (60 points).

Exemple d'entrée

2
6
3

Exemple de sortie

16
4

Comments


  • 1
    Nasroallah  commented on May 27, 2021, 9:36 p.m.

    https://ideone.com/hc3ght that's my solution


    • 0
      AkramElOmrani  commented on May 28, 2021, 10:06 a.m. edited

      this is definitly a good solution but lets not forget that in k(k+1)/2 property it exeeds int datatype so in some really serious testcases it would give TLE if numbers are big enough . Even if long int prevent you from overflow but it may give TLE


  • 0
    Nasroallah  commented on May 17, 2021, 10:23 p.m.

    AkramElOmrani I mean gauss formula: sum from 1 to n = (n*(n+1))/2


    • 0
      yn  commented on May 22, 2021, 4:40 p.m.

      but you have error because if we use you formula : n = 6 ==> (6*(6+1))/2 = 21

      I thik the correct fomula is : ((n(n-1))/2) + 1 : n = 6 ==> (6(6-1))/2 + 1 = 16

      we do a small transform in your formula : (((n*(n+1))/2)-n)+1 .


      • 0
        youssefboumhaout  commented on May 25, 2021, 6:55 p.m.

        they are other formula is : (n*(n-1)/2)+1 , but I think maybe if we use the formula we will get WA in the last case.


    • 0
      AkramElOmrani  commented on May 21, 2021, 7:03 p.m.

      Ok I will try.


  • 0
    AkramElOmrani  commented on March 26, 2021, 1:25 p.m.

    what do you mean by the sum formula?


  • 0
    Nasroallah  commented on Jan. 14, 2021, 9:28 p.m.

    AkramElOmrani Remembre the sum formula & read about modular inverse from BNL link


  • 0
    AkramElOmrani  commented on Jan. 14, 2021, 9:06 p.m.

    Yeah but What Is The Implimentation fro that here . I Made a counter and it increment every time the output is correct in the sample test But I dont know where I messed up


  • 0
    NawfalMazzal  commented on Aug. 23, 2020, 3:45 p.m.

    Why I always have WA on the last test case.