Авторски задачи

Машина на времето (Задача D6 - НОИ-3, Плевен, 2010 г.)

Изобретателят Айн Щайн създал машина на времето. Машината пътувала в кръг, като по часовник.  Tръгвала от настоящата 2010 година и пътувала напред в бъдещето до 4020 година. Щом я достигнела се пренасяла в година 1005 след Христа и пак тръгвала напред към настоящето.
Изобретателят Щайн разрешавал пътуване само ако желаещият успее да реши задача и отговори на въпроса в коя точно година ще го пренесе машината. Желаещите получават текст до 18 символа, в който има поне една цифра, различна от нула. Отделят се само цифрите (k на брой)  и с тях се образуват най-голямото и най-малкото възможни k-цифрени числа, като всяка цифра участва точно един път.  Разликата на тези две числа показва колко години ще пътува машината, тръгвайки от 2010 и пътувайки в кръга.
Помогнете на малкия изследовател Все Знайко, като създадете програма machine, която извежда точната година, в която машината ще се пренесе.

Ограничения: 1<=k<=18

Вход: На стандартния вход се въвежда текст до 18 символа.
Изход: На стандартния изход се извежда годината, в която машината ще се пренесе.

Пример:                                                                           

Задачата може да бъде решена по следния начин:
Отделят се цифрите от низа в масив и се сортират. Генерират се най-голямото и най-малкото число. При генерирането на най-малкото число трябва да се съобрази, че за да бъде то k – цифрено не трябва да има водещи нули. Намира се разликата им и се изчислява в коя година ще попадне машината при движението си в описания кръг.

Програмна реализация:
#include<iostream>
#include<string>
using namespace std;

int main()
{
char niz[20];
int i,j,swap,n,k=0,a[20],p;
unsigned long long A=0,B=0,C;
cin.getline(niz,20);
n=strlen(niz);

for(i=0;i<n;i++)
{
if(niz[i]>=48 && niz[i]<=57)
{
a[k]=niz[i]-48;
k++;
}
}
for(i=0;i<k-1;i++)
for(j=0;j<k-i-1;j++)
if(a[j]<a[j+1])
{
swap=a[j];
a[j]=a[j+1];
a[j+1]=swap;
}

for(i=0;i<k;i++)
A=A*10+a[i];

p=k-1;
if(a[p]==0)
{

           while(a[p]==0&&p>0) p--; 
a[k-1]=a[p];
a[p]=0;
}
for(i=0;i<k;i++)             
B=B*10+a[k-i-1];

C=((A-B)+1005)%3015+1005;
cout<<C<<endl;
return 0;
}

           
Всяка дума има свое тегло. То се определя от номерата на буквите в думата и от тяхната позиция.
Букви  A и a имат номер 1, букви B и b  – номер 2, букви C и c –  номер 3, … , букви Z и z  имат номер 26.
Теглото на думата се определя по следния начин  – номерът на първата буква се умножава по едно,  на втората – по две, на третата – по 4, на четвъртата – по 8, на петата – по 16  и т.н. Сборът на тези произведения  определя колко „тежи” дадената дума.. Например теглото на думата Kod се изчислява така:
11 x 1 + 15 x 2 + 4 x 4 = 57.

Напишете програма dumi, която за дадено множество от думи намира най-тежката дума.

            Вход: От първия ред на стандартния вход се въвежда броя на думите n, а от следващите n реда самите думи.
           
            Изход: На стандартния изход да се изведе „най-тежката” дума. Ако има няколко „най-тежки” думи, да се изведе първата по реда на въвеждане.

            Ограничения
2 <  n < 100
Всяка от дадените думи има най-много 20  букви.

Пример: