ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН’03

22 ноември 2003

ТЕМА ЗА  9–10 КЛАС (ГРУПА B)

Задача B1.  ЧИСЛА

Едно множество с M елемента ще наричаме последователно нарастващо, ако то се състои от M последователни цели числа. Например, следните множества са последователно нарастващи: {2, 1, 3}, {15, 9, 16, 12, 10, 14, 13, 11}, {5, 6, 7}  и {123, 122, 121}. А тези множества НЕ са последователно нарастващи: {1, 1, 3}, {101, 102, 105, 107, 106, 103} и {21, 4, 6, 8, 11}.

Нека е дадено множество от N (2 < N < 100 000) цели числа {а₁, а₂, ..., а_N}, като не е необходимо числата да са различни. Към всяко от тези числа a_i (0 < i < N+1) можем да добавим произволно цяло число b_i, така че новополученото множество от числа {c₁, c₂, ..., c_N} да е последователно нарастващо, където c_i = a_i + b_i. Допълнителното изискване е сумата от абсолютните стойности на числата b_i да е възможно най-малка.

Напишете програма NUMBER.EXE, която намира такива цели числа b₁, b₂, …, b_N, сумата от абсолютните стойности, на които е възможно най-малка и добавянето, на които към съответни елементи на зададено множество, прави множеството последователно нарастващо. Ако задачата има повече от едно решение, изведете кое да е от тях.

Входните данни ще бъдат зададени в текстов файл, който вашата програма ще прочете от стандартния си вход. В първия ред на входния файл ще бъде зададено цялото число N. Вторият ред съдържа числата на даденото множество а₁, а₂, ..., а_N, разделени с по един интервал. Числата ще са по-малки или равни на един милион по абсолютна стойност.

Резултатът трябва да бъде изведен на стандартния изход. Първият ред трябва да съдържа намерената минимална сума от абсолютни стойности на числата b_i, а вторият ред трябва да съдържа числата b₁, b₂, …, b_N, разделени с по един интервал.

ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН’03

22 ноември 2003

ТЕМА ЗА  9–10 КЛАС (ГРУПА B)

Задача B2.  ПЪТУВАНЕ

След дълго и изморително пътуване из света проф. Пенчо Минчев най-накрая се завърнал в своята родна страна. За негова жалост обаче той не пристигнал в родия си град Казанлък, а в Брегово. Той трябвало да избере поредица от влакове и автобуси, която да го доведе до дома му, при това възможно най-бързо (Професорът отдавна мечтаел за уютния си дом). Той вече бил събрал всички сведения за превозните средства, при това те били систематизирани, превозните средства били сортирани по часа на тръгване. Поради големия брой превозни средства, той не можел да направи изчислението на ръка. Ето защо той потърсил вашата помощ – да напишете програма TRAVEL.EXE, която знаейки разписанието на превозните средства, да намери най-бързия път за проф. Пенчо Минчев. Може да се счита, че професорът се прехвърля между превозните средства достатъчно бързо, т.е. ако пристигането на един влак и тръгването на друг (или автобус) съвпадат, той може да се прехвърли (разбира се и когато едното превозно средство пристига преди тръгването на другото).

Входните данни програмата чете от стандартния вход. На първият ред стои броят на градовете N (2 <= N <= 10000) (Пенчо Минчев не случайно е професор; той се е сетил предварително да номерира градовете от 1 до N, като с 1 е номериран Казанлък, а с N – Брегово) и броят на превозните средства M (1 <= М <= 100000). На всеки от следващите М реда стоят по 4 цели числа – номерът на града, от който тръгва съответният влак/автобус, номерът на града в който пристига, часът на тръгване (в минути от завръщането на проф. Пенчо Минчев) и времето за пътуване (също в минути). Забележка: проф. Пенчо Минчев е сигурен, че може да стигне от Брегово до Казанлък за по-малко от една седмица.

Изходните данни програмата трябва да запише на стандартния изход. На първия ред трябва да се изведе Т – минималното време (в минути от завръщането на проф. Пенчо Минчев) за пристигането на професора в Казанлък. На втория ред трябва да се изведе К – броят на превозните средства, които трябва да ползва професорът и на всеки от следващите К реда трябва да се изведе по едно число – номерът на превозното средство (по реда на въвеждане, започвайки от 1). Ако задачата има повече от едно решение с равни минимални времена, изведете едно от тях.

Пример.

ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН’03

22 ноември 2003

ТЕМА ЗА  9–10 КЛАС (ГРУПА B)

Задача B3.  ШПИОНИ

В главната квартира на КГБ има М (1 <= М <= 20) реда с компютри. Всеки ред има N (1 <= N <= 10000) компютъра. Всеки компютър от даден ред си има номер. Първият компютър от всеки ред е с номер 1, втория – с номер 2 и т.н., N-тият компютър има номер N. През един слънчев ден от ФБР успели да проникнат в мрежата от компютри на КГБ и решили да се пошегуват с колегите си като преномерирали компютрите от всеки ред. Така за номера на компютрите от всеки ред останали числата от 1 до N, но в разбъркан ред. След това изведнъж им хрумнало да преброят колко двойки компютри от всеки ред изпълняват следното условие: i < j и Num[i] > Num[j], където i и j са старите номера на компютрите от даден ред, а Num[i] и Num[j] са техните номера след преномерирането. За жалост на служителите от ФБР, всички им програмисти били в отпуск и затова те решили да се обърнат за помощ към вас. Напишете програма FBI.EXE, която извършва преброяването.

Входните данни се четат от стандартния вход. На първия ред са числата M и N. Следващите М реда съдържат по N числа, които отговарят на новите номера на компютрите от съответния ред. Вторият ред от входа отговаря на първия ред с компютри и т.н., (N + 1)-ят ред от входа отговаря на N-тия ред с компютри.

Стандартният изход на програмата трябва да съдържа M реда. На всеки ред трябва да има по едно цяло число, което отговаря на броя на двойките компютри, които изпълняват горното условие.

Пример

Вход Изход

2 3                     0

1 2 3                   1

1 3 2