The River II от Codingame

Yoan26 0 Точки

The River II от Codingame

Здравейте, упражнявах се докато чакам седващата лекция със задачата The River II от Codingame (https://www.codingame.com/ide/puzzle/the-river-ii-).

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

Това е кода ми

https://pastebin.com/qP35UGKV

ще се радвам ако някой сподели как мога да го оптимизирам.

Поздрaви и приятен уикенд !

П.С. Първоначално проверката в цикъла ми беше от 1 до числото, но така бе дори по-бавно при по-големи числа (напр 91004 - гърмят 3 теста) , затова смених проверката да е от числото до 1, въпреки това 2 теста гърмят за време.

Тагове:

03/04/2021 16:43:02 C++ Fundamentals

MartinBG 4803 Точки

Може и да пропускам нещо, но не виждам защо трябва да тестват всички възможноси от 1 до числото r1 (или обратното). Достатъчно е да се тестват числта от (r1 - 9 * (r1 digits)) до (r1 - 1) и при първото съвпадение да се върне "YES".

С тази промяна минават всички тестове (не претендирам решението да е коректно - все пак е 3 часа след полунощ ):

bool checkIfMettsRiver(int r) {
  int digits = 1;
  int temp = r;
  while ((temp /= 10) > 0) {
    digits++;
  }

  int end = r - 9 * (digits);

  for (int i = r - 1; i >= end; --i) {
    if(nextNum(i) == r) return true;
  }

  return false;
}

04/04/2021 03:08:19

j.petrov_90 373 Точки

Привет, Йоан,

Не съм разглеждал задачата в детайли, но определено while-while подходът не изглежда оптимален.
Ти си изчерпал всички възможни варианти, което също е известно като brute force.
Решението ти сигурно е вярно, но както си разбрал не оптимално.

Както голегата MartinBG ти е помогнал, ключът към решението на тази задача (а и на всички "алгоритмичти" задачи) се крие в това да се сетиш как с по-малко итерации да достигнеш до правилния отговор.

04/04/2021 12:01:12

Yoan26 0 Точки

Благодаря!!

17/04/2021 18:56:21