Задача Lamps2
Дискусія навколо задачі Lamps породила наступну задачу: Є гірлянда з лампочок, що не перегорають ні при яких умовах і світяться при будь-яких ненульових напругах.
Лампочки цієї моделі мають 2 контакти (1 і 2) та нитку розжарення між ними. Лампочки з'єднані провідниками з нульовим опором. Фізики знають, що в цьому випадку схема не матиме точок з однаковим потенціалом, що не з'єднані провідником напряму. Визначіть, скільки (та які саме) лампочок не світитимуться через помилки монтажу.Гірлянда підключена до мережі 2-ма додатковими провідниками, що під'єднані до перших контактів першої та останньої лампи.
Технічні умови: Ви вводите К (50>= K>=3)-кількість ламп в гірлянді,Т-кількість відрізків провідника,що з'єднують лампи, а далі -Т груп по 4 числа : номер_лампочки, номер_контакту, номер_лампочки, номер_ контакту - для кожного провідника. Всі величини вводяться з клавіатури через пропуск.
Ви виводите на екран кількість лампочок,що не світяться, а потім їх номери в порядку зростання. Якщо помилок в схемі немає, вивести 0.
Приклад:
Введення:
6 7 1 1 2 1 1 2 2 1 2 2 3 1 2 2 4 1 3 2 5 1 4 2 5 1 5 1 6 2
Виведення:
2 1 5
Задача Lamps3
Є достатня кількість лампочок різних типів. Кількість типів лампочок N (2<=N<=10). Для кожного типу відомий опір ламп R1, R2, ..., Rn (1=R1<R2<R3<...<Rn<=5000). З них необхідимо зібрати гірлянду опором R ( 1<=R<=20000) так,щоб при цьому використовувалась мінімальна кількість лампочок. Всі опори - цілі числа. Допускається тільки послідовне підключення лампочок.
Технічні умови:
Ви вводите з клавіатури через пропуск R - опір гірлянди, далі кількість типів лампочок N, далі опори цих лампочок. Ви виводите на екран знайдену мінімальну кількість лампочок в гірлянді,а далі - кількість лампочок кожного типу.
Приклад:
Введення:
17 3 1 3 15
Виведення:
3 2 0 1
Задача Cutting
Маленький хлопчик намалював на листку в клітинку систему координат так, що осі розміщено по лініях клітинок, а масштабна одиниця рівна стороні клітинки. Потім він намалював замкнуту ламану, що проходить по сторонах клітинок. При цьому, малюючи, не звертав уваги на те, скільки разів олівець проходить по одній і тій же лінії.
Далі хлопчик акуратно лезом для гоління зробив розріз по лінії свого малюнку. Скільки клітинок вирізав хлопчик?
Технічні умови:
Ви вводите з клавіатури кількість дільниць ламаної n (1<=n<=1000), потім координати вершин ламаної в порядку обходу ( не більші 50 за абсолютною величиною ). Ви виводите на екран кількість вирізаних клітинок.
Приклад:
Введення:
8 0 0 4 0 4 1 3 1 3 -1 2 -1 2 2 0 2
Виведення:
6
Задача Fire!
Космічна станція складається з однакових кубічних модулів, що утворюють один великий прямокутний паралелепіпед розміром X*Y*Z. При випробуванні на живучість перед стартом її обстрілювали гарматою з різних боків, імітуючи удари метеоритів. Снаряди влучали в центр грані якогось модуля перпендикулярно його поверхні і прошивали станцію наскрізь,не змінюючи своєї траекторії.
Скільки модулів залишились неушкодженими після P пострілів?
Технічні умови:
Ви вводите з клавіатури числа X,Y,Z і Р (1<=X,Y,Z<=1000, 0<=P<=150). Далі P груп по 3 координати x,y,z описують постріли. Нульове значення координати визначає вісь, паралельно якій зроблено постріл, а дві інші - відповідні координати прострелених модулів. Наприклад, якщо X=3, Y=4, Z=5 трійка (1, 0, 3) означає, що пробито модулі (1, 1, 3), (1, 2, 3), (1, 3,3) і (1, 4, 3). Відомо, що "снаряд двічі в одну воронку не падає ", тобто жодна трійка не може повторитися. Всі числа вводяться в одному рядку через пропуск. Ви виводите на екран єдине число – кількість неушкоджених модулів.
Приклад:
Введення:
3 4 5 2 2 2 0 2 0 1
Виведення:
52
Задача Chief
Шеф завжди приділяє всім відвідувачам рівні проміжки часу (наприклад,кожному по п'ять хвилин); щоб попасти на прийом, слід напередодні записатися у секретарки.
При реєстрації відвідувач вказує єдиний інтервал часу,що задається парою [Ai; Bi] (початковий та кінцевий моменти, коли він згоден ЗАХОДИТИ на прийом). Ai і Bi -- цілі числа, що означають кількість інтервалів прийому, що пройшли з початку робочого дня Шефа. Допоможіть секретарці обробляти зібрані записи і складати графік прийому.
Технічні умови:
Ви вводите кількість відвідувачів (2<=N<=50000), далі йдуть N груп, в кожній з яких по два числа Аi і Bi, 0<=Ai<=Bi<=2N. Числа вводяться з клавіатури через пропуск. Ви виводите на екран 1 (якщо встановити графік прийому можливо), або 0 (якщо неможливо). Якщо відповідь позитивна (1) - послідовність чисел-номерів відвідувачів в порядку, як вони потрапляють на прийом. Всі числа виводяться через пропуск. Якщо потрібно, щоб в якийсь момент ніхто не заходив на прийом,слід виводити -1.
Приклади:
Введення:3 1 2 0 1 2 2
Виведення: 1 2 1 3
Введення: 3 1 2 1 2 1 2
Виведення: 0
Введення: 3 1 2 1 2 2 4
Виведення: 1 -1 2 1 3
Г.Кравець, Г.Непомнящий, Ю.Пасіхов, І.Порубльов