В конце каждого семестра проводится итоговая контрольная работа.
По итогам первого семестра предлагалась на 3 часа работа состоящая из 10 задач для нескольких категорий студентов по уровню текущей успеваемости.
Первые 4 задачи от А до D соответствовали нескольким базовым темам полностью рассмотренным на занятиях.
Задачи E и F (составленные Александром Сергеевичем Антоненко) требовали несколько больших размышлений перед решением.
Задачи G и H на самом деле являлись одной задачей — решение задачи H легко может быть написано таким образом, чтобы задача G тоже проходила все тесты.
Две последние задачи I и J были составлены мной достаточно давно для (как я тогда искренне считал!) простого пробного тура финального этапа Всеукраинской олимпиады по программированию. Т.е. я считал их слишком простыми для серьёзной олимпиады. На данной контрольной эти задачи предназначались для студентов, перевыполнивших учебный план. Обе задачи хоть и олимпиадного уровня, но не громоздкие с точки зрения программной реализации.
В настоящее время экзамен временно НЕ доступен в режиме «дорешивания» по адресу http://acm.onu.edu.ua/cgi-bin/register?contest_id=48.
Чуть позже здесь появится разбор некоторых (или всех?) задач. Или нет.
Да! Меня попросили побыстрее опубликовать авторское решение для задачи H. Вызывает разумные сомнения возможность вычислить 19-ю цифру в числе. Ведь на сервере сейчас используется компилятор в котором невозможно использовать более чем 64 битные целые числа. Действительно это не так просто. Самое большое число, которым мы можем оперировать не привлекая «длинной арифметики» состоит всего из 20 цифр — 18 446 744 073 709 551 615. Т.е. не всякое 20-значное число поместится. Но 19-значное поместится. Значит принципиальная возможность всё же есть. Только не нужно допускать выхода за эти пределы результатов промежуточных вычислений.
Для тех кто не верит, и не хочет думать сам, публикую авторский код, который проходит все тесты:
|
1 2 3 4 5 6 7 8 9 10 |
#include<iostream> int main(){unsigned long long o,oo=1Ull,ooo,ull=1Ull,Ull=1Ull,UlL =1Ull,ULL=1Ull;std::cin>>o>>ooo>>oo;for(size_t ULl=0;ULl<oo;ULl++ ){ull*=2Ull;Ull*=5Ull;}for(size_t ULl=0;ULl<ooo;ULl++){UlL=(UlL*o )%ull;ULL=(ULL*o)%Ull;}long long UL,Ul,ul,uLl,OO,U,OoO,oOo,oOO,u= Ull,uL=ull;if(uL==0){UL=u;Ul=1Ull;ul=0Ull;}else{OoO=1;U=0Ull;oOO= 0Ull;oOo=1Ull;while(uL>0){uLl=u/uL;OO=u-uLl*uL;Ul=OoO-uLl*U;ul=// oOO-uLl*oOo;u=uL;uL=OO;OoO=U;U=Ul;oOO=oOo;oOo=ul;}UL=u;Ul=OoO;ul= oOO;}if(UL==1)UlL=(ull+Ul)%ull*(UlL-ULL);UlL=UlL%ull;//obfuscate? if(UlL<0Ull)UlL+=ull;o=ULL+UlL*Ull;std::cout<<o/(ull*Ull/10Ull);} |
Код абсолютно рабочий. Просто я заодно решил показать Вам к чему приводит отсутствие «лесенки» и нормального именования переменных. Есть даже специальный сайт и международный конкурс «запутывателей» (Obfuscate) программного кода.