Əməksevər tələbə
Billi çalışqan bir tələbədir. O, kompüterləri çox sevir və onlar haqqında mümkün qədər çox şey öyrənmək istəyir. Hazırda qraf nəzəriyyəsini öyrənir və şəkildə göstərilən qrafı quracaq bir proqram yazmalıdır.
Qrafın zirvələri ardıcıl olaraq tam ədədlərlə 0-dan N-1-ə (N ≤ 10000) qədər nömrələnmişdir. İki növ kənar mövcuddur: şəkildə B hərfi ilə göstərilən geri kənarlar (məsələn, 4 zirvəsindən 2 zirvəsinə və ya 3 zirvəsindən 1 zirvəsinə) və F hərfi ilə göstərilən irəli kənarlar (məsələn, 1-dən 2-yə və ya 0-dan 3-ə). Billi'nin proqramı 0, 1, 2, 3 zirvələrini ehtiva edən qraf üzərində işləməyə başlayır. Daha sonra o, qrafı mətn faylındakı əmrlər ardıcıllığına uyğun olaraq qurmalıdır. Hər bir əmr aşağıdakı formata malikdir:
index0 string_of_characters index1
burada index0 və index1 zirvələrin nömrələridir, string_of_characters isə sağdan sola yerinə yetirilən əməliyyatlar ardıcıllığıdır. Əməliyyat bir neçə simvoldan biri ilə təsvir olunur:
burada v qrafın zirvələrinin massividir. İlk əməliyyatın arqumenti v[index1] zirvəsidir. f və b əməliyyatlarının nəticəsi digər bütün əməliyyatlar üçün arqumenti təmsil edən bir zirvədir. < və = əməliyyatları ən solda göstərilmişdir. Məsələn, əmr üçün əməliyyatlar belədir:
index0 = 4, index1 = 0
x = f(v[0]) // 3 zirvəsinə irəli, x = 3
y = f(x) // irəli yeni zirvə yaradır (4), y = 4
k(y) // açarı çap edir (4)
V[4] = y // (4) zirvəsini v massivinə yerləşdirir
Bir zirvə yalnız < əmri ilə v massivinə yerləşdirilir. Başlanğıcda massiv 0, 1, 2, 3 açarları olan zirvələri ehtiva edir, v[0]=0, v[1]=1, v[2]=2 və v[3]=3. Proqramın girişi mətn faylından olur. Fayl əmrlər ardıcıllığını ehtiva edir. Hər bir çap standart çıxışa sətirin əvvəlindən edilməlidir. Arada boş sətirlər yoxdur. Girişdə boşluqlar sərbəst şəkildə ola bilər. Giriş məlumatları faylın sonu ilə tamamlanır.
Aşağıdakı cədvəldə giriş/çıxış nümunəsi verilmişdir.
