ტკბილეულის კოშკი



ძველი ლეგენდის თანახმად, დიდი ხნის წინ ანხ-მორპორკის მაცხოვრებლებმა მის იღბალს რაღაც დაუშავეს, მან კი წყევლით უპასუხა. მის იღბალმა თქვა, რომ ოდესღაც ქალაქში n ცალი განსხვავებული ზომის ტკბილეული ჩამოვარდებოდა, მაცხოვრებლებმა კი ამ ტკბილეულის ერთმანეთზე დალაგებით კოშკი უნდა ააშენონ. რა თქმა უნდა, დიდი ზომის ტკბილეული ქვემოთ უნდა იყოს, პატარა კი - ზემოთ.

დიდი დროის შემდეგ, ტკბილეულმა დაიწყო ცვენა ქალაქში და მოსახლეობა კოშკის შენებას შეუდგა. თუმცა შენებისას პრობლემები შეექმნათ. ყოველ დღე ზუსტად ერთი ვარდებოდა, მაგრამ მათი მიმდევრობა უცნაური იყო. მაცხოვრებლებს არ შეეძლოთ კოშკზე ახლის დადება ყოველ დღე, მათ უწევდათ ლოდინი სანამ უფრო დიდი ტკბილეული არ ჩამოვარდებოდა. რა თქმა უნდა, მის იღბალი რომ არ განერისხებინათ, ტკბილეულებს მაშინვე დებდნენ კოშკზე, როგორც კი შეეძლოთ.

დაწერეთ პროგრამა, რომელიც აღწერს ანხ-მორპორკის მაცხოვრებლების მოქმედებას.

შესატანი მონაცემები:  პირველი ხაზი შეიცავს ნატურალურ რიცხვს n (1 <= n <= 100 000) - ტკბილეულის რაოდენობას.

მეორე ხაზი შეიცავს n-ცალ ნატურალურ რიცხვს, i-ური რიცხვი შეესაბამება i-ურ დღეს ჩამოვარდნილი ტკბილეულის ზომას. ზომები ერთმანეთისგან განსხვავებული ნატურალური რიცხვებია 1-დან n-ის ჩათვლით.

გამოსატანი მონაცემები:  დაბეჭდეთ n ხაზი, i-ურ ხაზზე დაბეჭდეთ ამ დღეს კოშკზე დადებული ტკბილეულის ზომები. თუ რომელიმე დღეს ტკბილეული არ დაუდიათ, შესაბამისი ხაზი ცარიელი დატოვეთ.

მაგალითები
შესატანი მონაცემები
3
3 1 2
გამოსატანი მონაცემები
3
 
2 1
შესატანი მონაცემები
5
4 5 1 2 3
გამოსატანი მონაცემები
 
5 4
 
 
3 2 1

ამოხსნა ძალიან მარტივია, ფაქტობრივად პირობა როგორც გვეუბნება ისე უნდა მოვიქცეთ.

კოშკზე ტკბილეულის ზომების თანმიმდევრობა ცნობილია: n ცალი განსხვავებული ზომის ტკბილეული ჩამოვარდება, ხოლო აუცილებლად ჯერ დიდი ზომის უნდა დაიდოს კოშკზე, შემდეგ პატარა, არ შეგვიძლია დიდის მოგვიანებით ჩამატება. ასევე ყველა ჩამოვარდნილი უნდა იდოს კოშკზე. ამიტომ ტკბილეული ქვემოდან ზემოთ ზომის კლებადობით იქნება დალაგებული.

ავიღოთ მასივი სადაც შევინახავთ ყველა შემოსულ ზომას, ან შეგვიძლია ამის მაგივრად, გავაკეთოთ მასივი სადაც პასუხებს შევინახავთ სტრინგების სახით და ბოლოს დავბეჭდავთ ერთად. ასევე ავიღოთ მასივი მაგ.: fallen, სადაც შევინახავთ რა ზომებია ჩამოვარდნილი. ასევე ავიღოთ ერთი ცვლადი, სადაც შევინახავთ რა ზომას ვეძებთ მაგ.: lookingFor, თავიდან მისი მნიშვნელობა იქნება n, რადგანაც პირველი ეს ზომა უნდა დაიდოს.

ახლა გადავუყვეთ ზომებს, თუ პირველი შემხვედრი ზომა ემთხვევა lookingFor-ს, მაშინ პირდაპირ დავდოთ კოშკზე, lookingFor ერთით შევამციროთ და გავაგრძელოთ. თუ არ ემთხვევა, მაშინ მოვინიშნოთ fallen მასივში რომ ჩამოვარდა და დავბეჭდოთ ცარიელი ხაზი. ასე გავაგრძელოთ სანამ ჩამოვარდნილი ზომა lookingFor-ს არ დაემთხვევა. როდესაც ჩამოვარდება სასურველი ზომის ტკბილეული, დავდოთ კოშკზე, შემდეგ კი გადავუყვეთ fallen მასივს და დავდოთ რისი დადებაც შეგვიძლია, ანუ ამ დღის ხაზზე დაიბეჭდა ახლა ჩამოვარდნილი ზომა და კიდევ ისინი რისი დადებაც შეგვეძლო. გადაყოლისას როდესაც შეგვხვდება ისეთი ზომა, რომელიც ჯერ არ ჩამოვარდნილა, ის გახდება ახალი lookingFor.

ალგორითმის სირთული O(n) არის: ყველაზე კარგ ვარიანტში, თუ დალაგებული ვარდება ტკბილეული, n ციკლი შესრულდება, ყველაზე უარეს შემთხვევაში თუ პირიქით დალაგებული ცვივა, 2*n შესრულდება, შესაბამისად, ალგორითმის სირთულე O(n) არის.

#include<stdio.h>
#include<string.h>

int main(){

    int days = 0;
    scanf("%d", &days);

    char fallen[days+1];
    memset(fallen, 0, days+1);
    int next = 0;
    int lookingFor = days;

    int input [days+1];
    for (int i= 1 ; i <= days; i++){
        scanf("%d", &input[i]);
    }

    for (int i = 1 ; i <= days; i++){
        next = input[i];
        if(next == lookingFor){
                printf("%d ", next);
                lookingFor--;
                for(int j = lookingFor; j > 0; j--){
                    if (fallen[j] == 1)
                        printf("%d ", j);
                    else{
                        lookingFor = j;
                        break;
                    }
                }
                printf("n");
        }else{
            printf("n");
            fallen[next] = 1;
        }
    }

    return 0;
}