CompetitiveProgramming/codeforces/100876/A.cpp at master · phonglnDEV/CompetitiveProgramming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;

string s;
int k, len, flag;

int getSum(int i, int mask)
{
  int res = s[i] - '0';
  if (mask >> i & 1)
    res--;
  if (i && mask >> (i - 1) & 1)
    res += 10;
  if (!i && flag)
    res += 10;
  return res;
}

int solve(int mask)
{
  int d[22];
  memset(d, -1, sizeof d);

  for (int i = 0; i < len; i++)
    if (d[i] < 0)
    {
      int isGood = 0;
      for (d[i] = (i == 0); d[i] <= getSum(i, mask); d[i]++)
      {
        int ok = 1, last = i;
        while (1)
        {
          int cur = (last + k) % len;
          if (cur == i)
          {
            ok = d[cur] + d[last] == getSum(last, mask);
            break;
          }

          d[cur] = getSum(last, mask) - d[last];
          if (d[cur] < 0 || d[cur] > 9)
          {
            ok = 0;
            break;
          }

          last = cur;
        }

        if (ok)
        {
          isGood = 1;
          break;
        }
      }

      if (!isGood)
        return 0;
    }

  int start = 0;
  for (int i = 0; i < len; i++)
    if (start || d[i])
    {
      cout << d[i];
      start |= d[i] > 0;
    }
  return 1;
}

int main()
{
  freopen("coding.in", "r", stdin);
  freopen("coding.out", "w", stdout);

  cin >> s >> k;
  len = s.size();

  for (int mask = 0; mask < 1 << (len - 1); mask++)
    if (solve(mask))
      return 0;

  if (s[0] == '1')
  {
    flag = 1;
    s = s.substr(1);
    len--;
    for (int mask = 0; mask < 1 << (len - 1); mask++)
    if (solve(mask))
      return 0;
  }
}