Դիտել ողջ տարբերակը : Խնդիր խաղից
Մի հատ խաղ կա ուզում եմ գտնել լավագույն լուծումը :oy Հուսով եմ կօգնեք։
Կա 5x5 քառակուսի: Այդ քառակուսու մեջ պետք է ներկել
կապույտ
կարմիր
կանաչ
դեղին
գույներով: Ընդ որում, պայմաններն այսպիսին են:
Սկզբում քառակուսին դատարկ է:
կապույտ -ով կարող ենք ներկել ցանկացած վանդակ:
կարմիր-ով կարող ենք ներկել կապույտի կողքը: Այսինքն վերևից, ներքևից, աջից կամ ձախից պիտի լինի կապույտ
կանաչ-ով կարող ենք ներկել այն վանդակը որի հարևանությամբ կա կարմիր ու կապույտ վանդակ
դեղին-ով ներկելու համար անհրաժեշտ է, որ հարևանությամբ լինեն կանաչ, կարմիր ու կապույտ վանդակներ:
Վերջնական նպատակը առավելագույն դեղին վանդակներ ստանալն է:
Մի քիչ Sudoku-ին նմանեցրի :)
ինչքան էլ փորձեցի սրանից լավ տարբերակ չստացվեց... :oy
Մի քիչ Sudoku-ին նմանեցրի :)
ինչքան էլ փորձեցի սրանից լավ տարբերակ չստացվեց... :oy
Խնդիրը սխալ ես լուծել Կաթիլ ջան :) J, L և M տողերի կանաչների մեծ մասը հարևանությամբ կապույտ վանդակ չունի :think Հարևանությանը պիտի լինի վերևից, ներքևից, աջից կամ ձախից: Թեք հարևանությունը չի հաշվում:
Ի դեպ, մի կարևոր պայման ևս: Ցանկացած ներկած վանդակ, հետագայում կարելի է վերաներկել այլ պայմաններին բավարարող գույնով: Օրինակ ցանկացած կարմիր, կանաչ, դեղին վանդակ կարելի է ներկել կապույտ գույնի:
Խնդիրը սխալ ես լուծել Կաթիլ ջան :) J, L և M տողերի կանաչների մեծ մասը հարևանությամբ կապույտ վանդակ չունի :think Հարևանությանը պիտի լինի վերևից, ներքևից, աջից կամ ձախից: Թեք հարևանությունը չի հաշվում:
Ի դեպ, մի կարևոր պայման ևս: Ցանկացած ներկած վանդակ, հետագայում կարելի է վերաներկել այլ պայմաններին բավարարող գույնով: Օրինակ ցանկացած կարմիր, կանաչ, դեղին վանդակ կարելի է ներկել կապույտ գույնի:
:oy ես սխալ էի հասկացել...
բայց էդպես կստացվի՞ որ :think
:oy ես սխալ էի հասկացել...
բայց էդպես կստացվի՞ որ :think
Ինչ որ քանակ ստացվում ա, ես ուզում եմ իմանամ առավելագույն քանակը :)
Hayk Avetisyan
27.08.2008, 23:32
Շատ լավ մտածելու խաղ էր, ահագին բավականություն ստացա այն լուծելու ընթացքում
Շատ լավ մտածելու խաղ էր, ահագին բավականություն ստացա այն լուծելու ընթացքում
Չէ, մեկա դեղինների քանակը առավելագույնը չի:
Օրինակ երկրորդ տողում ձախից 1, 2, 3 ուղղահայացներում կարելի է կապույտներ շարել, հետո երրորդում դեղին, որից հետո առաջինում կարմիր ու հետ երկրորդում նույնպես դեղին: Ստացվեց +1 դեղին ;)
Hayk Avetisyan
28.08.2008, 00:10
փաստորեն լավից լավնելա լինում:)
Արթուր, իսկ թե հետ հաշվարկով գաս՞, ասենք փորձես մաքսիմալ դեղիններ դնել, հետո մնացած գույները տեղավորել :) սկսելով 22 դեղինից ;)
Մի բան ընդամենը, եթե կարելի ա վերաներկել վանդակը ու նախորդ ներկած վանդակներից մեկը սկսի չբավարարել պայմաններին ապա կարող եմն ասել, որ հենց 22-ն ա պատասխանը:
Մի բան ընդամենը, եթե կարելի ա վերաներկել վանդակը ու նախորդ ներկած վանդակներից մեկը սկսի չբավարարել պայմաններին ապա կարող եմն ասել, որ հենց 22-ն ա պատասխանը:
Չէ, նախորդների վրա չի ազդում :) Կարևորը ներկելուց բավարարի պայմաններին ;)
Դե ցույց տուր, ո՞նց
Ժողովուրդ ջան, նախ պատասխանը 22 լինել ՉԻ ԿԱՐՈՂ, այն պարզ պատճառով, որ 5*5 տախտակը ունի 4 անկյուն, որոնցու դեղին չի դրվում: Այսինքն ամենաշատը կարող է 21 լինել:
Ես մի տարբերակում ստացել եմ 12:
Ժողովուրդ ջան, նախ պատասխանը 22 լինել ՉԻ ԿԱՐՈՂ, այն պարզ պատճառով, որ 5*5 տախտակը ունի 4 անկյուն, որոնցու դեղին չի դրվում: Այսինքն ամենաշատը կարող է 21 լինել:
Ես մի տարբերակում ստացել եմ 10:
Իսկ քայլ առ քայլ կասե՞ս :think
Իսկ քայլ առ քայլ կասե՞ս :think
Հեսա մի հատ գրեմ, մի 15 րոպեից կասեմ:
Ի դեպ արդեն 12 է:
Որեմն էսպես: Նախ պարզության համար նշանակել եմ`
կապույտ-B
կարմիր-R
կանաչ-G
դեղին- Y
Տախտակի վանդակները համարակալված են a1-ից e5:
Սկզբում բոլորը կապույտ են:
1. a1-R
2. B1-R
3. B2-G
4. a2-Y
5. B1-Y
6. a3-R
7. B3-Y
8. B5-R
9. B4-G
10. a4-Y
11. B5-B
12. a5-R
13. B5-Y
14. c1-R
15. c2-Y
16. c3-R
17. c4-Y
18. c5-R
19. d5-R
20. d4-G
21. d5-Y
22. d3-Y
23. d1-R
24. d2-G
25. d1-Y
26. e1-R
27. e2-Y
28. e3-R
29. e4-Y
Այսքան բան: Արդյունքում` 12 դեգհին::hands
Այսքան բան: Արդյունքում` 12 դեգհին::hands
Չեղավ։ Ամեն դեղինի հարևանությամբ (այսինքն՝ վերևից, ներքևից, կամ կողքերից) պետք է լինի կանաչ, կարմիր և կապույտ վանդակ։
Չեղավ։ Ամեն դեղինի հարևանությամբ (այսինքն՝ վերևից, ներքևից, կամ կողքերից) պետք է լինի կանաչ, կարմիր և կապույտ վանդակ։
Դեղինը դնելու պահին: Վերջնական արդյունքում էական չի :)
Դեռ չեմ փորձել, էսա նայեմ :)
Դեղինը դնելու պահին: Վերջնական արդյունքում էական չի :)
Հա՞։ Ես էլ գիտեի վերջում։ Ներողություն, այդ դեպքում։
Hayk Avetisyan
29.08.2008, 17:21
փաստորեն լավից լավնելա լինում:)
ինչի սրանից ավել կարա լինի? բոլոր պահանջներին բավարարում ա մաքսիմում քանակով դեղիններով
Այս խնդրի պայմանները ինչ–որ անհասկանալի են ձևակերպված։ Օրինակ, ԱրմՍՕԱԴ–ի առաջարկած լուծման առաջին քայլերում իրար կողք գտնվող a1 և b1 վանդակները ներկվում են կարմիր։ Հիմա կարելի՞ է ներկել b1–ը 2-րդ քայլում կարմիր, եթե նրա հարևանությամբ կապույտ չկա (a1–ը կարմիր է, c1 և b2՝ չներկված)։ Բացի դրանից, ընթացքում միևնույն վանդակը վերաներկվում է (19 և 21 քայլերում՝ d5 վանդակը), այդպես կարելի՞ է։
Մի քիչ խնդիրը նորմալ ձևակերպեք, հասկանանք :esim
Այս խնդրի պայմանները ինչ–որ անհասկանալի են ձևակերպված։ Օրինակ, ԱրմՍՕԱԴ–ի առաջարկած լուծման առաջին քայլերում իրար կողք գտնվող a1 և b1 վանդակները ներկվում են կարմիր։ Հիմա կարելի՞ է ներկել b1–ը 2-րդ քայլում կարմիր, եթե նրա հարևանությամբ կապույտ չկա (a1–ը կարմիր է, c1 և b2՝ չներկված)։
Ընդամենը ուշադրություն է հարկավոր
Սկզբում բոլորը կապույտ են:
Բացի դրանից, ընթացքում միևնույն վանդակը վերաներկվում է (19 և 21 քայլերում՝ d5 վանդակը), այդպես կարելի՞ է։
Մի քիչ խնդիրը նորմալ ձևակերպեք, հասկանանք :esim
Էս դեպքում էլ
Ի դեպ, մի կարևոր պայման ևս: Ցանկացած ներկած վանդակ, հետագայում կարելի է վերաներկել այլ պայմաններին բավարարող գույնով: Օրինակ ցանկացած կարմիր, կանաչ, դեղին վանդակ կարելի է ներկել կապույտ գույնի:
*e}|{uka*
29.08.2008, 19:53
ինչի սրանից ավել կարա լինի? բոլոր պահանջներին բավարարում ա մաքսիմում քանակով դեղիններով
Ճիշտա ասում Գլադը, դեղին գույնով ներկելու առավելագույն ինդեքսը 6-ա :)
Իսկ եթե կարելի է վերաներկել ապա կարող է և 21 լինել քանի որ գագաթների վանդակներում դեղին չի կարող լինել :
Ժող ջան ես մանրամասն իմ քայլերը գրել էի: Եթե ուշադիր կարդաք ու խնդրի պայմաններին էլ ծանոթ լինեք ավելորդ հարցեր չեն առաջանա: Իմ արդյունքը 12 ա: Թե ուրիշ ձև կարող եք ավելացնել, ձեզ տեսնեմ...:think
*e}|{uka*
29.08.2008, 21:48
Ժող ջան ես մանրամասն իմ քայլերը գրել էի: Եթե ուշադիր կարդաք ու խնդրի պայմաններին էլ ծանոթ լինեք ավելորդ հարցեր չեն առաջանա: Իմ արդյունքը 12 ա: Թե ուրիշ ձև կարող եք ավելացնել, ձեզ տեսնեմ...:think
Հա բայց քո օրինակում կան կանաչ վանդակներ, որոնց կարմիր ու կապույտ հարևան չեն նույնը և դեղին կա, ուշադիր չե՞ս եղել, թե՞ սխալ ես հասկացել:think
Ի դեպ, մի կարևոր պայման ևս: Ցանկացած ներկած վանդակ, հետագայում կարելի է վերաներկել այլ պայմաններին բավարարող գույնով: Օրինակ ցանկացած կարմիր, կանաչ, դեղին վանդակ կարելի է ներկել կապույտ գույնի:
ի~ ես խնդրի պայմանները փոխել եք?
ի~ ես խնդրի պայմանները փոխել եք?
չեմ փոխել, պարզապես մոռացել եմ գրել :oy հետո եմ ավելացրել :oy
*e}|{uka*
29.08.2008, 22:02
չեմ փոխել, պարզապես մոռացել եմ գրել :oy հետո եմ ավելացրել :oy
Արտ ջան ինչի՞ ես ամաչում :oy
Բայց էտ պայմանը չհաշված մաքսիմալը վեցա լինում :;)
Իսկ նենց ArmSOAD ճիշտա գրել :)
Արտ ջան ինչի՞ ես ամաչում :oy
Բայց էտ պայմանը չհաշված մաքսիմալը վեցա լինում :;)
Իսկ նենց ArmSOAD ճիշտա գրել :)
Դե ուրեմն մաքսիմալը 12 է, շնորհակալություն ArmSOAD-ին :)
Hayk Avetisyan
30.08.2008, 00:03
Դե ուրեմն մաքսիմալը 12 է, շնորհակալություն ArmSOAD-ին :)
ահա, խնդիրը կեսից փոխելը հետո լուծելը իհարկե ավելի հեշտա լինում:
Դե ուրեմն մաքսիմալը 12 է, շնորհակալություն ArmSOAD-ին :)
Խնդրեմ...;) Իզուր չեմ 1 տարի գրաֆների տեսություն սովորել փաստորեն:think:
Խնդրեմ...;) Իզուր չեմ 1 տարի գրաֆների տեսություն սովորել փաստորեն:think:
Ինձ մոտ էլ ստացվեց առավելագույն քանակը՝ 12։ Դրանից ավել ստանալն անհնար է։ Կցում եմ perl լեզվով (C/C++ –ով երկար կստացվեր) գրածս ծրագիրը, որը գտնում է դեղին վանդակների առավելագույն քանակը (իսկ որ այդպիսի ներկում գոյություն ունի, երևում է ArmSOAD-ի գրառումից)։
ArmSOAD, դու այս խնդիրը ի՞նչ ալգորիթմով ես լուծել և, արդյո՞ք ծրագիր ես գրել լուծելու համար։ Եթե դժվար չի, գրիր ալգորիթմը (այս բաժնում, կամ նամակով), ինձ շատ հետաքրքիր է։ Եթե քեզ հետաքրքրի, ես էլ կարող եմ իմ օգտագործած ալգորիթմը նկարագրել։
Ինձ մոտ էլ ստացվեց առավելագույն քանակը՝ 12։ Դրանից ավել ստանալն անհնար է։ Կցում եմ perl լեզվով (C/C++ –ով երկար կստացվեր) գրածս ծրագիրը, որը գտնում է դեղին վանդակների առավելագույն քանակը (իսկ որ այդպիսի ներկում գոյություն ունի, երևում է ArmSOAD-ի գրառումից)։
ArmSOAD, դու այս խնդիրը ի՞նչ ալգորիթմով ես լուծել և, արդյո՞ք ծրագիր ես գրել լուծելու համար։ Եթե դժվար չի, գրիր ալգորիթմը (այս բաժնում, կամ նամակով), ինձ շատ հետաքրքիր է։ Եթե քեզ հետաքրքրի, ես էլ կարող եմ իմ օգտագործած ալգորիթմը նկարագրել։
Չե ոչ մի ցրագրից չեմ օգտվել: Ալգորիթմ էլ առանձնապես չեի մտածել: Ուղղակի մի քանի բան փորձեցի, հասկացա, որ անկյունագծերով դասավորելը ամենա հարմարն է: Իսկ քայլերս արդեն գրել եմ: Բայց կուզենաի քո ալգորիթմին ծանոթանալ:
Չե ոչ մի ցրագրից չեմ օգտվել: Ալգորիթմ էլ առանձնապես չեի մտածել: Ուղղակի մի քանի բան փորձեցի, հասկացա, որ անկյունագծերով դասավորելը ամենա հարմարն է: Իսկ քայլերս արդեն գրել եմ: Բայց կուզենաի քո ալգորիթմին ծանոթանալ:
Երևի ավելի ճիշտ կլիներ ասել դատողություններ, քան ալգորիթմ...
1. Տախտակի բոլոր հնարավոր ներկումները (նշանակություն չունի, թե ներկման որ քայլին են դրանք ստացվել) բաժանենք դասերի ըստ նրանցում դեղին վանդակների քանակի՝ Y[0], Y[1], ..., Y[21], որտեղ Y[N] ներկումների այն դասն է, որոնցում կա ճիշտ i հատ դեղին վանդակ։ Պարզ է, որ N–ը չի գերազանցում 21–ը, քանի որ անկյունների վանդակները հնարավոր չէ դեղին գույնով ներկել (մի քիչ ավելի ուշադիր ուսումնասիրությունը ցույց է տալիս, որ N-ը չի կարող գերազանցել նաև 18-ը բայց դա էական չի)։
2. Սկզբում ունենք որևէ ներկում Y[0] դասից։ Պարզ է, որ Y[i] դասի որևէ ներկում ունենալիս այդ պահին մեկ վանդակ ներկելով կարող է տեղի ունենալ հետևյալ դեպքերից միայն մեկը և այլ դեպք տեղի ունենալ չի կարող.
ա. ստանանք Y[i+1] դասի ներկում (որևէ կանաչ, կարմիր, կապույտ կամ չներկված վանդակ ներկել ենք դեղինով)
բ. ստանանք Y[i-1] դասի ներկում (դեղին վանդակներից մեկը ներկել ենք կանաչ, կարմիր կամ կապույտ գույնով)
գ. ստանանք Y[i] դասի ներկում (դեղինից բացի այլ գույնով ներկել ենք որևէ վանդակ, որը ներկված չէր կամ ներկված էր ոչ դեղին գույնով)։
Մեզ համար էական է միայն ա. դեպքը։
3. Կառուցենք ծառ, որի հանգույցներից յուրաքանչյուրը պարունակում է <a[1], a[2], ..., a[N]> տեսքի բուլյան վեկտոր՝ a[i]=1, եթե i-րդ վանդակը ներկված է դեղին, a[i]=0՝ հակառակ դեպքում։ Ծառը կառուցում ենք այսպես. գագաթում տեղադրում ենք <0, 0, ..., 0> վեկտորը, որպես նրա դուստր հանգույցվեր վերցնում ենք <1, 0, ..., 0>, <0, 1, 0, ..., 0>, ...., <0, 0, ..., 0, 1> վեկտորները։ Յուրաքանչյուր A=<a[1], a[2], ..., a[N]> վեկտորը պարունակող հանգույցի դուստր հանգույցները որոշում ենք հետևյալ կերպ.
B=<b[1], b[2], ..., b[N]>–ը A–ի դուստր հանգույցն է, եթե բավարարում է հետևյալ պայմաններին.
ա. Եթե k–ն ամենամեծ թիվն է, որի համար A վեկտորում a[k]=1 (այսինքն՝ a[k+1]=a[k+2]=...=a[N]=0), ապա B–ն պարունակում է ճիշտ մեկ հատ 1 a[k+1], a[k+2], ..., a[N] դիրքերից որևէ մեկում,
բ. Առաջին k բաղադրիչները A և B վեկտորների մոտ նույնն են՝ a[1]=b[1], a[2]=b[2], ..., a[k]=b[k]։
Այսպիսով, ծառի i-րդ շերտում գտնվում են Y[i] դասի ներկումները։ Ծառը կառուցելուց հետո բավական է գտնել նրա բարձրությունը՝ այսինքն ամենամեք P թիվը, որի համար ճանապարհ կա ծառի գագաթից մինչև այդ շերտի որևէ հանգույց (այսինքն, ենթադրաբար, կա ներկումների հաջորդականություն, որը կբերի P հատ դեղին վանդակ ունեցող ներկման)։
Մնացածը ծրագրավորման գործ է. կառուցում ես ծառը և գտնում նրա բարձրությունը։ Նոր հանգույցն ավելացնելիս ստուգվում է՝ արդյոք կարելի է այն ծնող–հանգույցից ստանալ առանց խնդրի պայմանները խախտելու, այսինքն, ներկվող դեղին վանդակի շուրջը կա՞ արդյոք առնվազն 3 ոչ դեղին վանդակ։
Ծրագիրը տալիս է ծառի խորությունը 12։ Դա նշանակում է, որ կարող է գոյություն ունենալ 12 դեղին վանդակից ոչ ավել դեղին վանդակ պարունակող ներկում. քո ներկումը ցույց է տալիս, որ այդ առավելագույն թւվը հասանելի է։
Հ.Գ. Իդեպ, ժողովուրդ, եթե որևէ մեկը առավելագույն դեղին վանդակների քանակը պարզող ծրագիր գրեր C կամ C++ –ով կամ Java–ով, հետաքրքիր կլիներ պարզել ծրագրերի աշխատանքի ժամանակները։ Իմը կազմում է 7.36վ, բայց ինձ թվում է այս արդյունքը կարելի է լավացնել...
Շնորհակալություն այս մեծ պատասխանիդ համար;) Փաստորեն մենք 2 ով տվեցինք թեմայի հարցի պատասխանը. դու գտար մաքսիմալ հնարավոր քանակը, ես ել ցույց տվեցի նրա գոյությունը :)
Հ.Գ. Որ մի քիչ ազատ ժամանակ գտնեմ, կաշխատեմ քո մեթոդով ծրագիր գրել C++-ով: