Ավտոմատ

Գոյություն ունի երկարությամբ ամբողջ թվերի զանգված, որի յուրաքանչյուր տարր գտնվում է միջակայքում։ Հնարավոր է, որ որոշ թվեր զանգվածում հանդիպեն մի քանի անգամ։ Այնուամենայնիվ, պարզ է, որ միջակայքից առնվազն մեկ թիվ զանգվածում չի հանդիպում։ Ձեր խնդիրն է գտնել ցանկացած այդպիսի թիվ։

Սովորաբար սա հեշտ կլիներ, բայց դուք պետք է ներկայացնեք ձեր լուծումը որպես դետերմինացված վերջավոր ավտոմատ հետևյալ այբուբենի վրա․

:

Այբուբենի սիմվոլների իմաստը հետևյալն է․

• թվերը նշանակում են՝ հոսքում կարդացվեց համապատասխան թիվը (այսինքն՝ զանգվածի հերթական տարրը հավասար էր այդ թվին)։

• թիվը նշանակում է՝ դուք հասել եք զանգվածի ավարտին։

Գոյություն ունեցող զանգվածը իհարկե գաղտնի է․ ​ (յուրաքանչյուր )։ Ձեր ավտոմատին տրվելու է հետևյալ տողը՝

այն կրկնած նույն հերթականությամբ անգամ:
Այսինքն ավտոմատը կտեսնի ( անգամ)։

Ավտոմատը կարող է ցանկացած պահի հայտարարել, որ արդեն գիտի ճիշտ պատասխանը։ Այդ դեպքում աշխատանքը կանգնում է։ Եթե ավտոմատը մինչև -րդ կրկնության ավարտը (ներառյալ վերջին -ն) չի կանգնում, լուծումը չի ընդունվում։ Եթե կանգնում է, բայց հայտարարում է ոչ ճիշտ թիվ, նույնպես չի ընդունվում։

Ֆորմալ սահմանում

Պետք է նկարագրեք վերջավոր ավտոմատ, որն ունի վիճակ՝ համարակալված ։

Յուրաքանչյուր համարի վիճակի համար դուք պետք է տպեք ամբողջ թիվ՝

:

-ն նկարագրում է ավտոմատի վարքը, երբ այն գտնվում է վիճակ -ում և կարդում է սիմվոլ -ն։

Յուրաքանչյուր պետք է լինի հետևյալ միջակայքում․
․

Եթե բացասական է, ապա ավտոմատը կանգնում է և հայտարարում է թիվը որպտես պատասխան։

Եթե ոչ բացասական է, ապա ավտոմատը անցնում է վիճակին և շարունակում է աշխատանքը։

Ավտոմատի աշխատանքը սկսվում է վիճակից։

Լուծումը համարվում է ճիշտ, եթե ցանկացած հնարավոր գաղտնի զանգվածի համար ավտոմատը անցման ընթացքում կանգնում և վերադարձնում է թիվ, որը տվյալ զանգվածում չի հանդիպում։

Այսինքն, տեղի է ունենում հետևյալ գործնթացը․

// Դուք տպում եք ավտոմատ, որը սահմանվում է delta[][]-ով
// Ցանկացած a[1], a[2], ..., a[n] համար
a[n + 1] = 0;
int state = 0;
for (int round = 0 round < m; ++round) {
    for (int i = 1; i <= n + 1; ++i) {
        state = delta[state][a[i]];
        if (state < 0) {
             // -state պետք է բացակայի a-ից
             return 0;
        }
    }
}
// Ձեր ավտոմատը չի կանգնել՝ լուծումը սխալ է

Մուտքային տվյալները

Տրվում են երեք ամբողջ թվեր՝ . զանգվածի երկարությունը, ավտոմատին որպես մուտք տրվող անցնումների քանակը, ավտոմատի վիճակների մաքսիմալ քանակը։

Ելքային տվյալները

Առաջին տողում տպեք ՝ ավտոմատի վիճակների քանակը ()։

Հաջորդ տողերում տպեք ամբողջ թիվ՝ ։

Օրինակ

1 6 800

3
-1 2 1 
-1 1 1 
-2 2 2 

Ենթախնդիրները