Циклические, повторяющиеся много раз однотипные вычисления позволяют наилучшим образом продемонстрировать вычислительные возможности компьютеров. Ради этого их изначально и создавали. В задачах этого раздела желательно снова перечитать параграф 5.4 из праймера посвященный «итерационным операторам» (так они назвали семейство из нескольких операторов цикла). Часть 5.4.3 можете пока пропустить, поскольку мы еще не изучали структур данных для которых … Continue reading →
Для заданных натуральных чисел $n$ и $m$ вывести прямоугольную рамку размером $n \times m$ из звездочек, заполненную пробелами как показано в примере.
Входные данные
Два натуральных числа $n$ и $m \; (n, m \leqslant 100)$.
Выходные данные
Выведите прямоугольную рамку размером $n \times m$.
Тесты
№
Входные данные
Выходные данные
1
4 7
C++
1
2
3
4
*******
**
**
*******
2
2 8
C++
1
2
********
********
3
3 3
C++
1
2
3
***
**
***
4
3 2
C++
1
2
3
**
**
**
Программный код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
usingnamespacestd;
intmain(){
intn,m;
cin>>n>>m;
for(inti=0;i<n;i++)
{
for(intj=0;j<m;j++)
{
if((i==0)or(j==0)or(i==n-1)or(j==m-1))cout<<"*";
elsecout<<" ";
}
cout<<endl;
}
return0;
}
Решение
Для получения рамки нужно заполнить первые и последние строки символом $*$ . Для этого в цикле будем проверять равенство столбцов $0$, $(m-1)$ и строк $0$ , $(n-1)$. В случае равенства выводить символ. Таким образом получим рамку.
Задана последовательность целых чисел. Подсчитать количество элементов, у которых чётные соседи.
Входные данные
В первой строке задано количество элементов последовательности $n$ $(n \leqslant 100)$. Во второй строке заданы сами элементы, значение каждого из которых по модулю не превышает $100$.
Выходные данные
Вывести в одной строке количество элементов последовательности с чётными соседями.
Тесты
№
Входные данные
Выходные данные
1
6
1 2 3 4 5 6
2
2
9
3 6 3 5 2 9 1 2 5
0
3
3
2 1 2
1
4
6
13 24 54 66 44 77
2
5
4
100 224 666 222
2
Программный код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
usingnamespacestd;
intmain(){
inti=1,n,prev,pres,fut,count=0;
cin>>n;
cin>>prev;//вводим предыдущий элемент
cin>>pres;//вводим текущий элемент
while((cin>>fut)&&(i<n)){
if(prev%2==0&&fut%2==0)
count++;
prev=pres;//приравниваем предыдущий к текущему
pres=fut;//приравниваем текущий к будущему
i++;
}
cout<<count;
return0;
}
Решение
Идея решения задачи состоит в том, чтобы создать три переменные: $prev$ (предыдущий), $pres$ (настоящий, текущий) и $fut$ (будущий). Затем в цикле мы перезаписываем эти переменные т.е.: настоящий становится прошлым, будущий настоящим, а новый будущий мы читаем из
cin. Так же, в ходе решения задачи обнаружилась проблема с чтением количества элементов. Допустим, если мы записали, что $n=6$, а дальше ввели $10$ элементов, то количество элементов с чётными соседями будет считаться для $10$ элементов. Чтобы избежать этого мы ограничиваем количество читаемых элементов с помощью счётчика
i++ и цикла
while.
Выведите квадраты всех натуральных чисел не больших [latex]n[/latex] в возрастающем порядке.
Входные данные
Одно натуральное число [latex]n[/latex] [latex](n \leqslant 10^9)[/latex]
Выходные данные
Выведите список квадратов всех натуральных чисел не больших [latex]n[/latex] в возрастающем порядке.
Тесты
Входные данные
Выходные данные
1
1
16
1 4 9 16
93
1 4 9 16 25 36 49 64 81
100
1 4 9 16 25 36 49 64 81 100
Код
C++
1
2
3
4
5
6
7
8
9
#include <iostream>
usingnamespacestd;
intmain(){
intn;
cin>>n;
for(inti=1;i*i<=n;i++)cout<<i*i<<' ';
return0;
}
Решение
Воспользуемся циклом, в котором заведем переменную [latex]i[/latex] и будем перечислять числа [latex]1, 4, 9, …, i^2[/latex], пока [latex]i^2[/latex] не будет больше [latex]n[/latex]. Выводим последовательно квадраты натуральных чисел в одной строке.
Подавляющее большинство людей стараются найти закономерности, которые приносят удачу! Зуб акулы в ухе папуаса — к удачной рыбной ловле. Черная кошка, которая передумала перебегать вам дорогу — к отмене контрольной. Любимая игрушка у компьютера — к удаче в командном чемпионате по программированию.
Для большинства студентов несомненным является тот факт, что номер трамвайного билетика приносит удачу. А уж если такой билетик достался перед экзаменом, пятерка обеспечена! Главное тут — четко понимать, что такое счастливый билет. И почему, спрашивается, многие считают, что только номер автобусного или троллейбусного билета может приносить удачу своему владельцу?! Чем хуже, скажем, номер паспорта или номер кассового чека в гастрономе? Главное, чтобы номер был счастливым!
Витька всегда считал, что удачу приносят такие номера, в записи которых цифры идут в неубывающем порядке. Например, счастливыми являются номера $11111$ или $12345$. Даже номер $00000$ — тоже счастливый!
Интересно, сколько счастливых номеров существует для заданной длины записи числа? Напишите программу, которая это количество вычислит.
Входные данные
Входной файл содержит единственное целое число $N$, $(1 \leq N \leq 64)$, $N$ — длина числа, для которой нужно вычислить количество счастливых номеров.
Выходные данные
Вывести одно число — количество счастливых номеров.
Тесты
№
Входные данные
Выходные данные
1
2
55
2
4
715
3
3
220
Программный код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "iostream"
usingnamespacestd;
longlongintfactorial(intn){
longlonginta=1;
for(inti=(n+9);i>n;i--)a=a*i;// мы сократили, чтобы не пришлось делить огромные числа
returna;
}
intmain()
{
intn;
cin>>n;
longlongintfact=1;
for(inti=2;i<=9;i++)fact=fact*i;
cout<<(factorial(n)/fact);
return0;
}
Решение
Для того, чтобы решить эту задачу, я начертил таблички (рис. 1.1) для всех вариантов $2$ значного числа и $1$ значного (рис. 1.2). Для $3$ значного аналогично, только рядов будет $3$. Из комбинаторики мы помним формулу: $C_n^m=\frac{n!}{m!(n-m)!}$, из которой мы получим: $(n + 9)! \over {9! \times n!}$. Потому-что из картинки мы видим что при 1 значном числе количество вариантов равно $10$. В коде я сразу сокращал на $n!$, чтобы не получались огромные числа.
returnfalse;// комбинация не найдена - возвращаем false
}
intmain(){
intn;
cin>>n;// считываем число, до которого будем искать
for(intk=5;k<=n;k++)// проверка для каждого k
if(check(k))
cout<<k<<" ";
return0;
}
Решение
Для решения задачи создадим функцию
check(), которая будет возвращать $true$, если число можно представить в виде суммы двух квадратов или же $false$, если нельзя. В функции перебираем всевозможные варианты $i$ и считаем $j$ для каждого $i$ по формуле $j=\sqrt{n-i^2}$, до тех пор пока не найдем целое (не равное $i$ ) $j$ или же не переберем все $i$. Просматриваем до $ i \cdot i < n $, потому что сумма двух квадратов не может превышать заданного числа. Формулу получили выразив $j$ из исходной формулы $(i^2+j^2=n)$.
Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $1$, дальше они нумеровались по кругу, а последний инструмент с номером $n$ висел слева от этой двери.
Малыши часто просили его научить играть на каком-нибудь инструменте. Гусля не отказывал, но сначала предлагал взять инструмент с первым номером, а если ученику хотелось играть на другом, то он выбирал шестой следующий по кругу и так далее. Напишите программу, которая определяла номер попытки, с которой ученик мог получить желаемый инструмент с номером $k$.
Например, если количество инструментов $n = 11$, то последовательность будет следующей: $(1) 2 3 4 5 6 (7) 8 9 10 11 1 (2) 3 4 5 6 7 (8) 9 10 11 1 2 (3) 4 5$ …, то есть при $k = 3$ инструмент с номером $3$ можно было бы получить с пятой попытки.
Входные данные
Два натуральных числа $n$ и $k$ $(1 \leqslant k \leqslant n \leqslant 100)$.
Выходные данные
Вывести номер попытки, в который «выпадал» инструмент с номером $k$. Если это никогда не происходило, следует вывести $0$.
Для решения задачи нам необходимо рассмотреть ряд натуральных чисел, начиная с единицы и прибавляя каждый раз $6$. С помощью операции деления с остатком мы можем реализовать алгоритм нахождения номера музыкального инструмента. Однако логика решения изменяется в зависимости от введенных пользователем данных. Имеется два случая:
Если пользователь вводит разные числа.
Если пользователь вводит одинаковые числа.
В первом случае мы рассматриваем две ситуации:
1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.
Во втором случае мы также рассматриваем две ситуации:
1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
Также не забываем про подводный камень, указанный выше.
Ещё в детстве маленького Гарика заинтересовал вопрос: а сколькими способами на шахматной доске размером [latex]n \times n[/latex] можно расставить [latex] n [/latex] ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.
А как быстро Вы управитесь с этой задачкой?
Входные данные
Размер шахматной доски — натуральное число, не превышающее [latex] 1000 [/latex].
if(carry>0){// если в разряде переноса все еще остались цифры
c.push_back(carry);
}
returnc;
}
intmain(){
intn;
intbase=1000;
cin>>n;
vector<int>res;
res.push_back(0);
res.push_back(1);
for(inti=1;i<n;i++){
res=multiply(res,i+1,base);
}
cout<<res[res.size()-1];
for(inti=res.size()-2;i>=1;i--){
cout<<setw(3)<<setfill('0')<<res[i];
}
}
Код № 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <string>
usingnamespacestd;
stringmultiplication(stringx,inty){
intcarry=0,temporary=0;
stringanswer="";
for(inti=x.size()-1;i>=0;i--){
temporary=int(x[i]-'0')*y+carry;
carry=temporary/10;
answer=char(temporary%10+'0')+answer;
}
while(carry){
answer=char(carry%10+'0')+answer;
carry/=10;
}
returnanswer;
}
intmain(){
intn;
strings="1";
cin>>n;
for(inti=2;i<=n;i++){
s=multiplication(s,i);
}
cout<<s<<endl;
}
Алгоритм решения
Алгоритм решения данной задачи заключается в том, что нужно вычислить [latex]n! = 1\times 2\times 3\times \cdots\times n [/latex] , используя длинную арифметику ( умножение длинного числа на короткое ).
Иллюстрация для восьми ладей:
В коде № 1 разбиваем вектор на ячейки по три цифры. Но, некоторые ячейки могут иметь менее чем три цифры. С учетом того, что перенос может состоять не из трех цифр, следует выводить результат так:
cout<<setw(3)<<setfill('0')<<res[i];.
В коде № 2 разбиваем строку посимвольно.
Детали реализации
Безусловно, для использования векторов и строк нам понадобятся соответствующие библиотеки:
#include <vector> и
#include <string>.
Для вывода данных в коде № 1 стоит подключить библиотеку
#include <iomanip>.
if(div.top()==sqrt_n)div.pop();//удаляем последний элемент, если он является корнем
while(!div.empty()){
cout<<n/div.top()<<" ";
div.pop();//выводим и удаляем первый элемент
}
return0;
}
Решение
Можно заметить, что делитель и частное взаимодополняют друг друга. Мы найдем делители, потом частные этого выражения. Так как частные также являются делителями. Значит последовательность делителей в порядке возрастания можно разделить на две части. Создадим два цикла для нахождения этих двух частей:
В первом цикле проверяем каждое натуральное число от $1$ до $\sqrt n$. В коде №1 выводим числа, если они являются делителями. В коде №2 помещаем их в стек и выводим;
Во втором цикле в коде №1 делим заданное число $n$ на все делители и выводим. В коде №2 делим заданное число $n$ на все элементы стека и выводим.
Примечание: для избежания повторения в коде №2, удаляем $\sqrt n$ из стека.
Напишите программу, которая считывает строку и проверяет, содержит ли она действительное число. Действительное число может содержать десятичную точку или показатель степени (начинающийся с $ e $ или $ E $), или и то и то одновременно. Также число может содержать обыкновенный набор десятичных цифр. Если число содержит десятичную точку, то должна присутствовать хотя бы одна цифра с каждой стороны точки. Перед числом или экспонентой может находиться плюс или минус (или одновременно и там и там) (без пробелов после знака). Экспонентой является целое число (не содержит десятичной запятой). Пробелы могут присутствовать до или после числа, но не внутри него. Обратите внимание, что границ диапазона входных чисел не существует, но для простоты будем предполагать, что входные строки содержат не более $ 1000 $ символов.
Входные данные
Первая строка содержит количество тестов $ t $. Дальше следует $ t $ строк, каждая из которых содержит одно число.
Выходные данные
Вывести $ t $ строк, каждая из которых содержит слово $ LEGAL $ или $ ILLEGAL $.
Тесты
№
Входные данные
Выходные данные
1.
2
1.5e+2
3.
LEGAL
ILLEGAL
2.
4
752.45e+24
0.762e.
-0.355.6432e
LEGAL
ILLEGAL
ILLEGAL
3.
1
-652.32e+45
LEGAL
4.
3
542.512e+3
123.456E+42
123.456.789
LEGAL
LEGAL
ILLEGAL
Код
5041
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
usingnamespacestd;
boolisdigit(charx){// проверка, является ли символ числом
return(x>='0'&&x<='9'?1:0);
}
boolisreal(char*x){// сама функция синтаксического анализа
cin>>x;// ввод игнорирует пробелы, которые по условию могут быть до и после числа
cout<<(isreal(x)?"LEGAL":"ILLEGAL")<<"\n";
}
return0;
}
Решение
Для решения задачи нам понадобится функция
idigit() проверки того, является ли символ цифрой. В STL существует одноименная функция, которая выполняет ту же самую задачу, однако для практики, я написал свою. В функции анализа вещественных чисел
isreal() нужно указать условия, при которых синтаксис будет нарушен. Т.е. не будут выполнены условия, описанные в задаче. Затем, если в символьном массиве не было замечено ошибок — возвратить
trueв основную функцию. Важно то, что в числе не должно по условию быть других символов кроме «e», «E», «.», «+», «-» и цифр. Что касается окаймляющих пробелов, то при вводе строки через
cin они игнорируются.
На сайте в таблице результатов соревнований, проводимых по правилам ACM (Association for Computing Machinery), верно решённая задачка оценивается плюсом. Но он какой-то маленький. Выведите большой плюс из звёздочек.
Входные данные
Целое число [latex]n[/latex] ([latex]1 \leqslant n \leqslant 100[/latex]).
Выходные данные
Выведите соответствующий большой квадратный «плюс» из точек и звёздочек — см. примеры входных и выходных данных.
Задача задана немного нетривиально: не указано, каким образом число [latex]n[/latex] должно влиять на выходные данные. Однако по приведённым в условии примерам легко понять, что [latex]2n+1[/latex] — это ширина и высота плюса из звёздочек.
Печатать будем по строкам, для этого создадим главный цикл. Существует два случая: когда нужно вывести полную строку звёздочек (если [latex]u=n[/latex], то есть мы находимся в середине плюса) и когда нужно вывести обычную строку, состоящую из [latex]2n[/latex] точек и звёздочки посередине. В первом случае распечатываем [latex]2n+1[/latex] звёздочек. Во втором с помощью условия в цикле выводим звёздочку, если [latex]i=n[/latex] (центр строки), при других [latex]i[/latex] точки.
Факториал натурального числа [latex]n[/latex] определяется как произведение всех натуральных чисел от [latex]1[/latex] до [latex]n[/latex] включительно.
Код № 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
usingnamespacestd;
longfactorial(inta){
if(a==0)
return1;
else
returna*factorial(a-1);
}
intmain(){
inta,n;
cin>>n;
cout<<factorial(n);
return0;
}
Решение № 2
Также факториал числа можно найти при помощи рекурсивной функции (функции, которая вызывает сама себя).
Нурдаулет и Жарасхан тренируют студентов. К каждому студенту у них имеется свое собственное отношение, которое выражается как числа $a_{i}$ (для Нурдаулета) и $b_{i}$ (для Жараскана), которые называются индексом любви студентов. Аскар попросил их рассчитать коэффициент несправедливого отношения. Коэффициент несправедливого отношения — это разница между самым большим и самым маленьким индексом любви. Чтобы не показывать свои, возможно, большие коэффициенты несправедливого отношения, они решили обмануть: каждый перемешивает свой массив, после чего формируется новый массив $c_{i}$ = $a_{i}$ + $b_{i}$, и его коэффициент несправедливого отношения передается Аскару. Какое минимально возможное значение коэффициента они могут достичь?
Входные данные
Первая строка содержит одно целое число $n$ $(1 ⩽ n ⩽ 200000)$. Вторая строка содержит $n$ целых чисел $a_{i}$ $(-10^6 ⩽ a_{i} ⩽ 10^6)$. Третья строка содержит $n$ целых чисел $b_{i}$ $(-10^6 ⩽ b_{i} ⩽ 10^6)$.
sort(b,b+n);// Вместо сортировки по убыванию будем просматривать отсортированный массив в обратном порядке
for(inti=0;i<n;i++)a[i]+=b[n-i-1];// Суммируем элементы
intmaxa=a[0],mina=a[0];
for(inti=0;i<n;i++){
maxa=max(maxa,a[i]);// Находим минимальный и максимальный элементы
mina=min(mina,a[i]);
}
cout<<maxa-mina;// Разность минимального и максимального и будет самым маленьким индексом любви
return0;
}
Решение
Коэффициент будет минимальным в том случае, когда все элементы массива $c_{i}$ будут отличаться друг от друга как можно меньше. Для этого отсортируем один массив по убыванию, другой — по возрастанию и почленно сложим. После этого останется только найти максимальный и минимальный элементы полученного массива.
Сначала задано число $n\, \left ( 1\leqslant n\leqslant 100 \right )$, а затем n моментов времени. Каждый момент времени задается 3 целыми числами — часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60)
Выходные данные
Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не нужно)
Создадим 4 массива где мы будем хранить время(отдельно часы, минуты, секунды), а также четвертый в котором мы будем хранить все время в одной удобной для нас единице измерения — секундах. Читаем поток ввода и переводим полученные данные, сравниваем их потом сортируем полученные результаты и выводим ответ.
Аліна хоче замовити таксі через один відомий додаток. Одразу декілька водіїв готові приїхати на її замовлення.
Проте Аліна — дівчинка відповідальна, вона бажає поїхати із найдосвідченішим таксистом, тобто з тим, який вже здійснив найбільшу кількість перевезень. Але ось невдача — додаток не показує кількість перевезень, здійснених водієм. Єдина інформація, якою володіє Аліна — рейтинг водія.
Нагадаємо, що по завершенню кожного перевезення пасажир виставляє водієві оцінку — ціле число від $1$ до $5$ включно. Рейтинг таксиста $R$ рахується як середнє арифметичне усіх отриманих ним оцінок.
Завдання
Допоможіть Аліні – напишіть програму, яка визначить мінімально можливу кількість перевезень, які мав здійснити таксист щоб отримати рейтинг рівно $R$ (без округлень).
Вхідні дані
В єдиному рядку вхідного файлу знаходиться дійсне число $R$ $\left(1 \leqslant R \leqslant 5 \right)$ — рейтинг водія з точністю не більш ніж $18$ знаків після десяткової крапки.
Вихідні дані
В першому рядку вихідного файлу виведіть єдине натуральне число — відповідь на задачу, або $-1,$ якщо заданий рейтинг отримати неможливо.
Якщо рейтинг отримати можливо, у другому рядку необхідно вивести $5$ цілих невід’ємних чисел — кількість оцінок $1,$ $2,$ $3,$ $4$ і $5$ відповідно, отриманих водієм. У разі коли існує декілька варіантів оцінок, які призводять до оптимальної відповіді, дозволяється вивести будь-який з них.
Оцінювання
Пiдзадача. Бали. Додатковi обмеження. Необхідні підзадачі.
$0$ Тести з умови —
$41$ Точнiсть $R$ не бiльш нiж $1$ знак пiсля коми —
$33$ Точнiсть $R$ не бiльш нiж $6$ знаків пiсля коми $0,$ $1$
$26$ Точнiсть $R$ не бiльш нiж $18$ знаків пiсля коми $0,$ $1,$ $2$
Спочатку зазначимо, що для рейтингу з точністю $k$ знаків після десяткової коми оптимальна відповідь завжди $\leqslant 10^k$. Розглянемо це на прикладі. Нехай ми маємо рейтинг $3.xxx,$ де $xxx$ — $3$ будь-які цифри. Припустимо, що таксист отримав $10^3=1000$ оцінок $3.$ Тоді його рейтинг буде дорівнювати $\frac{3\cdot1000}{1000}=3.000,$ тобто рівно $3.$ Тепер спробуємо замінити одну оцінку $3$ на $4.$ Тоді його рейтинг дорівнюватиме $\frac{3\cdot 999+4\cdot 1}{999+1}=\frac{3001}{1000}.$ Тобто замінивши одну трійку на четвірку ми збільшили рейтинг на $\frac{1}{1000}.$ Таким чином якщо поступово змінювати усі $3$ на $4$ ми зможемо отримати будь-який рейтинг від $3.000$ до $4.000$ з трьома знаками після коми, а отже і заданий рейтинг $3.xxx.$
Підзадача $1$:
Виходячи з вищезазначеного відповідь $\leqslant 10.$ Тоді ЇЇ можна отримати просто перебравши усі можливі комбінації оцінок $5$-ма вкладеними циклами.
Підзадача $2$:
Доведемо, що оптимальну відповідь завжди можна отримати тільки за допомогою оцінок двох сусідніх типів $a$ та $\left(a+1\right),$ або одного типу (якщо рейтинг цілий). Припустимо, що існує оптимальна відповідь, у якій НЕ сусідні оцінки $x$ та $y,$ $x<y.$ У випадку, якщо $y-x=3,$ ми можемо замінити їх на $x+1$ та $y-1.$ Якщо $y-x=2$ або $y-x=4,$ можна замінити їх на дві оцінки по $x+1$ або $x+2$ відповідно. Ці дії жодним чином не впливають ні на суму, ні на кількість оцінок, а тому не впливають і на середнє арифметичне. Таким чином, будь-який набір оцінок можна звести до набору оцінок з щонайбільше двох типів. Очевидно, що ці два типи — рейтинг округлений вниз та вгору.
Тоді розв’язання полягає у тому щоб перебрати кількість оцінок першого типу, порахувати скільки потрібно оцінок другого типу, аби отримати заданий рейтинг і перевірити, чи кількість оцінок другого типу ціла (тобто такий розподіл оцінок можливий). Нехай рейтинг рівня $R,$ покладемо $a=\lfloor R\rfloor,$ кількість оцінок типу $a$ дорівнює $x,$ а кількість оцінок типу $a+1$ (якщо вони необхідні) дорівнює $y.$ Тоді, $x\cdot a+y\cdot\left(a+1\right)=R\cdot x+R\cdot y.$ З цього, щоб отримати точну відповідь, потрібно виконувати операції у цілих числах або у $64$-бітних числах з плавоючою комою.
Підзадача $3$:
Представимо рейтинг $R$ у вигляді звичайного дробу, домноживши чисельник та знаменник на $10^{18}$. Виходячи з визначення середнього арифметичного, знаменник цього дробу $10^{18}$ — кількість отриманих оцінок, а чисельник $\left( R \cdot 10^{18} \right)$ — їх сума. Якщо цей дріб можна скоротити, це зменшить кількість оцінок, тому що знаменник (тобто кількість оцінок) зменшиться, а відношення чисельника до знаменника (тобто рейтинг) не зміниться. Отже, чисельник і знаменник потрібно поділити на їх НСД. Припустимо, що після скорочення ми отримали дріб $\frac{a}{b}.$ Очевидно, що отримане у знаменнику число $\left( b \right)$ і є оптимальною відповіддю, адже дріб нескоротний і зменшити знаменник не вдасться. Тепер потрібно довести, що ця відповідь завжди досяжна, тобто існує набір з $b$ оцінок від $1$ до $5$, сума яких дорівнює $a.$
Доведення цього факту аналогічне доведенню у підзадачі $2.$ Зауважимо, що завжди $b \leqslant a \leqslant 5b,$ бо рейтинг за умовою від $1$ до $5$. Тепер припустимо, що усі оцінки дорівнюють $1.$ Тоді чисельник дорівнюватиме $1 \cdot b,$ тобто $b.$ Тепер змінемо будь-яку оцінку $\left( m \neq 5 \right)$ на $m+1.$ Тоді чисельник збільшиться на $1,$ а знаменник залишиться рівним $b.$ Поступово здійснюючи такі заміни, можемо припустити «пройти» через усі значення від $b$ до $5b,$ зокрема і через $a,$ яке нам потрібно отримати.
Аби відновити самі оцінки, згадаємо доведений у другій підзадачі факт про те, що оптимальну відповідь завжди можна отримати з оцінок $\lfloor R\rfloor$ та $\lceil R\rceil.$ Якщо б усі оцінки дорівнювали $\lfloor R\rfloor,$ чисельник був би $b \cdot \lfloor R\rfloor .$ Але чисельник дорівнює $a \geqslant b \cdot \lfloor R\rfloor ,$ тому кількість оцінок $\lceil R\rceil$ як раз дорівнює залишку, тобто $a-b \cdot \lfloor R\rfloor .$ Решта оцінок – оцінки $\lfloor R\rfloor .$ Також зауважимо, що через недостатню точність зберігання чисел з плаваючою комою у пам’яті комп’ютера, необхідно зчитувати рейтинг у вигляді рядка і конвертувати одразу у ціле число.
Первая строка содержит количество тестов. Каждая следующая строка содержит три целых числа $x, m$ и $n (1 \le x, m, n \le 10^{16})$.
Выходные данные
Для каждого теста выведите ответ в отдельной строке.
Тесты
Входные данные
Выходные данные
1 1000 1 10000
1001
1 999999999999999 999999999999999 13
8
1 99999999999999 99999999999999 23
8
1 3 2 5
3
Алгоритм
Для решения этой задачи можно использовать следующий алгоритм. Сумму данной последовательности будем считать рекурсивно. Базой рекурсии является случай когда степень $m = 0$. Также есть два случая:
Количество членов последовательности четно (а следовательно степень $m$ нечетная), тогда заметим что $(1 + x + x^2 + \ldots + x^m)$ можно представить как $(1 + x + x^2 \ldots +x^{\frac{m}{2}}) + x^{\frac{m+1}{2}} \cdot (1 + x + x^2 + \ldots + x^{\frac{m}{2}}) = $ $= (1 + x + x^2 + \ldots + x^{\frac{m}{2}}) \cdot (1 + x^{\frac{m+1}{2}})$
Количество членов последовательности нечетно (степень $m$ четная), тогда от последовательности $(1 + x + x^2 + \ldots + x^m)$ можно отделить последний член $x^m$ и тогда ситуация будет сведена к первому случаю.
Для возведения $x$ в степень будем использовать алгоритм быстрого возведения в степень, а результат брать по модулю $m$.
Найти закопанный пиратами клад просто: всё, что для этого нужно – это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм нахождения клада так: «Встаньте около одинокой пальмы. Пройдите тридцать шагов в сторону леса, потом семнадцать шагов в сторону озера, …, наконец десять шагов в сторону большого булыжника. Клад находится под ним«. Большая часть таких указаний просто сводится к прохождению какого-то количества шагов в одном из восьми направлений ([latex]1[/latex] – север, [latex]2[/latex] – северо-восток, [latex]3[/latex]– восток, [latex]4[/latex] – юго-восток, [latex]5[/latex] – юг, [latex]6[/latex] – юго-запад, [latex]7[/latex] – запад, [latex]8[/latex] – северо-запад) (см. рис). Длина шага в любом направлении равна 1. Путешествие по такому пути обычно является прекрасным способом посмотреть окрестности, однако в наше время постоянной спешки ни у кого нет времени на это. Поэтому кладоискатели хотят идти напрямую в точку, где зарыт клад. Например, вместо того, чтобы проходить три шага на север, один шаг на восток, один шаг на север, три шага на восток, два шага на юг и один шаг на запад, можно пройти напрямую, использовав около 3.6 шага (см. рис).
Вам необходимо написать программу, которая по указаниям пиратов определяет точку, где зарыт клад.
Входные данные
Первая строка входного файла содержит число [latex]N[/latex] – число указаний $(1 ≤ N≤ 40)$. Последующие [latex]N[/latex] строк содержат сами указания – номер направления (целое число от 1 до 8) и количество шагов (целое число от 1 до 1000). Числа разделены пробелами.
Выходные данные
В выходной файл выведите координаты [latex]X[/latex] и [latex]Y[/latex] точки (два вещественных числа, разделённые пробелом), где зарыт клад, считая, что ось [latex]Ox[/latex] направлена на восток, а ось [latex]Oy[/latex] – на север. В начале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с точностью [latex]10^{-3}[/latex].
Тесты
№
Ввод
Вывод
1
6
1 3
3 1
1 1 3 3
5 2 7 1
3.000 2.000
2
1
8 10
-7.071 7.071
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <math.h>
#include <iomanip>
usingnamespacestd;
intmain(){
longlongn,z,dir;
longlongx=0,y=0,ne=0,se=0;
doubledx,dy;
cin>>n;
while(n--){
cin>>dir>>z;
switch(dir){
case1:y+=z;break;
case5:y-=z;break;
case3:x+=z;break;
case7:x-=z;break;
case2:ne+=z;break;
case6:ne-=z;break;
case4:se+=z;break;
case8:se-=z;break;
}
}
dx=x+(ne+se)*M_SQRT1_2;
dy=y+(ne-se)*M_SQRT1_2;
cout<<fixed<<setprecision(3)<<dx<<" "<<dy;
return0;
}
Решение
Как видно из рисунка направление 1 совпадает с осью [latex]y[/latex], а 3 — с осью [latex]x[/latex]. Допустим, направление — переменная [latex]dir[/latex], а шаг-[latex]z[/latex]. Тогда, для направления 1 можно записать $y=z\cdot\cos((45^0)\cdot(dir — 1))$ , $x=z\cdot\sin((45^0)\cdot(dir-1)) $. Выражение $\cos((45^0)\cdot(1-1))=\cos(0^0)=1$ , то есть для 1 направления [latex]y=z[/latex], а выражение $\sin((45^0)\cdot(dir-1))=\sin((45^0)\cdot(1-1))=0 $. Следовательно, для направления 1 координаты [latex]y[/latex] и [latex]x[/latex] принимают значения: [latex]y=z[/latex], а [latex]x=0[/latex] .Рассмотрите значения приведенных выражений для всех направлений и увидим, что для всех направлений можно применить данные выражения для вычисления координат. А это позволяет сократить код программы.
Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера $n × m$, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.
Школьники заняли свои места следующим образом: они входили в зал в порядке, в котором шли их номера, и полностью занимали сначала первый ряд, потом второй, потом третий и т.д.
Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).
Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.
Входные данные:
В первой строке заданы числа $n$ и $m$ $(1 \le n, \le 1000)$.
Выходные данные:
Выведите одно число — количество учеников, которые в результате пересадки останутся сидеть на тех же местах.
Конус расположен в трехмерном пространстве так, что его основание радиуса [latex] r [/latex] лежит в плоскости [latex] z = 0 [/latex] с центром в [latex] (0,0,0) [/latex]. Вершина конуса расположена в [latex] (0, 0, h) [/latex]. На его поверхности заданы две точки в конусных координатах. Конусной координатой точки называется пара чисел [latex] (d, A) [/latex], где [latex] d [/latex] — расстояние от вершины конуса до точки [latex] p [/latex], а [latex] A (A < 360) [/latex] — угол в градусах между плоскостью [latex] y = 0 [/latex] и плоскостью, проходящей через точки [latex] (0,0,0), (0,0,h) [/latex] и [latex] p [/latex], считая против часовой стрелки от направления оси [latex] x [/latex].
На поверхности конуса заданы две точки [latex] p1 = (d1, A1) [/latex] и [latex] p2 = (d2, A2) [/latex]. Найти кратчайшее расстояние между [latex] p1 [/latex] и [latex] p2 [/latex], измеряемое по поверхности конуса.
Входные данные
Каждая строка является отдельным тестом и содержит 6 действительных чисел: [latex] r, h, d1, A1, d2 [/latex] и [latex] A2 [/latex].
Выходные данные
Для каждого теста в отдельной строке вывести кратчайшее расстояние между точками [latex] p1 [/latex] и [latex] p2 [/latex] по поверхности конуса. Расстояние выводить с 2 десятичными знаками.
Инициализирую все нужные переменные и через поток ввода считываю все исходные данные. Затем нахожу образующую
l по теореме Пифагора и угол между плоскостями —
alpha .
k1 это часть, которую занимает угол
alpha от основания конуса.
k2 — коэффициент пропорциональности между окружностями радиусами
r и
l .
fi — величина угла развертки конуса, а
beta — угол между прямыми на которых лежат точки, данные в условии. Далее находим искомое расстояние по теореме косинусов.
Frank Gray (13 September 1887 – 23 May 1969) was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic
Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.
Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: «двоичный отражённый (рефлексный) код Грея». Именно этот код обычно имеется в виду, когда говорят о неконкретном «коде Грея».
Отображённый двоичный код Грея строится следующим образом. Начинаем со строк [latex]0[/latex] и [latex]1[/latex], которые представляют соответственно целые числа [latex]0[/latex] и [latex]1[/latex].
[latex]0[/latex]
[latex]1[/latex]
Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим [latex]1[/latex] слева от новых записей списка, а слева от уже имевшихся разместим [latex]0[/latex].
[latex]00[/latex]
[latex]01[/latex]
[latex]11[/latex]
[latex]10[/latex]
Таким образом получен отражённый код Грея для [latex]n = 2[/latex]. Чтобы получить код для [latex]n = 3[/latex], повторим описанную процедуру и получим:
[latex]000[/latex]
[latex]001[/latex]
[latex]011[/latex]
[latex]010[/latex]
[latex]110[/latex]
[latex]111[/latex]
[latex]101[/latex]
[latex]100[/latex]
При таком способе построения легко увидеть по индукции по [latex]n[/latex], что, во-первых, каждая из [latex]2n[/latex] комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.
Для каждого заданного числа [latex]k[/latex] вывести десятичное значение [latex]k[/latex]-го кода Грея.
Входные данные
Во входном файле содержится некоторый набор тестовых данных, каждое число [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает [latex]10^5[/latex].
Выходные данные
Для каждого заданного числа [latex]k[/latex] вывести в отдельной строке десятичное значение [latex]k[/latex]-го кода Грея.
Тесты
№
Входные данные
Выходные данные
1
3
2
14
9
5
7
12
10
2
0
0
72
108
265
397
4781
7163
50642
42811
3
1010234
581415
96721758
119682801
640214927
893162568
2456987013
3679188807
51027963402
60418988303
1000000000000000000
797398725282889728
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
usingnamespacestd;
intmain(){
unsignedlongintk;
while(cin>>k){
cout<<(k^(k>>1))<<endl;
}
return0;
}
Решение задачи
Объявляем переменную [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) типа
unsignedlongint для считывания чисел из входного потока. Цикл
while работает столько раз, сколько чисел во входном потоке (по условию задачи их количество [latex]\le 10^5[/latex]). В цикле вычисляется Код Грея числа [latex]k[/latex] путем побитовой операции «исключающее ИЛИ», применимого к [latex]k[/latex] и к результату побитового сдвига [latex]k[/latex] на [latex]1[/latex] бит вправо ([latex]k \gg 1[/latex]).
Ссылка на алгоритм ниже.
Для отправки комментария необходимо войти на сайт.