PDA

Դիտել ողջ տարբերակը : Խնդիր խաղից



Artgeo
27.08.2008, 21:03
Մի հատ խաղ կա ուզում եմ գտնել լավագույն լուծումը :oy Հուսով եմ կօգնեք։

Կա 5x5 քառակուսի: Այդ քառակուսու մեջ պետք է ներկել
կապույտ
կարմիր
կանաչ
դեղին
գույներով: Ընդ որում, պայմաններն այսպիսին են:
Սկզբում քառակուսին դատարկ է:
կապույտ -ով կարող ենք ներկել ցանկացած վանդակ:
կարմիր-ով կարող ենք ներկել կապույտի կողքը: Այսինքն վերևից, ներքևից, աջից կամ ձախից պիտի լինի կապույտ
կանաչ-ով կարող ենք ներկել այն վանդակը որի հարևանությամբ կա կարմիր ու կապույտ վանդակ
դեղին-ով ներկելու համար անհրաժեշտ է, որ հարևանությամբ լինեն կանաչ, կարմիր ու կապույտ վանդակներ:

Վերջնական նպատակը առավելագույն դեղին վանդակներ ստանալն է:

Կաթիլ
27.08.2008, 22:15
Մի քիչ Sudoku-ին նմանեցրի :)
ինչքան էլ փորձեցի սրանից լավ տարբերակ չստացվեց... :oy

Artgeo
27.08.2008, 22:23
Մի քիչ Sudoku-ին նմանեցրի :)
ինչքան էլ փորձեցի սրանից լավ տարբերակ չստացվեց... :oy
Խնդիրը սխալ ես լուծել Կաթիլ ջան :) J, L և M տողերի կանաչների մեծ մասը հարևանությամբ կապույտ վանդակ չունի :think Հարևանությանը պիտի լինի վերևից, ներքևից, աջից կամ ձախից: Թեք հարևանությունը չի հաշվում:

Ի դեպ, մի կարևոր պայման ևս: Ցանկացած ներկած վանդակ, հետագայում կարելի է վերաներկել այլ պայմաններին բավարարող գույնով: Օրինակ ցանկացած կարմիր, կանաչ, դեղին վանդակ կարելի է ներկել կապույտ գույնի:

Կաթիլ
27.08.2008, 22:30
Խնդիրը սխալ ես լուծել Կաթիլ ջան :) J, L և M տողերի կանաչների մեծ մասը հարևանությամբ կապույտ վանդակ չունի :think Հարևանությանը պիտի լինի վերևից, ներքևից, աջից կամ ձախից: Թեք հարևանությունը չի հաշվում:

Ի դեպ, մի կարևոր պայման ևս: Ցանկացած ներկած վանդակ, հետագայում կարելի է վերաներկել այլ պայմաններին բավարարող գույնով: Օրինակ ցանկացած կարմիր, կանաչ, դեղին վանդակ կարելի է ներկել կապույտ գույնի:

:oy ես սխալ էի հասկացել...
բայց էդպես կստացվի՞ որ :think

Artgeo
27.08.2008, 22:35
:oy ես սխալ էի հասկացել...
բայց էդպես կստացվի՞ որ :think
Ինչ որ քանակ ստացվում ա, ես ուզում եմ իմանամ առավելագույն քանակը :)

Hayk Avetisyan
27.08.2008, 23:32
Շատ լավ մտածելու խաղ էր, ահագին բավականություն ստացա այն լուծելու ընթացքում

Artgeo
27.08.2008, 23:41
Շատ լավ մտածելու խաղ էր, ահագին բավականություն ստացա այն լուծելու ընթացքում
Չէ, մեկա դեղինների քանակը առավելագույնը չի:
Օրինակ երկրորդ տողում ձախից 1, 2, 3 ուղղահայացներում կարելի է կապույտներ շարել, հետո երրորդում դեղին, որից հետո առաջինում կարմիր ու հետ երկրորդում նույնպես դեղին: Ստացվեց +1 դեղին ;)

Hayk Avetisyan
28.08.2008, 00:10
փաստորեն լավից լավնելա լինում:)

Dayana
28.08.2008, 10:40
Արթուր, իսկ թե հետ հաշվարկով գաս՞, ասենք փորձես մաքսիմալ դեղիններ դնել, հետո մնացած գույները տեղավորել :) սկսելով 22 դեղինից ;)

Guest
28.08.2008, 11:04
Մի բան ընդամենը, եթե կարելի ա վերաներկել վանդակը ու նախորդ ներկած վանդակներից մեկը սկսի չբավարարել պայմաններին ապա կարող եմն ասել, որ հենց 22-ն ա պատասխանը:

Artgeo
28.08.2008, 11:07
Մի բան ընդամենը, եթե կարելի ա վերաներկել վանդակը ու նախորդ ներկած վանդակներից մեկը սկսի չբավարարել պայմաններին ապա կարող եմն ասել, որ հենց 22-ն ա պատասխանը:
Չէ, նախորդների վրա չի ազդում :) Կարևորը ներկելուց բավարարի պայմաններին ;)
Դե ցույց տուր, ո՞նց

ArmSOAD
29.08.2008, 14:14
Ժողովուրդ ջան, նախ պատասխանը 22 լինել ՉԻ ԿԱՐՈՂ, այն պարզ պատճառով, որ 5*5 տախտակը ունի 4 անկյուն, որոնցու դեղին չի դրվում: Այսինքն ամենաշատը կարող է 21 լինել:
Ես մի տարբերակում ստացել եմ 12:

Artgeo
29.08.2008, 14:18
Ժողովուրդ ջան, նախ պատասխանը 22 լինել ՉԻ ԿԱՐՈՂ, այն պարզ պատճառով, որ 5*5 տախտակը ունի 4 անկյուն, որոնցու դեղին չի դրվում: Այսինքն ամենաշատը կարող է 21 լինել:
Ես մի տարբերակում ստացել եմ 10:
Իսկ քայլ առ քայլ կասե՞ս :think

ArmSOAD
29.08.2008, 14:28
Իսկ քայլ առ քայլ կասե՞ս :think

Հեսա մի հատ գրեմ, մի 15 րոպեից կասեմ:
Ի դեպ արդեն 12 է:

ArmSOAD
29.08.2008, 14:49
Որեմն էսպես: Նախ պարզության համար նշանակել եմ`
կապույտ-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

ars83
29.08.2008, 16:11
Այսքան բան: Արդյունքում` 12 դեգհին::hands
Չեղավ։ Ամեն դեղինի հարևանությամբ (այսինքն՝ վերևից, ներքևից, կամ կողքերից) պետք է լինի կանաչ, կարմիր և կապույտ վանդակ։

Artgeo
29.08.2008, 16:23
Չեղավ։ Ամեն դեղինի հարևանությամբ (այսինքն՝ վերևից, ներքևից, կամ կողքերից) պետք է լինի կանաչ, կարմիր և կապույտ վանդակ։
Դեղինը դնելու պահին: Վերջնական արդյունքում էական չի :)

Դեռ չեմ փորձել, էսա նայեմ :)

ars83
29.08.2008, 16:49
Դեղինը դնելու պահին: Վերջնական արդյունքում էական չի :)

Հա՞։ Ես էլ գիտեի վերջում։ Ներողություն, այդ դեպքում։

Hayk Avetisyan
29.08.2008, 17:21
փաստորեն լավից լավնելա լինում:)

ինչի սրանից ավել կարա լինի? բոլոր պահանջներին բավարարում ա մաքսիմում քանակով դեղիններով

ars83
29.08.2008, 19:07
Այս խնդրի պայմանները ինչ–որ անհասկանալի են ձևակերպված։ Օրինակ, ԱրմՍՕԱԴ–ի առաջարկած լուծման առաջին քայլերում իրար կողք գտնվող a1 և b1 վանդակները ներկվում են կարմիր։ Հիմա կարելի՞ է ներկել b1–ը 2-րդ քայլում կարմիր, եթե նրա հարևանությամբ կապույտ չկա (a1–ը կարմիր է, c1 և b2՝ չներկված)։ Բացի դրանից, ընթացքում միևնույն վանդակը վերաներկվում է (19 և 21 քայլերում՝ d5 վանդակը), այդպես կարելի՞ է։

Մի քիչ խնդիրը նորմալ ձևակերպեք, հասկանանք :esim

Artgeo
29.08.2008, 19:16
Այս խնդրի պայմանները ինչ–որ անհասկանալի են ձևակերպված։ Օրինակ, ԱրմՍՕԱԴ–ի առաջարկած լուծման առաջին քայլերում իրար կողք գտնվող a1 և b1 վանդակները ներկվում են կարմիր։ Հիմա կարելի՞ է ներկել b1–ը 2-րդ քայլում կարմիր, եթե նրա հարևանությամբ կապույտ չկա (a1–ը կարմիր է, c1 և b2՝ չներկված)։
Ընդամենը ուշադրություն է հարկավոր

Սկզբում բոլորը կապույտ են:


Բացի դրանից, ընթացքում միևնույն վանդակը վերաներկվում է (19 և 21 քայլերում՝ d5 վանդակը), այդպես կարելի՞ է։

Մի քիչ խնդիրը նորմալ ձևակերպեք, հասկանանք :esim
Էս դեպքում էլ

Ի դեպ, մի կարևոր պայման ևս: Ցանկացած ներկած վանդակ, հետագայում կարելի է վերաներկել այլ պայմաններին բավարարող գույնով: Օրինակ ցանկացած կարմիր, կանաչ, դեղին վանդակ կարելի է ներկել կապույտ գույնի:

*e}|{uka*
29.08.2008, 19:53
ինչի սրանից ավել կարա լինի? բոլոր պահանջներին բավարարում ա մաքսիմում քանակով դեղիններով

Ճիշտա ասում Գլադը, դեղին գույնով ներկելու առավելագույն ինդեքսը 6-ա :)
Իսկ եթե կարելի է վերաներկել ապա կարող է և 21 լինել քանի որ գագաթների վանդակներում դեղին չի կարող լինել :

ArmSOAD
29.08.2008, 21:02
Ժող ջան ես մանրամասն իմ քայլերը գրել էի: Եթե ուշադիր կարդաք ու խնդրի պայմաններին էլ ծանոթ լինեք ավելորդ հարցեր չեն առաջանա: Իմ արդյունքը 12 ա: Թե ուրիշ ձև կարող եք ավելացնել, ձեզ տեսնեմ...:think

*e}|{uka*
29.08.2008, 21:48
Ժող ջան ես մանրամասն իմ քայլերը գրել էի: Եթե ուշադիր կարդաք ու խնդրի պայմաններին էլ ծանոթ լինեք ավելորդ հարցեր չեն առաջանա: Իմ արդյունքը 12 ա: Թե ուրիշ ձև կարող եք ավելացնել, ձեզ տեսնեմ...:think

Հա բայց քո օրինակում կան կանաչ վանդակներ, որոնց կարմիր ու կապույտ հարևան չեն նույնը և դեղին կա, ուշադիր չե՞ս եղել, թե՞ սխալ ես հասկացել:think



Ի դեպ, մի կարևոր պայման ևս: Ցանկացած ներկած վանդակ, հետագայում կարելի է վերաներկել այլ պայմաններին բավարարող գույնով: Օրինակ ցանկացած կարմիր, կանաչ, դեղին վանդակ կարելի է ներկել կապույտ գույնի:
ի~ ես խնդրի պայմանները փոխել եք?

Artgeo
29.08.2008, 21:57
ի~ ես խնդրի պայմանները փոխել եք?
չեմ փոխել, պարզապես մոռացել եմ գրել :oy հետո եմ ավելացրել :oy

*e}|{uka*
29.08.2008, 22:02
չեմ փոխել, պարզապես մոռացել եմ գրել :oy հետո եմ ավելացրել :oy

Արտ ջան ինչի՞ ես ամաչում :oy

Բայց էտ պայմանը չհաշված մաքսիմալը վեցա լինում :;)
Իսկ նենց ArmSOAD ճիշտա գրել :)

Artgeo
29.08.2008, 22:04
Արտ ջան ինչի՞ ես ամաչում :oy

Բայց էտ պայմանը չհաշված մաքսիմալը վեցա լինում :;)
Իսկ նենց ArmSOAD ճիշտա գրել :)
Դե ուրեմն մաքսիմալը 12 է, շնորհակալություն ArmSOAD-ին :)

Hayk Avetisyan
30.08.2008, 00:03
Դե ուրեմն մաքսիմալը 12 է, շնորհակալություն ArmSOAD-ին :)

ահա, խնդիրը կեսից փոխելը հետո լուծելը իհարկե ավելի հեշտա լինում:

ArmSOAD
30.08.2008, 11:41
Դե ուրեմն մաքսիմալը 12 է, շնորհակալություն ArmSOAD-ին :)

Խնդրեմ...;) Իզուր չեմ 1 տարի գրաֆների տեսություն սովորել փաստորեն:think:

ars83
11.09.2008, 15:14
Խնդրեմ...;) Իզուր չեմ 1 տարի գրաֆների տեսություն սովորել փաստորեն:think:
Ինձ մոտ էլ ստացվեց առավելագույն քանակը՝ 12։ Դրանից ավել ստանալն անհնար է։ Կցում եմ perl լեզվով (C/C++ –ով երկար կստացվեր) գրածս ծրագիրը, որը գտնում է դեղին վանդակների առավելագույն քանակը (իսկ որ այդպիսի ներկում գոյություն ունի, երևում է ArmSOAD-ի գրառումից)։

ArmSOAD, դու այս խնդիրը ի՞նչ ալգորիթմով ես լուծել և, արդյո՞ք ծրագիր ես գրել լուծելու համար։ Եթե դժվար չի, գրիր ալգորիթմը (այս բաժնում, կամ նամակով), ինձ շատ հետաքրքիր է։ Եթե քեզ հետաքրքրի, ես էլ կարող եմ իմ օգտագործած ալգորիթմը նկարագրել։

ArmSOAD
11.09.2008, 16:56
Ինձ մոտ էլ ստացվեց առավելագույն քանակը՝ 12։ Դրանից ավել ստանալն անհնար է։ Կցում եմ perl լեզվով (C/C++ –ով երկար կստացվեր) գրածս ծրագիրը, որը գտնում է դեղին վանդակների առավելագույն քանակը (իսկ որ այդպիսի ներկում գոյություն ունի, երևում է ArmSOAD-ի գրառումից)։

ArmSOAD, դու այս խնդիրը ի՞նչ ալգորիթմով ես լուծել և, արդյո՞ք ծրագիր ես գրել լուծելու համար։ Եթե դժվար չի, գրիր ալգորիթմը (այս բաժնում, կամ նամակով), ինձ շատ հետաքրքիր է։ Եթե քեզ հետաքրքրի, ես էլ կարող եմ իմ օգտագործած ալգորիթմը նկարագրել։

Չե ոչ մի ցրագրից չեմ օգտվել: Ալգորիթմ էլ առանձնապես չեի մտածել: Ուղղակի մի քանի բան փորձեցի, հասկացա, որ անկյունագծերով դասավորելը ամենա հարմարն է: Իսկ քայլերս արդեն գրել եմ: Բայց կուզենաի քո ալգորիթմին ծանոթանալ:

ars83
11.09.2008, 17:41
Չե ոչ մի ցրագրից չեմ օգտվել: Ալգորիթմ էլ առանձնապես չեի մտածել: Ուղղակի մի քանի բան փորձեցի, հասկացա, որ անկյունագծերով դասավորելը ամենա հարմարն է: Իսկ քայլերս արդեն գրել եմ: Բայց կուզենաի քո ալգորիթմին ծանոթանալ:
Երևի ավելի ճիշտ կլիներ ասել դատողություններ, քան ալգորիթմ...

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վ, բայց ինձ թվում է այս արդյունքը կարելի է լավացնել...

ArmSOAD
13.09.2008, 23:14
Շնորհակալություն այս մեծ պատասխանիդ համար;) Փաստորեն մենք 2 ով տվեցինք թեմայի հարցի պատասխանը. դու գտար մաքսիմալ հնարավոր քանակը, ես ել ցույց տվեցի նրա գոյությունը :)

Հ.Գ. Որ մի քիչ ազատ ժամանակ գտնեմ, կաշխատեմ քո մեթոդով ծրագիր գրել C++-ով: