Решение задачи " inc ARG" с Codeforces

С пояснением   Просмотров: 49


Сергей тестирует процессор нового поколения. Вместо байтов процессор работает с ячейками памяти, состоящими из n битов, пронумерованных от 1 до n. Число хранится в ячейке памяти следующим образом: младший бит числа хранится в первом бите ячейки, следующий бит числа — во второй ячейке, и так далее; старший бит числа хранится в n-й ячейке.

Сейчас Сергей хочет протестировать инструкцию «прибавить 1 к значению ячейки». В результате инструкции число, двоичное представление которого записано в ячейке, должно увеличиться на единицу; при этом, если некоторые старшие разряды числа не помещаются в ячейку, их необходимо отбросить.

Сергей записал определенные значения битов в ячейку и собирается прибавить к ее значению 1. Сколько битов ячейки поменяются в результате этой операции?

Код

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
	string s;
	cin>>s;
	int i;
	for(i=0;i<n && s[i]=='1';i++);
	if(i==n)
        cout<<n;
	else
        cout<<i+1;
}

         

 Администратор Photo Автор: Администратор


Если прибавить к числу 1, его двоичная запись поведет себя понятным образом: все младшие единицы превратятся в нули, а следующий за ними ноль станет единицей. Найдем длину максимального суффикса из единиц, пусть она равна l. Тогда ответ равен l + 1, кроме случая, когда вся строка состоит из единиц, тогда ответ l.

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться