題目 1959:
藍(lán)橋杯算法提高VIP-Light Bulbs
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 10 解決: 0
題目描述
好萊塢最新的劇院“the Atheneum of Culture and Movies”擁有一個(gè)由計(jì)算機(jī)控制的成千上萬(wàn)個(gè)燈泡組成的巨型熒幕。每行燈泡都用由電腦操作的一系列開(kāi)關(guān)控制。不幸的是，電工接錯(cuò)了開(kāi)關(guān)的型號(hào)，并且今天晚上就是ACM的開(kāi)幕式。你需要寫(xiě)個(gè)程序讓這些開(kāi)關(guān)正確的運(yùn)作。
熒幕的一排有n個(gè)燈泡，它們被n個(gè)開(kāi)關(guān)控制。燈泡和開(kāi)關(guān)都從左至右依次編號(hào)為1到n。每個(gè)燈泡要么是開(kāi)的，要么是關(guān)的。每組輸入數(shù)據(jù)含有一排燈泡的起始狀態(tài)和目標(biāo)狀態(tài)。
最初的計(jì)劃是讓一個(gè)開(kāi)關(guān)控制一個(gè)燈泡。但是電工的失誤導(dǎo)致了每個(gè)開(kāi)關(guān)控制2或3個(gè)燈泡，如圖1所示。最左邊的開(kāi)關(guān)（i=1）控制最左邊的兩個(gè)燈泡（1和2）；最右邊的燈泡（i=n）控制最右邊的兩個(gè)燈泡（n-1和n）。剩下的開(kāi)關(guān)（1<i<n）控制3個(gè)燈泡i-1，i和i+1。（特別的，如果只有1個(gè)燈泡，那么就只有1個(gè)開(kāi)關(guān)控制那唯一的燈泡。）也就是說(shuō)，如果燈泡1是開(kāi)的，燈泡2是關(guān)的，轉(zhuǎn)換開(kāi)關(guān)1則會(huì)導(dǎo)致燈泡1關(guān)上，燈泡2打開(kāi)。最少的代價(jià)是指將這一排燈泡從初始狀態(tài)轉(zhuǎn)換到最終狀態(tài)所需要轉(zhuǎn)換的最少的開(kāi)關(guān)數(shù)。
你可以將一排開(kāi)關(guān)的狀態(tài)表示為二進(jìn)制數(shù)，0表示關(guān)，1表示開(kāi)。舉例來(lái)說(shuō)，01100表示一排5個(gè)燈泡，其中第二個(gè)和第三個(gè)是開(kāi)的。如果要把這個(gè)狀態(tài)轉(zhuǎn)化到10000，可以轉(zhuǎn)換開(kāi)關(guān)1、4、5，或者轉(zhuǎn)換開(kāi)關(guān)2。
你需要寫(xiě)個(gè)程序來(lái)決定最少轉(zhuǎn)換哪些開(kāi)關(guān)使得這排燈泡從初始狀態(tài)變?yōu)槟繕?biāo)狀態(tài)。有些初始狀態(tài)和目標(biāo)狀態(tài)是無(wú)解的。為了壓縮數(shù)據(jù)，我們用10進(jìn)制來(lái)輸入。也就是說(shuō)，01100和10000將用12和16來(lái)表示。
熒幕的一排有n個(gè)燈泡，它們被n個(gè)開(kāi)關(guān)控制。燈泡和開(kāi)關(guān)都從左至右依次編號(hào)為1到n。每個(gè)燈泡要么是開(kāi)的，要么是關(guān)的。每組輸入數(shù)據(jù)含有一排燈泡的起始狀態(tài)和目標(biāo)狀態(tài)。
最初的計(jì)劃是讓一個(gè)開(kāi)關(guān)控制一個(gè)燈泡。但是電工的失誤導(dǎo)致了每個(gè)開(kāi)關(guān)控制2或3個(gè)燈泡，如圖1所示。最左邊的開(kāi)關(guān)（i=1）控制最左邊的兩個(gè)燈泡（1和2）；最右邊的燈泡（i=n）控制最右邊的兩個(gè)燈泡（n-1和n）。剩下的開(kāi)關(guān)（1<i<n）控制3個(gè)燈泡i-1，i和i+1。（特別的，如果只有1個(gè)燈泡，那么就只有1個(gè)開(kāi)關(guān)控制那唯一的燈泡。）也就是說(shuō)，如果燈泡1是開(kāi)的，燈泡2是關(guān)的，轉(zhuǎn)換開(kāi)關(guān)1則會(huì)導(dǎo)致燈泡1關(guān)上，燈泡2打開(kāi)。最少的代價(jià)是指將這一排燈泡從初始狀態(tài)轉(zhuǎn)換到最終狀態(tài)所需要轉(zhuǎn)換的最少的開(kāi)關(guān)數(shù)。
你可以將一排開(kāi)關(guān)的狀態(tài)表示為二進(jìn)制數(shù)，0表示關(guān)，1表示開(kāi)。舉例來(lái)說(shuō)，01100表示一排5個(gè)燈泡，其中第二個(gè)和第三個(gè)是開(kāi)的。如果要把這個(gè)狀態(tài)轉(zhuǎn)化到10000，可以轉(zhuǎn)換開(kāi)關(guān)1、4、5，或者轉(zhuǎn)換開(kāi)關(guān)2。
你需要寫(xiě)個(gè)程序來(lái)決定最少轉(zhuǎn)換哪些開(kāi)關(guān)使得這排燈泡從初始狀態(tài)變?yōu)槟繕?biāo)狀態(tài)。有些初始狀態(tài)和目標(biāo)狀態(tài)是無(wú)解的。為了壓縮數(shù)據(jù)，我們用10進(jìn)制來(lái)輸入。也就是說(shuō)，01100和10000將用12和16來(lái)表示。
輸入格式
輸入數(shù)據(jù)有多個(gè)case。每個(gè)case一行，2個(gè)非負(fù)整數(shù)，其中至少有一個(gè)是整數(shù)，并且不超過(guò)100個(gè)數(shù)字。第一個(gè)數(shù)字表示開(kāi)始狀態(tài)，第二個(gè)數(shù)字表示目標(biāo)狀態(tài)。這些數(shù)字化為2進(jìn)制后表示一行燈泡的狀態(tài)，1是開(kāi)，0是關(guān)。
為了避免二進(jìn)制數(shù)中出現(xiàn)前導(dǎo)0的問(wèn)題，數(shù)據(jù)保證第一個(gè)燈泡要么在起始狀態(tài)是亮的，要么是在目標(biāo)狀態(tài)是亮的（或者都是亮的）。輸入保證沒(méi)有多余的空格，輸入的10進(jìn)制數(shù)中沒(méi)有前導(dǎo)0，兩個(gè)數(shù)由一個(gè)空格隔開(kāi)。
為了避免二進(jìn)制數(shù)中出現(xiàn)前導(dǎo)0的問(wèn)題，數(shù)據(jù)保證第一個(gè)燈泡要么在起始狀態(tài)是亮的，要么是在目標(biāo)狀態(tài)是亮的（或者都是亮的）。輸入保證沒(méi)有多余的空格，輸入的10進(jìn)制數(shù)中沒(méi)有前導(dǎo)0，兩個(gè)數(shù)由一個(gè)空格隔開(kāi)。
輸出格式
對(duì)每個(gè)case，輸出一行。包括case編號(hào)和一個(gè)十進(jìn)制數(shù)。這個(gè)十進(jìn)制數(shù)表示在最小代價(jià)下，需要轉(zhuǎn)換的開(kāi)關(guān)的狀態(tài)。也就是說(shuō)如果把這個(gè)數(shù)轉(zhuǎn)為2進(jìn)制后，最右邊的位（最低位）代表第n個(gè)開(kāi)關(guān)的狀態(tài)，1表示開(kāi)關(guān)轉(zhuǎn)換過(guò)，0表示沒(méi)有。如果無(wú)解，輸出“impossible”。如果有多組解，輸出轉(zhuǎn)成十進(jìn)制后最小的那一個(gè)。
在每個(gè)case間輸出一個(gè)空行，用輸出樣例顯示的格式輸出。
在每個(gè)case間輸出一個(gè)空行，用輸出樣例顯示的格式輸出。
樣例輸入
12 16 1 1 3 0 30 5 7038312 7427958190 4253404109 657546225 0 0
樣例輸出
Case Number 1: 8 Case Number 2: 0 Case Number 3: 1 Case Number 4: 10 Case Number 5: 2805591535 Case Number 6: impossible
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情