Uşaq bağçası
Hər il üç dost uşaq bağçası tərbiyəçisi, uşaqların qruplarını dəyişməyə icazə verirlər. Lakin bu dəyişiklik nəticəsində yenidən üç qrup yaranmalıdır. Bəzi uşaqlar artıq kifayət qədər böyüyüblər ki, bağçada qalsınlar. Amma bir il daha qalanlar üç tərbiyəçi arasında yenidən bölüşdürülürlər.
Tərbiyəçilər, uşaqlara yenidən bölüşdürmə prosesində söz haqqı verirlər. Dostluq gənc yaşlarda tez gəlib gedir, buna görə də hər bir uşaq X, digər hər bir uşaq Y-ni X-in yeni qrupunda görməkdən nə qədər məmnun olacağına görə qiymətləndirir. Yəni X-in bütün digər uşaqları əhatə edən bir üstünlük siyahısı var. Əgər siyahı eyni dəyərləri ehtiva edirsə, deməli X üçün bu uşaqlar eyni dərəcədə arzuolunandır.
Üç tərbiyəçi, yeni qrupların uşaqların sayına görə balanslaşdırılmamasına qarşı deyillər, çünki bu qruplara həmçinin uşaq bağçasında ilk dəfə həyatlarına başlayacaq yeni uşaqlar da daxil edilir. Onlar istəyirlər ki, yeni qruplarındakı bütün uşaqlar keçən ilin uşaqlarından fərqlənsin, çünki hətta tərbiyəçinin də bir il eyni uşaqlardan istirahət etməsi lazımdır. Uşaqların üç qrupa bölünməsi daha yaxşı hesab olunur, əgər heç bir uşaq üstünlük siyahısının top T-ində göstərilməyən uşaqlarla eyni qrupda deyilsə, burada T mümkün qədər kiçik olmalıdır. Qeyd edək ki, yeni qrupdakı uşaqlar köhnə qrupdakı eyni tərkibdə ola bilərlər, amma yalnız yeni tərbiyəçi ilə!
Giriş məlumatları
Birinci sətir uşaq bağçasında yenidən bölüşdürülməsi lazım olan uşaqların sayını n (n ≤ 200) ehtiva edir. Uşaqlar 1-dən n-ə qədər nömrələniblər.
Növbəti n sətir uşaqları təsvir edir. i-ci sətir cari tərbiyəçinin nömrəsini (tam ədəd 0, 1 və ya 2) və n − 1 tam ədəd {1, 2, 3, ..., i−1, i+1, ..., n} müəyyən bir qaydada ehtiva edir, bu da i-ci uşaq üçün üstünlük siyahısını azalan sırada təyin edir.
Çıxış məlumatları
Uşaqların üç yeni qrupa elə bölünməsi üçün mövcud olan ən kiçik qeyri-mənfi tam T ki,
heç bir uşaq köhnə qrupunda olan tərbiyəçi ilə eyni deyil
hər bir uşaq üçün yeni qrupdakı bütün dostlar üstünlük siyahısının top
T-indədir.