Բլոկներով խաղ
Համլետը խաղում է խաղ չափանի վանդակավոր դաշտի վրա։ Խաղը կոչվում է «Block Puzzleո»։ Նա արդեն բավականին երկար ժամանակ է, ինչ խաղում է այս խաղը և դաշտի որոշ վանդակներ արդեն ծածկված են ինչ-որ բլոկներով։ Համլետը այս քայլին պետք է ծածկի վանդակավոր դաշտի ինչ-որ վանդակներ և դրա համար նա պետք է օգտագործի հետևալ բլոկներից մեկը՝ թե որը, նրան տրված է։ (Նկատեք, որ ներկայումս ծածկված վանդակները, կարող են ծածկված լինեն նաև այլ տեսակի բլոկներ օգտագործելով)
Համլետը կարող է պտտել տրված բլոկը աստիճան՝ քանի անգամ ցանկանա։ Նա պետք է տեղադրի այն այնպես, որ տրված բլոկը չհատվի արդեն ծածկված վանդակների հետ և դուրս չգա դաշտի սահամաններից։ Համլետը պետք է ձգտի բլոկը տեղադրել դաշտում այնպես, որ որքան հնարավոր է շատ տողեր և/կամ սյուներ ամբողջությամբ ծածկված լինեն բլոկներով։
Միավորների հաշվարկը կատարվում է հետևյալ կերպ․ Միայն մեկ տող կամ մեկ սյուն լրացնելու համար տրվում է միավոր, իսկ միանգամից տող կամ սյուն լրացնելու դեպքում տրվում է միավոր։ Այսինքն, միանգամից տող, կամ սյուն, կամ տող և սյուն լրացնելու դեպքում տրվում է միավոր, իսկ, օրինակ, միանգամից տող և սյուն լրացնելու դեպքում տրվում է միավոր։ Ի սկզբանե որևէ տող կամ սյուն լրիվ լցված չէ, այսինքն պարունակում է գոնե մեկ չծածկված վանդակ։
Ձեզ հարկավոր է պարզել, թե ամենաշատը քանի միավոր կարող է վաստակել Համլետը այս քայլից հետո։ Եթե բլոկը հնարավոր չէ տեղադրել այնպես, որ չհատվի արդեն ծածկված վանդակների հետ, հարկավոր է արտածել ։
Մուտքային տվյալներ
Առաջին տողերում տրված է վանդակավոր դաշտը։ Ամեն տողում վանդակները նշված են 0 թվանշանով, իսկ զբաղեցվածները՝ 1 թվանշանով (նկատեք, որ տողը տրված է առանց բացատների)։ -րդ տողում տրված է մի տառ՝ O, I, S կամ Z, որը ցույց է տալիս, թե Համելտն այս պահին որ բլոկը պետք է տեղադրի։
Ելքային տվյալներ
Ստանդարտ ելքում պետք է արտածել մեկ թիվ՝ մաքսիմալ միավորը, որ Համլետը կարող է ունենալ տրված բլոկը լավագույն կերպով տեղադրելու դեպքում, կամ ՝ , եթե այն հնարավոր չէ տեղադրել։
Օրինակ
Մուտք | Ելք |
|---|---|
00011000 | 120 |
00011000 | -1 |
01111101 | 175 |
01110110 | 75 |
Ենթախնդիրներ
Ենթախնդիր 0, (0 միավոր), օրինակները,
Ենթախնդիր 1, (25 միավոր), բոլոր թեստերում պետք է տեղադրել O տիպի բլոկ,
Ենթախնդիր 2, (25 միավոր), բոլոր թեստերում պետք է տեղադրել I տիպի բլոկ,
Ենթախնդիր 3, (25 միավոր), բոլոր թեստերում պետք է տեղադրել S տիպի բլոկ,
Ենթախնդիր 4, (25 միավոր), բոլոր թեստերում պետք է տեղադրել Z տիպի բլոկ:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB