oj.uz

Submission #667955

# Submission time Handle Problem Language Result Execution time Memory
667955 2022-12-02T12:12:40 Z 600Mihnea Board (CEOI13_board) C++17
40 / 100
 3 ms 1492 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll nxt(ll a, char ch)
{
  if (ch == '1') return 2 * a;
  if (ch == '2') return 2 * a + 1;
  if (ch == 'U') return a / 2;
  if (ch == 'L') return a - 1;
  if (ch == 'R') return a + 1;
  assert(0);

}

ll nxt(ll a, string s)
{
  for (auto &ch : s)
  {
    a = nxt(a, ch);
  }
  return a;
}

int get_level(ll x)
{
  if (x == 1)
  {
    return 1;
  }
  else
  {
    assert(x >= 2);
    return 1 + get_level(x / 2);
  }
}

ll solve(ll a, ll b)
{
  if (a == b)
  {
    return 0;
  }
  if (get_level(b) > get_level(a))
  {
    return 1 + solve(a, b / 2);
  }
  if (get_level(a) > get_level(b))
  {
    return 1 + solve(a / 2, b);
  }
  assert(get_level(a) == get_level(b));
  return min(abs(a - b), 2 + solve(a / 2, b / 2));
}

int main()
{
#ifdef ONPC
  freopen ("input.txt", "r", stdin);
#endif // ONPC

#ifndef ONPC
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC

  string s, t;
  cin >> s >> t;
  ll a = nxt(1, s);
  ll b = nxt(1, t);
  cout << solve(a, b) << "\n";

  return 0;
}
/**
**/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 740 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 2 ms 596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 696 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1492 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1368 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1236 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -