Jump to content
php.lv forumi

Kārtējais uzdevums


Леший

Recommended Posts

Nu ja jau aizgaja mode uz uzdevumiem, tad viens no manis. Ir atrodams internetos, bet labāk tomēr padomājiet paši. Risinājumus kā vienmēr publicējam zem spoiler tegiem.

 

Tu atrodies cietumā, vienā kamerā ar savu draugu. Tad tevi aizved uz citu istabu, kur ir sargs un šaha dēlis. Sargs saliek uz dēļa 64 vienādas monētas random veidā, dažās ar aversu uz augšu, dažās ar reversu (var būt arī visas ar aversu vai otrādi). Pēc tam sargs parāda uz monētu A (randomā). Tad tev ir iespēja apgriezt otrādi tikai vienu monētu (jebkuru, var to pašu A monētu, var arī neapgriezt nevienu). Tad tev ir jāiet trešajā istabā, bet tavu draugu ielaiž otrajā istabā, un viņam ir jāatrod monētu A.

Pirms tas viss notiks, jūs abi zināt, kāds būs uzdevums, tāpēc pirms tevi ielaiž istabā ar monētām, jums ar draugu ir iespēja izdomāt stratēģiju. Uzdevums ir atrast tādu stratēģiju.

 

Uzdevumam ir 100% risinājums, bet es to nezinu. Nebija laika pieķerties šim uzdevumam, bet plānoju to izdarīt tuvākajā laikā.

Link to comment
Share on other sites

 

 

Vispārējs risinājums:

Sākuma sagrupējat visus 64 bitu skaitļus 64 grupās tā, lai katrā grupā ir skaitļi tā, lai samainot kādu no 63 bitiem, iegūst skaitli citā grupā.

Izveidot no monētām 64 bitu skaitli. 

Tu no sarga uzliktā stāvokļa izrēķini šo 64 bitu skaitli, tad sargs parāda uz šo monētu.

Tu izdomā, kuru bitu jāmaina, lai no sarga uzliktā 64 bitu skaitļa, iegūtu skaitli grupā, kurai atbilst monēta uz kuru sargs norādīja.

Kad ienāk tavs draugs, viņš nosaka jauno 64 bitu skaitli un pēc grupas, kurai šis skaitlis pieder, nosaka, kuru monētu sargs norādīja.

 

Pilnīgam risinājumam jāizdomā, kā vienkārši sagrupēt visus šos 64 bitu skaitļus 64 grupās.

 

 

 

 

 

Ā, izdomāju.

Paņem katram bitam ar vērtību "1" kārtas numurus un sasummē tos, piemēram, skaitlis 10011 dos 5 + 2 + 1 =8

Tad izrēķini atlikumu dalot ar 64, iegūsi 0 - 63.

Tad izmainot vienu no 64 bitiem var iegūt jebkuru atlikumu no 0 - 63.

Šis atlikums arī norādīs uz monētu uz kuru sargs norādīja.

 

Edit:

Tomēr, šis sadalījums laikam nav pareizi.

Šis nav pareiz, tāpēc, ka mainot x-to bitu no 0 uz 1, pie atlikuma iegūst +x, bet no 1 uz 0, 64-x, kas mums sliktākajā gadījumā, izmainot vienu bitu, garantē iegūt tikai 32 dažādus atlikumus.

Jāpadomā vēl.

 

 

Edited by codez
Link to comment
Share on other sites

Pietika, būtībā mans vispārīgais risinājums jau ir pareizs.

 

 

Vienīgais, lai cilvēkam būtu saprotams, vajag izdomāt kā vienkārši sagrupēt tos 64 bitu skaitļus. Linkos jau arī ir kompleksa grupēšana ar xor-iem no xor-iem.

Vispārīgā gadījumā var uzbūvēt pilnu grafu, kur virsotnes ir kombinācijas, bet šķautnes 1 bita pārveidojumi un sagrupēt.

 

 

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
×
×
  • Create New...