Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #define KONJ 42 - 42
- #define INF 105
- using namespace std;
- int N, len;
- char s[150];
- int niz[150];
- short memo[110][1000010];
- bool visited[110][1000010];
- int solve( int curr, int val ){
- int ret = 0;
- if ( curr == len ){ return INF; }
- if ( val == 0 ){ visited[curr][val] = true; return memo[curr][val] = 0; }
- if ( visited[curr][val] ){ return memo[curr][val]; }
- visited[curr][val] = true;
- ret = min( solve( curr + 1, val ), 1 + solve( curr + 1, ( val + niz[ curr + 1 ] ) % N ) );
- return memo[curr][val] = ret;
- }
- int main( void ){
- scanf( "%s", s ); len = strlen( s );
- scanf( "%d", &N );
- int ostatak = 0;
- for ( int i = len - 1; i >= 0; --i ){
- if ( i == len - 1 ){ niz[i] = 1 % N; } else { niz[i] = niz[i + 1] * 2; niz[i] %= N; }
- if ( s[i] == '1' ){ ostatak += niz[i]; ostatak %= N; }
- // printf( "%d %c %d %d\n", ostatak, s[i], niz[i], i );
- }
- for ( int i = 0; i < len - 1; ++i ){
- if ( s[i] == '1' ){ niz[i] = N - niz[i]; }
- }
- //printf( "%d\n", ostatak );
- printf( "%d\n", solve( 0, ostatak ) );
- return KONJ;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement