Премини към съдържанието

Препоръчан отговор


Здравейте! Тези дни реших да реша някои от задачите, които се се паднали на националните олимпиади по програмиране. Проблемът ми е, че за повечето успявам да измисля алгоритъм, но не достатъчно оптимален. Твърде наивен. Например днес се мъча с ето тази задача, която е за 12 клас:
 

Задача A2. САМОТНА ПЕЙКА

Пейката в метрото има n места, номерирани с числата от 1 до n. В началото пейката е празна – всичките n места са свободни. Последователно, един по един, през входа на метрото влизат пътници. Всеки влязъл човек сяда в центъра на първата максимална последователност от свободни места. В случай, че максималната последователност от свободни места съдържа четен брой места, човекът сяда на мястото с по-малък номер измежду двете централни места на последователността.

Например, ако пейката има n = 6 места, първият човек сяда на място с номер 3, защото има единствена максимална последователност от свободни места – от 1 до 6, която съдържа четен брой места, и 3 е мястото с по-малък номер измежду двете централни места (3 и 4) на тази последователност. За втория човек има две последователности от свободни места – от място 1 до място 2 и от място 4 до място 6. Последователността от място 4 до място 6 е максимална, съдържаща 3 места, и вторият човек сяда в центъра  – място 5. Третият човек сяда на място с номер 1 – „централното” за последователността от свободни места от първо до второ, четвъртият човек – на място 2, петият – на място 4 и шестият – на място 6.

Напишете програма bench, която определя мястото, на което сяда определен човек, и кой човек сяда на предварително зададено място.

Вход

От стандартният вход се въвежда един ред с три цели чиста: n i p, разделени с интервал, където:

  • n е общият брой места на пейката;
  • i е номер на човек, влязъл в метрото (първият влязъл има номер 1);
  • p представлява номер на място от пейката.

 Изход

Програмата трябва да извежда на стандартния изход един ред с две цели числа q и j, разделени с интервал, за които е изпълнено, че:

  • i-тият човек, влязъл в метрото сяда на място с номер q и
  • j-тият човек, влязъл в метрото сяда на място с номер p.

Ограничения

1 ≤ i, pn ≤ 1016

В 20% от тестовете е изпълнено n ≤ 10000.

В други 30% от тестовете, n = 2k-1, където k>0 е цяло число.

Пример 1   Пример 2

Вход   Вход

6 1 5   10 2 6

Изход   Изход

3 2                                                 8 5

 

 

Накратко имам една пейка в метрото. Всеки нов пътник сяда точно в средата на най-дългото място от свободни седалки. И така докато всички седалки бъдат запълнени. Трябва да намеря мястото, на което ще седнe даден пореден пътник и кой поред пътник ще седне на дадено място.

 

Алгоритъма, който аз успях да напиша е твърде елементарен. При всяко влизане на нов пътник аз обхождам масива с n седалки и търся най-дългата свободна редица. След това маркирам средната седалка на тази редица като използвана и така се получават две отделни редици. Но този метод е твърде бавен. Както пише в условието n може да бъде до 10^16, а аз не мога да направя толкова голям масив. А и да успея ще ми трябва доста време за да го обходя.

Чуда се дали знаете за някаква техника, която да ми помогне. Може би трябва да се използва някаква формула? И също ще се радвам, ако можете да ми кажете как да започна да измислям добри алгоритми.. Ако можете да ми препоръчате някаква книга, която да развива мисленето на човека или нещо подобно? Защото няма как да стана добър програмист без да прочета нещо от някъде нали :D В книгите от които учих C++ бяха дадени само основни примери и задачи, но не и по-трудни проблеми като този. :)

Поздрави!

 

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Чуда се дали знаете за някаква техника, която да ми помогне. Може би трябва да се използва някаква формула? И също ще се радвам, ако можете да ми кажете как да започна да измислям добри алгоритми.. Ако можете да ми препоръчате някаква книга, която да развива мисленето на човека или нещо подобно? Защото няма как да стана добър програмист без да прочета нещо от някъде нали :D В книгите от които учих C++ бяха дадени само основни примери и задачи, но не и по-трудни проблеми като този. :)

Мога да добавя още едно нещо към препоръките на soundtracker, които са много добри. И това е, че добър, във каквото и да е, се става със знания и опит. Ако целта са ти алгоритми и задачи, освен четенето на теория, бих ти препоръчал да си намериш решени задачи и много хубаво да ги разбереш, да осмислиш мотивите за избор на решението и самата му реализация. Да го кажа по такъв начин: ако знаеш решенията на 50 различни проблема, като дойде 51ият, в най-лошия случай ще знаеш 50 възможни начина, които директно да отхвърлиш. Но по-вероятно е, поне нещо от тях да те насочи към решението.

Относно задачата.

Мисля, че и двамата имате една и съща солидна грешка в подхода. При положение, че имате директно и еднозначно дефинирана редица и то само от 2 числа - големината на пейката и номера на човека или съответно седалката, вие реално знаете, къде е той. Няма нужда да го търсите, независимо с колко сложен или ефективен метод. Е, може би не е толкова очевидно, но... Не мисля да решавам задачата, само ще продължа подсказката от условието.

вземаме 30те % в които n = 2k -1,  Това не е случайна стойност. Всъщност това е best-case на задачата. Тоест:

  • проверката дали число е от вида 2k -1 е елементарна
  • първият седнал ще раздели пейката на две равни половини и то забележете как:
  • всяка половина ще е (2k -1 - 1) / 2 = (2k - 2) / 2 = 2k-1 - 1 - т.е число от същия вид.
  • тоест първият човек ще я раздели на 2, първите 3ма на 4, първите 7 на 8 и т.н равни части. Не е ли прекрасно?
  • намираме колко е броят на хората, които ще разделят пейката по такъв начин преди да седне нашия човек: това е най-голямата стойност 2m -1 < i, Може с побитови операции или логаритъм с основа 2 - избирате си.
  • към момента след сядане на 2m -1вия човек, на пейката има 2m празни места, всяко от по (n - 2m -1) / 2m седалки.
  • Е те са еднакви, значи просто всеки следващ ще сяда в средата на първата свободна, по ред.
  • значи нашия човек ще седне в средата на (i - 2m -1) % 2m -тото празно място (% -  остатък от деленето).
  • Това дотук се разписва в формула на 1 ред.

От мен толкова. :)

  • Харесва ми 4

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

За да продължа обаче по-нататък с помощта, трябва да ми отговорите на следните въпроси:

1) Знаете ли какво са Binary Tree и Heap ? Можете ли да боравите с тях и знаете ли как ?

2) Знаете ли какво е Balanced Tree и каква е идеята, заложено в него ?

3) Знаете ли какво е B-Tree - какво представлява и с какво се различава от горното ?

4) Знаете ли какво представлява алгоритъма Alpha-Beta Pruning ? Той ще е необходим за оптимизирането на работата на алгоритъма Ви.

Мерси за предложените алгоритми. 1) и 2) знам какво представляват, но за 3) и 4) не мога да кажа същото. Ще ги разгледам по-подробно :)

 

 

Други, които мога да дам като пример са тези две:

Основи на алгоритмите

Алгоритми на С

За съжаление втората книга не мога да я намеря в наличност. Първата съм я разглеждал и аз, но ми се стори, че по-голямата част от кода е на Pascal и може би малко по-трудно ще осмисля съдържанието. Може би някоя книга, която използва C/C++, C# или Java ще е по-добър избор :)

 

 

@flare, мерси много за предложената формула. Ще се опитам да я реализирам. А откъде мога да намеря решени задачи? Може би можете да ми препоръчате някоя книга или сайт?  :)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Коментар-допълнение в телеграфен стил:

 

Първата книга е много добра и не отстъпва на чуждестранните такива. Третата я има на английски, ако ви устройва -- Algorithms in C. Акцентира повече върху имплементацията, отколкото върху теорията и анализа. Introduction to Algorithms  е класическа.

 

Освен това, курсовете на Масачузетския институт може да са от полза: http://ocw.mit.edu

Редактирано от arcane (преглед на промените)

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

@flare, мерси много за предложената формула. Ще се опитам да я реализирам.

Че тя е реализирана. По скоро помисли, как да я разшириш за случаите, когато n != 2k -1...

 

А откъде мога да намеря решени задачи?

Google. Редактирано от flare (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Регистрирайте се или влезете в профила си за да коментирате

Трябва да имате регистрация за да може да коментирате това

Регистрирайте се

Създайте нова регистрация в нашия форум. Лесно е!

Нова регистрация

Вход

Имате регистрация? Влезте от тук.

Вход

  • Разглеждащи това в момента   0 потребители

    Няма регистрирани потребители разглеждащи тази страница.

  • Горещи теми в момента

  • Подобни теми

    • от Chris Panov
      Здравейте, 
      В момента пиша една програма, в която в една от функциите ми се налага да излезна по-рано при определено условие. Функцията връща string впрочем.
      Ето кодът:
       
      #include "stdafx.h" #include <iostream> #include <string> #include <sstream> #include <vector> #define CONSOLE_LOG(x) std::cout << x #define COMMAND_END command[0] #define COMMAND_SUM command[1] #define COMMAND_SUBTRACT command[2] #define COMMAND_CONCAT command[3] #define COMMAND_DISCARD command[4] #define COMMAND_DISPSEQ command[5] template <typename T> void top_back(std::vector<T>& v) {     v.erase(v.end() - 1); } std::string sum(std::string& x, std::string& y, std::vector<std::string>& vec) {     int xInt = atoi(x.c_str());     int yInt = atoi(y.c_str());     int result = xInt + yInt;     std::ostringstream os;     std::string strResult;     os << result;     strResult = os.str();     top_back(vec);     top_back(vec);     return strResult; } std::string subtract(std::string& x, std::string& y, std::vector<std::string>& vec) {     int xInt = atoi(x.c_str());     int yInt = atoi(y.c_str());     int result = xInt - yInt;     std::ostringstream os;     std::string strResult;     os << result;     strResult = os.str();     top_back(vec);     top_back(vec);     return strResult; } std::string concat(std::string& x, std::string& y, std::vector<std::string>& vec) {     if (atoi(x.c_str()) < 0)     {         return;     }     else {         std::string concatStr = y + x;         top_back(vec);         top_back(vec);         return concatStr;     } } void dispseq(std::vector<std::string>& vec) {     std::vector<std::string>::const_iterator iter;     for (iter = vec.begin(); iter != vec.end(); iter++)     {         std::cout << *iter << std::endl;     } } void enterSequence() {     std::vector<std::string> command =     {         "end",         "sum",         "subtract",         "concat",         "discard",         "dispseq"     };     std::vector<std::string> sequence;     std::string input;     std::string a;     std::string b;     do     {         std::cin >> input;         sequence.emplace_back(input);         if (input == COMMAND_END)         {              top_back(sequence);         }         if (input == COMMAND_SUM)         {             top_back(sequence);             a = sequence[sequence.size() - 1];             b = sequence[sequence.size() - 2];             sequence.emplace_back(sum(a, b, sequence));         }         if (input == COMMAND_SUBTRACT)         {             top_back(sequence);             a = sequence[sequence.size() - 1];             b = sequence[sequence.size() - 2];             sequence.emplace_back(subtract(a, b, sequence));         }         if (input == COMMAND_CONCAT)         {             top_back(sequence);             a = sequence[sequence.size() - 1];             b = sequence[sequence.size() - 2];             sequence.emplace_back(concat(a, b, sequence));         }         if (input == COMMAND_DISCARD)         {             top_back(sequence);             top_back(sequence);         }         if (input == COMMAND_DISPSEQ)         {             top_back(sequence);             dispseq(sequence);         }     } while (input != COMMAND_END); } int main() {     enterSequence();     std::cin.get();     std::cin.get();     return 0; } И ето проблемната функция:
       
      std::string concat(std::string& x, std::string& y, std::vector<std::string>& vec) {     if (atoi(x.c_str()) < 0)     {         return;     }     else {         std::string concatStr = y + x;         top_back(vec);         top_back(vec);         return concatStr;     } }  
      Както виждате ако стрингът x(който естествено го превръщам в интиджър) е по-малък от 0, теоритично трябва да излезна от функцията, и това е единственият начин за който се сетих, с return;, обаче пък компилаторът иска функцията да връща стойност, понеже е от тип стринг.
      Как да съчетая двете? - да връща стринг ако всичко е по план, и да излиза ако е по-малко от 0.
    • от Chris Panov
      Здравейте,
      В момента имам сериозен проблем със взимането на броят на елементи в даден вектор.
      vec.size(); и  
      sizeof(vec) / sizeof(vec[0]); не работят. Програмата те пита за брой ключове за даден тест, въвеждаш ключовете, после въвеждаш и отговорите, които са били дадени, и програмата ги сравнява и в зависимост от това колко верни отговори имаш ти дава точки. Ключовете и дадените отговори са тип char. ("A", "B", "C" etc.)
      Ето го и кода, като повечето съм го направил на коментар за да си тествам само функцията която извежда броя на елементите.
      #include "stdafx.h" #include <iostream> #include <vector> #define CONSOLE_LOG(x) std::cout << x; std::vector<char> keys = {'A', 'B', 'C', 'D', 'E'}; std::vector<char> studentAnswers; int n, points = 0; char key, answer; template <typename T> T vecSize(std::vector<T>& vec) { T size = vec.size(); return size; } /* template <typename T1> void enterKeys(std::vector<T1>& k) { CONSOLE_LOG("Please enter the number of keys: "); std::cin >> n; for (int i = 0, counter = 1; i < n, counter <= n; i++, counter++) { CONSOLE_LOG("Key " << counter << ": "); std::cin >> key; k.emplace_back(key); } } template <typename T2> void enterAnswers(std::vector<T2>& stAns) { for (int i = 0, counter = 1; i < n, counter <= n; i++, counter++) { CONSOLE_LOG("Answer " << counter << ": "); std::cin >> answer; stAns.emplace_back(answer); } } template <typename T3> void getGrade(std::vector<T3>& x, std::vector<T3>& y) { for (int i = 0; i < n; i++) { if (x[i] == y[i]) { points++; } } CONSOLE_LOG("Points: " << points); } */ int main() { /* enterKeys(keys); enterAnswers(studentAnswers); getGrade(studentAnswers, keys); */ std::cout << keys.size() << std::endl; std::cout << vecSize(keys) << std::endl; std::cin.get(); std::cin.get(); std::cin.get(); return 0; } Опитах всевъзможни начини, и пак не става. Идеята е да заместя n променливата със броя на елементите от вектора. Програмата върви по един и същи начин, защото все пак в n променливата запазваме големината на вектора, но бих искал да си го направя с функция.
      Както виждате на края на програмата си извеждам тестове. Първият, който си е по конвенционалният метод си работи сам по себе си, но пък във for цикъл не бачка.
      А вторият е функцията която съм направил. Проблемът е че ми извежда непознат символ - "�"
      Проблемът е че типът на елементите във вектора е char, защото като го направих с int тип си работеше както трябва.
      Бих бил изключително благодарен ако някой може да ме насочи и да ми бутне едно рамо :)
    • от Goshko
      Да се напише програма, която създава структура "Book" като имате следните полета - Title(заглавието на книгата), Автор(Author), Цена(Price) и уникален номер на книгата(ISBN-num). Да се ваведе цяло число n и след него n на брой данни за ученика. Да се изведе на монитора данните за книгата с цена по-висока от предварително зададена.
    • от Нели Николова
      Здравейте, имам две готови задачи, но не мога да ги компилирам. Дали може да ги проверите?
      зад.1 Да се състави програма, която да сортира едномерен масив от цели числа тип short  с име X състоящ се от 19 елемента. Сортирането да се извърши във възходящ ред чрез метода пряка селекция.
      #include <iostream>
      using namespace std;
      void sortAsc(short[]);
      int main() {
          short x[] = {123,13,23,31,1,55,36,17,8,9,10,11,6,12,14,15,16,35,184,19};
           
          sortAsc(x);
          
          return 0;
      }
      void sortAsc(short x[]){
          for(short i = 0; i < 19 ; i++) {
              for(short j = i; j < 19; j++) {
                  if(x[j] < x) {
                      swap(x[j], x);
                  }
              }    
          }
          
          for(int i=0; i<19; i++)
          {
              cout << x << endl;
          }
      }
      зад. 2 Да се състави програма,която реализира динамичен стек от реални числа тип float. Стекът да се преобразува в два нови стека, един стек P за четните и един стек O за нечетните числа от стек едно. Стековете да се извеждат на екрана.
      int main() {
          stack<float>numbers;
          stack<float>p;
          stack<float>o;
          
          for(short i = 1; i <= 200; i++) {
              numbers.push(i);
          }  
          
          numbers.push(200.64);
          numbers.push(203.34);
          
          while(!numbers.empty()) {
              int number = numbers.top();
              
              if (number % 2 == 0) {
                  p.push(number);
              } else {
                  o.push(number);
              }
              numbers.pop();
          }
          
          cout << "EVEN NUMBERS:" << endl;
          
          while(!p.empty()) {
              cout << p.top() << endl;
              p.pop();
          }
          
          cout << "ODD NUMBERS:" << endl;
          
          while(!o.empty()) {
              cout << o.top() << endl;
              o.pop();
          }
          
      }
      Много Ви благодаря :)
       
    • от Georgi Kirchev
      Здравейте имам да предам курсова работа утре ,но не мога да я реша , ще бъда изключително благодарен ако може някой да ми помогне.

      Дефинирайте клас Телевизор, който да е родител на клас Самсунг и клас Сони. Клас Телевизор да има цена и брой продадени за година в сектор private. Класовете Самсунг и Сони да имат в сектор public функции за определяне на общата сума от продажби за година (цена * брой продадени за година). Всички класове да имат конструктори по подразбиране.
       
      Благодаря предварително !
  • Дарение

×

Информация

Поставихме бисквитки на устройството ви за най-добро потребителско изживяване. Можете да промените настройките си за бисквитки, или в противен случай приемаме, че сте съгласни с нашите условия за ползване.