მიკროპროცესორი

დროის ლიმიტი: 2 წმ

მეხსიერების ლიმიტი: 128 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: GEOI, 2010, შესარჩევი

   თქვენს განკარგულებაშია ახალი მიკროპროცესორი, რომელსაც შეუძლია  ერთგანზომილებიან მასივზე შეასრულოს შემდეგი ორი ოპერაცია:
    1.     მოახდინოს მასივის ელემენტთა მიმდევრობის ინვერსია L ინდექსიდან R ინდექსამდე, ანუ:
            L ინდექსის მქონე ელემენტი ადგილს უცვლის R ინდექსის მქონე ელემენტს;
            L+1 ინდექსის მქონე ელემენტი ადგილს უცვლის R-1 ინდექსის მქონე ელემენტს და ა.შ.
    ეს ოპერაცია პროგრამულად ასე შეიძლება იქნას აღწერილი:
 
    For i = 1 to [(R-L+1)/2] do Swap(A, L+i-1, R-i+1)
 
    სადაც [X]-ით აღინიშნება უდიდესი მთელი რიცხვი, რომელიც ნაკლებია ან ტოლია X–ზე (X ნამდვილი რიცხვია). რაც შეეხება Swap(A, i, j) პროცედურას, იგი შეიძლება ასე ჩაიწეროს:
 
    Procedure Swap(A, i, j) 
     Begin
       Tmp = A[i]
       A[i] = A[j]  
       A[j] = Tmp 
      End
 
    2.     დაბეჭდოს მასივის ელემენტების ჯამი L ინდექსიდან R ინდექსამდე. შესაბამის პროცედურას ექნება სახე:
 Procedure PrintSum(A, L, R)
     Begin
      Sum = 0
      For i = L to R do Sum = Sum + A[i]
      Print(Sum)
     End
 
    საწყის მომენტში A[1] = 1, A[2] = 2, …, A[N] = N.
    პროგრამა ამ მიკროპროცესორისათვის წარმოადგენს K რაოდენობის ოპერაციათა მიმდევრობას, სადაც თითოეული ოპერაცია არის ერთ-ერთი ზემოთ აღწერილი ორი ოპერაციიდან.
    დაწერეთ პროგრამა, რომელიც მიკროპროცესორის მოცემული პროგრამის და მოცემული N-ის (მასივში ელემენტთა რაოდენობა) მიხედვით იპოვის მიკროპროცესორის მიერ დაბეჭდილ რიცხვთა მიმდევრობას.
 
    შესატანი მონაცემები: შესატან მონაცემთა ფაილის პირველ სტრიქონში მოცემულია ორი მთელი N და K რიცხვი (1 ≤ N ≤ 10^9, 1 ≤ K ≤ 5000) _ მასივის ელემენტთა რაოდენობა და პროგრამაში ოპერაციათა რაოდენობა შესაბამისად. მომდევნო K რაოდენობის სტრიქონიდან თითოეულში აღწერილია პროგრამის თითო ოპერაცია. ოპერაციის აღწერაში პირველ ადგილზე მდგომი სიმბოლო გვიჩვენებს ოპერაციის ტიპს: ‘I’ (ASCII 73) – ინვერსია, ‘S’ (ASCII 83) – ბეჭდვა. ამ სიმბოლოს შემდეგ კი ჩაწერილია ორი მთელი L და R რიცხვი (1 ≤ L ≤ R ≤ N) (შესაბამისი ინდექსები).
    პროგრამა აუცილებლად შეიცავს ერთ S-ოპერაციას მაინც.
    შესატან მონაცემთა ფაილის ყველა სტრიქონში მონაცემები ერთმანეთისაგან თითო ჰარითა გამოყოფილი. 
 
    გამოსატანი მონაცემები: გამოსატან მონაცემთა ფაილი უნდა შეიცავდეს მიკროპროცესორის მიერ დაბეჭდილ რიცხვთა მიმდევრობას (თითო რიცხვს თითო სტრიქონში).
 
 



მაგალითები

შესატანი მონაცემები
10 2
I 1 5
S 3 7
                  დაკოპირება
გამოსატანი მონაცემები
19
                  დაკოპირება
შესატანი მონაცემები
15 4
S 2 11
I 10 15
I 1 10
S 5 10
                  დაკოპირება
გამოსატანი მონაცემები
65
21
                  დაკოპირება
შესატანი მონაცემები
1000 10
S 17 149
I 199 428
I 17 417
I 212 987
S 300 420
I 400 700
I 633 759
S 11 238
S 477 872
I 1 2
                  დაკოპირება
გამოსატანი მონაცემები
11039
101519
86244
194331
                  დაკოპირება