VIII Всеукраїнська олімпіада з інформатикиПерший тур25 березня 1995 року Завдання 1 Задано множину з N натуральних чисел a[1], a[2], ...,a[N]. Знай ти множину рiзних номерiв b[1], b[2], ..., b[K] (1 <= K <= N) таку, щоб число a[b[1]] + a[b2]] + ... + a[bK]] дiлилось без остачi на N.Технiчнi умови 1. Iмена файлiв програми, вхiдних та вихiдних даних: SEQUENCE.???, SEQUENCE.DAT, SEQUENCE.SOL, де ??? - PAS, BAS, C, CPP (в залежностi вiд мови програмування).2. Перший рядок вхiдного файлу мiстить кiлькiсть тестiв. Перший рядок кожного тесту мiстить кiлькiсть чисел N ( 1 <= N <= 45 ). Наступнi N рядкiв мiстять натуральнi числа a[1], a[2], ..., a[N]. Гарантовано, що їх сума не виходить за межi стандартних цiлочисельних типiв. 3. Коректнiсть вхiдних даних гарантується. 4. У вихiдний файл для кожного тесту в один рядок вивести множи ну номерiв b[1], ..., b[K], вiдокремивши їх пропусками, або повiдом- леннями "No solution". Приклад вхiдного та вихiдного файлiв
Вхiдний (SEQUENCE.DAT):
2
1
1
3
1
2
3
Вихідний (SEQUENCE.SOL):
1
1 2 3
Завдання 2 Написати програму для знаходження такого рядка з 75 символiв, кожен з яких може набувати значення "A", "B" або "C", щоб нiякi його два сусiднi пiдрядка не спiвпадали. Наприклад, в рядку з 7 символiв "ABACBAB" не має сусiднiх однакових пiдрядкiв, а в рядках "ABAACAB", "CABABCA", "CABCABA", "BACBCBBA" є.Технiчнi умови 1. Iмена файлiв програми та вихiдних даних: ABC.???, ABC.SOL, де ??? - PAS, BAS, C, CPP (в залежностi вiд мови програмування).2. У вихiднiй файл вивести розв'язок задачi або повiдомлення "No solution", якщо такого рядка не iснує. Завдання 3 За заданими натуральними числами P (0 < P < 10000) та N (0 < N < 1000) обчислити значення P (кореня квадратного з числа P) з N точними циф- рами пiчля коми.Технiчнi умови 1. Iмена файлiв програми, вхiдних та вихiдних даних: SQROOT.???, SQROOT.DAT, SQROOT.SOL, де ??? - PAS,BAS,C,CPP (в залежностi вiд мови програмування).2. Перший рядок вхiдного файлу мiстить кiлькiсть тестiв m,n на- борiв тестових даних, кожен з яких складається з двох рядкiв, якi мiстять числа P та N вiдповiдно. 3. Коректнiсть вхiдних даних гарантується. 4. У вихiдний файл вивести розв'язки всiх тестiв, по одному в рядок. Числа повиннi бути наданi у виглядi десяткових дробiв. Приклад вхiдного та вихiдного файлiв
Вхiдний (SQROOT.DAT):
3
2
5
10
10
100
30
Вихiдний (SQROOT.SOL):
1.41421
3.1622776601
10.0000000000000000000000000000000000
Другий тур 26 березня 1995 року Завдання 1 Вибiр складається з N деталей. Є N верстатiв, на кожному з яких можна виготовити будь-яку деталь. Для кожних верстату та деталей вiдомий час t[i,k] виготовлення k-ї деталi на i-му верстатi. Напишiть програму, яка визначить, на якому верстатi слiд виготовити кожну де- таль, щоб одночасно почавши виготовляти всi деталi, завершити виго- товлення всмх деталей якнайшвидше.Технiчнi умови 1) Iмена файлiв програми, вхiдних та вихiдних даних: DETAILS.???, DETAILS.DAT, DETAILS.SOL, де ??? - PAS, BAS, C, CPP (в залежностi вiд мови програмування).2) Перший рядок вхiдного файлу мiстить кiлькiсть текстiв. Перший рядок кожного тексту мiстить кiлькiсть верстатiв та деталей N(1<=N<=50). Кожен з наступних N рядкiв мiстить тривалостi виготов- лення деталей на вiдповiдному верстатi t[i,1], t[i,2],...,t[i,N], вiдокремленi комами. Кожне з цих чисел натуральне i не перевершує 100. 3) Коректнiсть вхiдних даних гарантується. 4) У вихiдний файл для кожного тесту треба послiдовно вивести в один рядок. Номери деталей, якi треба виготовити вiдповiдно на 1-му, 2-му,..., N-му верстатах, вiдокремивши їх пропусками. В наступний ря- док треба вивести час вiд початку до завершення виготовлення всiх де- талей. 5) Для кожного тесту досить знайти один розв`язок. Приклад вхiдного та вихiдного файлiв
Вхiдний(DETAILS.DAT):
2
2
3,2
1,2
3
3,3,3
3,3,3
3,3,3
Вихiдний (DETAILS.SOL):
2 1
2
1 2 3
|
Повний архів олімпіади (142 Kb)
© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"