Другие языки программирования и технологии
Вам даны все целые числа от 1 до N + 1, кроме одного. Найдите отсутствующее число.
В первой строке входных данных записано целое число 1 <= N <= 100,000. Во второй строке через пробел даны N целых чисел в диапазоне от 1 до N + 1.
т к число <2^17 то можно определить число по остатку от деления на 2^17
то есть достаточно получить последние 17 бит а если n< 65536 то и 16
то есть достаточно чтобы компилятор создавал код не проверяющий переполнение
то есть достаточно получить последние 17 бит а если n< 65536 то и 16
то есть достаточно чтобы компилятор создавал код не проверяющий переполнение
Загнать исходный файл в список, отсортировать его, выполнить поиск тупым перебором.
Если числа по-порядку то:
for i:=1 to 100000 do
begin
read(file,x);
if x > i then
begin
writeln(i);
break;
end;
end;
for i:=1 to 100000 do
begin
read(file,x);
if x > i then
begin
writeln(i);
break;
end;
end;
Олег Сысоев
спасибо вам!!!
Цикл от 1 до N+1, ищем по очереди каждое в полученном списке. То которое не находим - искомое.
Олег Сысоев
Спасибо вам!!!
Если числа НЕ по-порядку, то предлагаю идею: числа от 1 до N + 1 - арифметическая прогрессия с шагом 1. Мы можем по простой формуле вычислить её сумму. Мы так же можем вычислить сумму всех чисел в файле (просто читаем по порядку и складываем). Так как в файле не хватает ОДНОГО числа, то сумма чисел в файле будем меньше суммы арифметической прогрессии ровно на это самое число (которое отсутствует в файле и которое нужно найти). Так как по условию задачи N <= 100000, максимальная сумма арифметической прогрессии составит 5 000 200 002. Это не помещается в 4 байта, поэтому используйте 8 байтовое целые числа.
read(N);
sum := 0;
S := (1 + (N + 1)) / 2 * (N + 1); {вычисляем сумму чисел от 1 до N + 1 включительно}
{читаем и складываем числа из файла}
for i:=1 to N do
begin
read(file,x);
sum := sum + x;
end;
{выводим искомое число как разность сумм}
writeln(S - sum);
read(N);
sum := 0;
S := (1 + (N + 1)) / 2 * (N + 1); {вычисляем сумму чисел от 1 до N + 1 включительно}
{читаем и складываем числа из файла}
for i:=1 to N do
begin
read(file,x);
sum := sum + x;
end;
{выводим искомое число как разность сумм}
writeln(S - sum);
Ххх Virt Для Девочек
Кстати, можно сделать так: не вычислять сумму от 1 до N + 1 сразу, потому что можно неявно вычислить её в цикле во время чтения. Это затратит больше арифметических операций, зато не нужно париться с 64-битным целым числом
read(N);
sum := 0;
for i:=1 to N do
begin
read(file,x);
sum := sum + i - x;
end;
writeln(sum + N + 1);
read(N);
sum := 0;
for i:=1 to N do
begin
read(file,x);
sum := sum + i - x;
end;
writeln(sum + N + 1);
Олег Сысоев
Спасибо вам большое!!!

Похожие вопросы
- Дан файл целых чисел. Создать два новых файла, первый из которых содержит положительные числа из исходного файла...
- помогите? Дан массив целых чисел (n=15),
- Вывести все числа от 1 до N, являющиеся палидромами
- Найти сумму квадратов всех чисел от 1 до n .
- дан массив целых чисел F1,F2...Fn. распечатать элементы, нах-ся между min и max и их номера. подскажите где я ошибся
- Дано натуральное число n. Найти и вывести все числа в интервале от 1 до n -1, у которых произведение всех цифр совпадает
- Даны 3 целых числа найти среднее язык #C
- Составить программу С++ В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число
- Даны 3 целых числа. Возвести в квадрат отрицательные числа и в третью степень - положительные (число 0 не изменять)
- Дан файл целых чисел.Найти сумму компонент с четным значением и записать в новый файл те из них,значения которых превыша