Նարնջագույն և Կապույտ ռոբոտների խնդիրը

Այս ծրագրավորման խնդիրն առաջարկվել է Google Code Jams օնլայն ծրագրավորման մրցությի սահմաններում որպես որակավորման փուլի խնդիր: Խնդիրը բավականին զվարճալի է և հետաքրքիր, ուստի առաջարկում եմ, որ դուք ևս լուծեք:

portal-2-co-op

Չար Արհեստական Ինտելեկտը փակել է կապույտ և նարնջագույն ռոբոտներին տեստավորման սենյակում: Ռոբոտներից ամեն մեկը կանգնած է միջանցքում, որտեղ ամեն մետրի վրա տեղադրված է մի մեծ կոճակ՝ յուրաքանչյուր միջանցքում ընդհամենը 100 կոճակ {1, 2, … 100}: Ժամանակի 0 պահին երկու ռոբոտն էլ կանգնած են իրենց միջանցքների 1 համարի կոճակի մոտ: 1 վայրկյանի ընթացքում ռոբոտներից ամեն մեկը կարող է անել հետևյալ քայլերից մեկը՝
1. տեղափոխվել մեկ մետր առաջ
2. տեղափոխվել մեկ մետր ետ
3. սեղմել այն կոճակը, որի մոտ տվյալ պահին գտնվում է
4. կանգնել և ոչինչ չանել
Որպեսզի ԱԻ-ն դուրս թողնի նրանց սենյակից, ռոբոտները պետք է սեղմեն կոճակները ըստ նախապես տրված խիստ հաջորդականության: Օրինակ՝ O 2 O 7 B 96 O 65 B 1 նշանակում է նարնջագույնը պետք է սեղմի 2 համարի կոճակը, ապա 7 համարի, հետո կապույտը պետք է սեղմի իր միջանցքի 96 համարի կոճակը և այլն…
Ռոբոտներից յուրաքանչյուրը ի սկզբանե գիտի հրամանների հաջորդականությունը և ցանկացած պահին կարող է կապ հաստատել ընկերոջ հետ և պարզել, թե նա «ուր է հասել»:

090410_portal_2_coop_pax_preview_tԽնդրի պահանջը հետևալն է: Ունենալով մուտքում նմանատիպ հրամանների հաջորդականություներ, յուրաքանչյուր հաջորդականության համար տպել, թե նվազագույնը քանի վայրկյանից կարող են ռոբոտները կատարել ԱԻ-ի տեստը: Մուտքային ֆայլի առաջին տողում տրվում է հրամանների հաջորդականությունների քանակը, հաջորդ տողերում հրամանների հաջորդականությունից առաջ տրվում է տվյալ հաջորդականություններում հրամանների թիվը:

Մուտքային ֆայլի օրինակ
3
4 B 17 O 1 B99 O 75
2 O 18 B 26
3 O 45 B 64 O 1

Ելքային ֆայլ
103
27
92

Advertisements

Թողնել մեկնաբանություն

Filed under Մտածենք..., Ծրագրավորում

Թողնել պատասխան

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Փոխել )

Twitter picture

You are commenting using your Twitter account. Log Out / Փոխել )

Facebook photo

You are commenting using your Facebook account. Log Out / Փոխել )

Google+ photo

You are commenting using your Google+ account. Log Out / Փոխել )

Connecting to %s