Петя
Булочкин твердо решил стать программистом и найти работу. Он целыми днями
ходил по разным компьютерным фирмам, но везде ему отказывали. Наконец,
фирма «NoBugs» согласилась принять его на
работу, но только если он сдаст экзамен.
Экзамен
состоял в следующем: Пете дали программу, которая по введенным числу N (1<=N<=1000000) и числам Ai (1<=Ai<=N, все Ai – различные) выводит
на экран некоторое количество звездочек T. Задача Пети заключалась в том,
чтобы определить, сколько звездочек выводит данная программа. Чтобы
проверить, справился ли он с экзаменом, ему было предложено 10 тестовых
примеров. Петя должен был дать ответы на них, причем, как сказало ему
руководство фирмы, не важно, каким способом он их получит.
Программа
выглядела следующим образом:
{язык
программирования Pascal}
var
A: Array[0..1000000] of
LongInt;
i, j, n, s:
LongInt;
begin
A[0]:=
0;
ReadLn(n);
For i:= 1 to n
do
ReadLn(A[i]);
For i:= 1 to n do
begin
j:=
i;
While
(j>1) and (A[j] < A[j-1]) do begin
Write(‘*’);
s:= A[j]; A[j]:= A[j-1]; A[j-1]:= s;
j:=
j-1;
end;
end;
end.
//
язык программирования C++
#include
<iostream.h>
int
main()
{
long *A;
A = newlong [1000001]; //
определяется массив A, индексы от 0 до 1000000
long n, i, j,
s;
A[0] = 0;
cin >>
n;
for (i=1; i<=n; i++) {cin
>> A[i];}
for (i=1; i<=n;
i++)
{
j =
i;
while ((j>1)
&& (A[j] < A[j-1]))
{
cout
<< “*”;
s = A[j];
A[j] = A[j-1]; A[j-1] = s;
j--;
}
}
delete [ ]
A;
}
За
помощью Петя, естественно, обратился к вам.
Итак, даны 10 входных файлов
(формат см. ниже). Каждый из файлов содержит набор чисел, которые вводятся
в программу с клавиатуры. Вам необходимо сформировать 10 выходных файлов,
каждый из которых будет содержать одно число – количество звездочек,
которые напечатает программа на соответствующих входных данных. Программу
в этой задаче сдавать не нужно, нужно сдать только выходные
файлы. Выходным файлом для файла InputK.Txt (1 <= K <= 10)
должен быть файл OutputK.Txt.
Ввод. Первая строка входного
файла содержит число N. Следующие N строк содержат числа A1, A2, …, ANпо одному в строке.