VIII Всеукраинская олимпиада по информатике

1 тур, 25 марта 1995 года

Задание 1

Задано множество из N натуральных чисел a[1], a[2], ...,a[N]. Найти множество различных номеров b[1], b[2], ..., b[K] (1 <= K <= N) такое, чтобы число a[b[1]] + a[b2]] + ... + a[bK]] делилось без остатка на N.

Технические условия

1. Имена файлов программы, входных и выходных данных:

SEQUENCE.???, SEQUENCE.DAT, SEQUENCE.SOL, где ??? - PAS, BAS, C, CPP

(в зависимости от языка программирования).

2. Первая строка входного файла содержит количество тестов. Первая строка каждого теста содержит количество чисел N ( 1 <= N <= 45 ). Последующие N строк содержат натуральные числа a[1], a[2], ..., a[N]. Гарантируется, что их сумма не выходит за пределы стандартных целочисленных типов.

3. Корректность входных данных гарантируется.

4. В выходной файл для каждого теста в одну строку вывести множество номеров b[1], ..., b[K], отделив их пробелами, либо сообщения "No solution".

Пример входного и выходного файлов

Входной (SEQUENCE.DAT):

2

1

1

3

1

2

3

Выходной (SEQUENCE.SOL):

1

1 2 3

Задание 2

Написать программу для поиска такой строки из 75 символов, каждый из которых может принимать значения "A", "B" либо "C", чтобы никакие ее две соседние подстроки не совпадали. Например, в строке из 7 символов "ABACBAB" нет соседних одинаковых подстрок, а в строках "ABAACAB", "CABABCA", "CABCABA", "BACBCBBA" есть.

Технические условия

1. Имена файлов программы и выходных данных: ABC.???, ABC.SOL, где ??? - PAS, BAS, C, CPP (в зависимости от языка программирования).

2. В выходной файл вывести решение задачи либо сообщение "No solution", если такой строки не существует.

Задание 3

По заданным натуральным числам

P (0 < P < 10000) и N (0 < N < 1000) вычислить значения (корня квадратного из числа P) з N точными цифрами после запятой.

Технические условия

1. Имена файлов программы, входных и выходных данных: SQROOT.???, SQROOT.DAT, SQROOT.SOL, где ??? - PAS,BAS,C,CPP (в зависимости от языка программирования).

2. Первая строка входного файла содержит количество тестов m,n наборов тестовых данных, каждый из которых состоит из двух строк, содержащих числа P и N соответственно.

3. Корректность входных данных гарантируется.

4. В выходной файл вывести решения всех тестов, по одному в строку. Числа должны быть представлены в виде десятичных дробей.

Пример входного и выходного файлов

Входной (SQROOT.DAT):

3

2

5

10

10

100

30

Выходной (SQROOT.SOL):

1.41421

3.1622776601

10.0000000000000000000000000000000000

2 туp, 26 марта 1995 года.

Задание 1.

Изделие состоит из N деталей. Имеется N станков, на каждом из которых можно изготовить любую деталь. Для каждых станка и деталей известно время t[i,k] изготовления k-й детали на i-м станке. Напишите программу, определяющую, на каком станке следует изготовить каждую деталь, чтобы одновременно начав изготовлять все детали, завершить изготовления всех деталей как можно раньше.

Технические условия.

1) Имена файлов программы, входных и выходных данных: DETAILS.???, DETAILS.DAT, DETAILS.SOL, где ??? - PAS, BAS, C, CPP (в зависимости от языка программирования).

2) Первая строка входного файла содержит количество тестов. Первая строка каждого теста содержит количество станков и деталей N (1<=N<=50). Каждая из последующих N строк содержит длительности изготовления деталей на соответствующем станке t[i,1], t[i,2],...,t[i,N], разделенные запятыми. Каждое из этих чисел натуральное и не превосходит 100.

3) Корректность входных данных гарантируется.

4) В выходной файл для каждого теста нужно последовательно вывести в одну строку. Номера деталей, которые надо изготовить соответственно на 1-м, 2-м,..., N-м станках, разделив их пробелами. В следующую строку необходимо вывести время от начала до завершения изготовления всех деталей.

5) Для каждого теста достаточно найти одно решение.

Пример входного и выходного файлов

Входной (DETAILS.DAT):

2

2

3,2

1,2

3

3,3,3

3,3,3

3,3,3

Выходной (DETAILS.SOL):

2 1

2

1 2 3