41 Востаннє редагувалося Arete (30.05.2018 07:27:27)

Re: Класика студіка

0 - Зеник не стає на сходинку, 1 - стає. При n сходинок кількість всіх варіантів проходу по них 2^n, але оскільки на останню ходинку він повинен стати то кількість можливих варіантів зменшується вдвічі: 2^(n-1).  Кількість варіантів проходу сходинок за правилом можна розраховувати як кількість всіх варіантів мінус кількість невірних варіантів: 2^(n-1) - .....
Приклад для 6 сходинок:

100000
100001
100010
100011
100100
100101
100110
100111
101000
101001
101010
101011
101100
101101
101110
101111
110000
110001
110010
110011
110100
110101
110110
110111
111000
111001
111010
111011
111100
111101
111110
111111

Нехай m - кількість вірних варінтів, w - кількість невірних варіантів. Тоді для 6 сходинок значення будуть такі:

k = 6, m = 32, w =  0
k = 5, m = 31, w =  1, рядки: 1
k = 4, m = 29, w =  3, рядки: 1,2,17
k = 3, m = 24, w =  8, рядки: 1,2,3,4,9,17,18,25
k = 2, m = 13, w = 19, рядки: 1,2,3,4,5,6,7,8,9,10,13,17,18,19,20,21,25,26,29
k = 1, m =  1, w = 31, рядки: всі крім останнього

Послідовність кількості невірних варіантів w при зменшенні k від n до 0 завжди однакова при будь-якому n: 0, 1, 3, 8, 19, ..., n-1. Достатньо знайти таку функцію f(n,k) яка повертає вірне w і задача буде розв'язана. Але я поки що не знайшов закономірність.

42

Re: Класика студіка

#include <iostream>
#include <cmath>
#include <cstdlib>

int getWrongMoves(int n, int k)
{
    int result = 1;
    for (int i = 1; i < n - k; ++i)
    {
        result = 2 * result + i;
    }
    return  result;
}

int main(int argc, char *argv[])
{
    int n = 0;
    int k = 0;

    if (argc > 2)
    {
        n = atoi(argv[1]);
        k = atoi(argv[2])+1;
    }
    if (n < 1 || n > 100)
    {
        std::cout << "Usage: zenik <N>, <K>\n"
                  " where 1 <= N, K <= 100" << std::endl;
        return 0;
    }

    double allMoves = std::pow(2, n-1);
    double wrongMoves = 0;

    if (k == 1)
    {
        wrongMoves = allMoves - 1;
    }
    else if (k >= n)
    {
        wrongMoves = 0;
    }
    else
    {
        wrongMoves = getWrongMoves(n, k);
    }

    std::cout << "all moves: " << allMoves <<  std::endl;
    std::cout << "wrong moves: " << wrongMoves <<  std::endl;
    std::cout << "corect moves: " << allMoves - wrongMoves <<  std::endl;

    return 0;
}

43

Re: Класика студіка

Щось не дуже працює. Контроль (Python, наївна неоптимізована рекурсія): https://ideone.com/bZ3CsZ
recursion_zenik(5,2) => 14 (список додається)
Ваш код: https://ideone.com/w2rkTA => 8.

Подякували: Arete1

44

Re: Класика студіка

При zenik 5 2 мій код дає результат:

all moves: 16
wrong moves: 3
corect moves: 13

І це схоже вірний результат, бо існує 3 невірних варіанти:

10000 - зразу на останню сходинку, пропустили 4 сходинки
10001 - з першої на останню сходинку, пропустили 3 сходинки
11000 - зразу на передостанню, пропустили 3 сходинки

P.S. але якщо враховувати що всі сходинки можна пройти за 1 крок то варіант 10000 буде вірним..

45

Re: Класика студіка

Ось більш зручний варіант для Arete: https://ideone.com/ujiPtf

Подякували: Arete1

46

Re: Класика студіка

koala написав:

Ось більш зручний варіант для Arete: https://ideone.com/ujiPtf

Дякую, а мій варіант коду вище виявився неправильним :)

47

Re: Класика студіка

Написав свій варіант. На жаль, у 2 секунди Пайтон не вкладається навіть на сервері, але очевидно, що будь-яка ближча до заліза мова (навіть Java) має вкластися:
https://ideone.com/KmIuFW
Головне - 128-бітні змінні одразу ставити.

Втім, майже очевидно, що має бути краще рішення, ніж оце, впритул по часу. Інакше час би збільшили.

48 Востаннє редагувалося Q-bart (01.06.2018 15:28:18)

Re: Класика студіка

Я маю код на плюсах, який пройшов всі тести

Прихований текст
#include<iostream>
#include<vector>

using namespace std;

const long ost = 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 + 7;
int n, k;

long long Min(long long a, long long b)
{
 if (a < b)
  return a;
 else
  return b;
}

long long Max(long long a, long long b)
{
 if (a > b)
  return a;
 else
  return b;
}

long long memo[101][101][101];

long long go(int size, long long min, long long max)
{
 if (max - min > k)
  return 0;
 long long x = 0;
 if (size != n)
  if (memo[size][min][max] != -1)
   return memo[size][min][max];
 for (int i = 1; i <= n; i++)
 {
  if (size - i >= 0 && max - min <= k)
   x += go(size - i, Min(min, i), Max(max, i)) % ost;
  if (max - min > k)
   return 0;
  if (size == 0 && max - min <= k)
   return 1;
 }
 if (size != n)
  memo[size][min][max] = x;
 return x;
}

int main() {
 cin >> n;
 cin >> k;
 for (int i = 0; i < 101; i++)
  for (int j = 0; j < 101; j++)
   for (int k = 0; k < 101; k++)
    memo[i][j][k] = -1;
 cout << go(n, 10000, 0);
 //system("pause");
 return 0;

Здається тут те саме рішення

49

Re: Класика студіка

А що це за ost такий?

50

Re: Класика студіка

Ідея з матрицею та сама, а от рекурсія чомусь швидша за мої цикли.

51

Re: Класика студіка

Цього сказати не можу, тому що код не мій. Це типу студіки між собою вже мають кілька шарів робочих кодів, щоб здавати. А я ось вирішив прошаритись. Одну написав, а ця не йде

Прихований текст

Ну я після повідомлення на форумі толком не сідав за ню)

52

Re: Класика студіка

Переписав на Python - воно лише удвічі швидше за моє, а я не дуже стежив за межами, цілком можливо, що прихопив щось зайве. Причому досить неоптимізоване:

long long go(int size, long long min, long long max)//min, max можуть бути int-ами
{
 if (max - min > k)
  return 0;
 long long x = 0;
 if (size != n)
  if (memo[size][min][max] != -1)
   return memo[size][min][max];
 for (int i = 1; i <= n; i++)
 {
  if (size - i >= 0 && max - min <= k)//ми вже перевіряли max-min, а size-i>=0 можна внести в умову циклу
   x += go(size - i, Min(min, i), Max(max, i)) % ost;
  if (max - min > k)//це ніколи не виконається
   return 0;
  if (size == 0 && max - min <= k)//це можна винести на початок
   return 1;
 }
 if (size != n)
  memo[size][min][max] = x;
 return x;
}

Отже, разом буде

long long go(const int size, const int min, const int max)
{
 if (max - min > k)
  return 0;
 if (size != n && memo[size][min][max] != -1)
   return memo[size][min][max];
 if (size == 0)
  return 1;
 long long x = 0;
 for (int i = 1; i <= size; i++)
 {
   x += go(size - i, Min(min, i), Max(max, i)) % ost;
 }
 if (size != n)
  memo[size][min][max] = x;
 return x;
}

І що таке в біса те ost?

53

Re: Класика студіка

Переписав свій код на плюсах: https://ideone.com/xPWktF - точно така ж швидкість. Якщо, звісно, я правильно зрозумів, що таке ost, бо ви все мовчите.

54

Re: Класика студіка

koala написав:

Переписав свій код на плюсах: https://ideone.com/xPWktF - точно така ж швидкість. Якщо, звісно, я правильно зрозумів, що таке ost, бо ви все мовчите.

та я ж кажу, що не знаю: "Цього сказати не можу, тому що код не мій"

55 Востаннє редагувалося Q-bart (02.06.2018 12:02:49)

Re: Класика студіка

О, курва. Я зрозумів:
остача

Оскiльки вiдповiдь може бути дуже великою, виведiть її замодулем 10^9 + 7(остачу вiд дiлення на 10 ^ 9+ 7).

56

Re: Класика студіка

Що це ви процитували?

57 Востаннє редагувалося Q-bart (02.06.2018 12:34:23)

Re: Класика студіка

koala написав:

Що це ви процитували?

Це зі завдання
http://i.imgur.com/ZusMhHk.png

58

Re: Класика студіка

Тобто ви хочете сказати, що у вас увесь час було повне завдання, але викласти ви його вирішили лише у 57 повідомленні в темі, присвяченій задачі?
Більше так не робіть.

59

Re: Класика студіка

Тобто? Я ж спеціально переписав, щоб не фоточкою)) Не буду більше

60

Re: Класика студіка

Про остачу ви не писали. До речі, ваш плюсний код не має проходити контроль, він при (100,100) видає 3 з чимось мільярди.

Подякували: leofun011