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

დროის ლიმიტი: 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 დაკოპირება