Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Бүх бодолтууд Шилдэг бодолтууд PDF Жагсаалт руу буцах

RGB7792 - Гена Ханойн цамхгаар тоглож байна

Ханой цамхаг бол 3 шон болон өөр өөр диаметр бүхий хэдэн дискээс бүрддэг алдартай тоглоом юм.

Энэхүү тоглоомыг  томоос нь жижиг хэмжээтэй рүү давхарласан нэг шонгийн хамгийн дээд жижиг дискийг зөөж эхэлдэг.

Тоглоомын зорилго нь дараах дүрмээр нэг шонгоос нөгөө шон руу бүх дискийг зөөх явдал юм.

 1. Нэг удаад зөвхөн нэг диск зөөх боломжтой.

 2. Хөдөлгөөн бүрд орой дахь дискийг давхарласан дискээс аваад өөр давхарласан дискүүдийн дээд хэсэгт шилжүүлнэ.

3. Жижиг дискийн дээр том диск байрлуулж болохгүй.

Генад Ханой цамхаг тоглоомын өөрчлөгдсөн хувилбар байна.

Түүнд 4 шон, N дискүүдын томыг доор байрлуулан давхарласан Ханой тоглоом байна.

Тэрээр хэд хэдэн алхам (дээрх дүрмийг дагаж) хийв. Дараа нь тэр түр завсарлаад байтал цааш зөөх байрлалаа алджээ.

Тэрээр зөв алхам хийсээр буцааж Ханой цамхгийг анхны байдалд нь оруулахыг хүсч байна.

Генагийн Ханой цамхгийн өгөгдсөн байрлалаас цамхгийн анхны байдалд нь оруулахад шаардлагатай диск

зөөх хамгийн бага тоог тооцоолоход нь тусална уу.

Тайлбар: Генагийн шонгууд 1, 2, 3, 4 гэж дугаарлагдсан. Бүх диск нэгдүгээр шон дээр байрласан.

Оролтын хэлбэр

Эхний мөрд дискийн тоог илэрхийлэх N бүхэл тоо өгөгдөнө.

Хоёрдугаар мөрд N ширхэг тоонууд зайгаар тусгаарлагдан өгөгдөнө. i-р тоо нь i-р диск хэд дугаартай шон дээр байгааг илэрхийлнэ.  

Зааглалт

 1 <= N <= 10

Гаралтын хэлбэр

Гена нэгдүгээр шонд дискүүдийг буцаан байрлуулахад шаардагдах хамгийн цөөн диск зөөх тоо болох нэг бүхэл тоо байна.

Жишээ

Оролт

3

1 4 1

Гаралт

3

Тайлбар

Диск зөөх үйлдлийг 3 удаа хийхэд хангалттай. Дор нэг боломжит шийдлийг харуулав.

 

Орчуулсан : Р.Мижиддорж МУБИС, доктор


Submit solution!
Нэмсэн:Bataa
Огноо:2020-04-12
Хугацааны хязгаарлалт:1s
Эх кодын хэмжээний хязгаарлалт:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Програмчлалын хэлүүд:ADA95 ASM32 ASM64 BASH BF C NCSHARP CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO JULIA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYPY3 PYTHON3 RUBY SCALA SCM guile ST TCL WHITESPACE
Эх сурвалж:https://www.hackerrank.com/challenges/gena/problem
hide comments
2024-01-22 12:28:19
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to calculate the minimum number of moves
int minMovesToOriginalState(int N, vector<int>& discs) {
vector<int> targetState(N, 1); // The target state is all discs on the first pole
int moves = 0;

for (int i = N - 1; i >= 0; --i) {
if (discs[i] == 1) {
// If the disc is already on the first pole, move to the next disc
continue;
} else {
// Move the disc to the first pole
moves++;
discs[i] = 1;
}
}

// Sort the target state to match the original order
sort(targetState.begin(), targetState.end());

// Compare the current state with the sorted target state
while (discs != targetState) {
for (int i = 0; i < N; ++i) {
if (discs[i] != targetState[i]) {
// Move the disc to the correct pole
moves++;
discs[i] = targetState[i];
}
}
}

return moves;
}

int main() {
int N;
cin >> N;

vector<int> discs(N);
for (int i = 0; i < N; ++i) {
cin >> discs[i];
}

int result = minMovesToOriginalState(N, discs);

cout << result << endl;

return 0;
}
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.