e-olymp 8663. Задача про множення

09/01/2020 by Эвелина Алексютенко

Задача

На уроці математики Байтик навчився множити, і почав застосовувати цю операцію з різними числами. Наприклад, розкладав число на цифри і знаходив добуток цифр. І тут він задумався, який найбільший добуток цифр серед натуральних чисел, що не перевищує [latex]N[/latex]. Допоможіть розв’язати задачу.

Вхідні дані

Одне число [latex]N(1\leqslant N\leqslant 2\times 10^{9})[/latex].

Вихідні дані

Максимальний добуток цифр серед чисел, що не перевищують [latex]N[/latex].

Тести

Вхідні дані	Вихідні дані
57	36
1000	729
7999	5103
28994	10368
4876	2268

Код програми

#include <iostream>
using namespace std;

int multiplication(int x) {
    int mul = 1;
    while(x != 0) {
        mul *= x % 10;
        x /= 10;
    }
    return mul;
}
int main() {
  int n;
  cin >> n;
  int maxmul = multiplication(n);  
  int copy = n;
  int i = 10;
  while(n != 0) {
      int temporary_number = (copy / (i / 10)) % 10;
      int left = copy / i;
      int right = copy % (i / 10);
      if(temporary_number != 9) {
        temporary_number = 9;
        copy = ((left - 1) * 10 + temporary_number) * (i / 10) + right;
      }
      n /= 10;
      i *= 10;
      int mul = multiplication(copy);
      if(maxmul < mul) maxmul = mul;
    }  
    cout << maxmul; 
}

#include <iostream>

using namespace std;

int multiplication(int x) {

int mul = 1;

while(x != 0) {

mul *= x % 10;

x /= 10;

}

return mul;

}

int main() {

int n;

cin >> n;

int maxmul = multiplication(n);

int copy = n;

int i = 10;

while(n != 0) {

int temporary_number = (copy / (i / 10)) % 10;

int left = copy / i;

int right = copy % (i / 10);

if(temporary_number != 9) {

temporary_number = 9;

copy = ((left - 1) * 10 + temporary_number) * (i / 10) + right;

}

n /= 10;

i *= 10;

int mul = multiplication(copy);

if(maxmul < mul) maxmul = mul;

}

cout << maxmul;

}

Алгоритм

Складність задачі полягає в обмеженості у часі.

Знайдемо добуток цифр заданого числа.
Змінемо останню цифру на [latex]9[/latex] та віднімемо [latex]1[/latex] від попереднього розряду. Визначаємо поточний добуток цифр отриманого числа. Повторюємо цю операцію з наступними розрядами числа.
Порівнюємо поточний добуток з максимальним.

Приклад:

Приклад розкладу числа на різних етапах алгоритму:

Посилання

Задача на e-olymp
Зарахований розв’язок
Код на ideone

Related Images:

e-olymp 1327. Ладьи на шахматной доске

14/12/2019 by Эвелина Алексютенко

Задача

Ещё в детстве маленького Гарика заинтересовал вопрос: а сколькими способами на шахматной доске размером [latex]n \times n[/latex] можно расставить [latex] n [/latex] ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.

А как быстро Вы управитесь с этой задачкой?

Входные данные

Размер шахматной доски — натуральное число, не превышающее [latex] 1000 [/latex].

Выходные данные

Выведите ответ, найденный Гариком.

Тесты

Входные данные	Выходные данные
2	2
10	3628800
500	122013682599111006870123878542304692625357434280319284219241 358838584537315388199760549644750220328186301361647714820358 416337872207817720048078520515932928547790757193933060377296 085908627042917454788242491272634430567017327076946106280231 045264421887878946575477714986349436778103764427403382736539 747138647787849543848959553753799042324106127132698432774571 554630997720278101456108118837370953101635632443298702956389 662891165897476957208792692887128178007026517450776841071962 439039432253642260523494585012991857150124870696156814162535 905669342381300885624924689156412677565448188650659384795177 536089400574523894033579847636394490531306232374906644504882 466507594673586207463792518420045936969298102226397195259719 094521782333175693458150855233282076282002340262690789834245 171200620771464097945611612762914595123722991334016955236385 094288559201872743379517301458635757082835578015873543276888 868012039988238470215146760544540766353598417443048012893831 389688163948746965881750450692636533817505547812864000000000 000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000
999	402387260077093773543702433923003985719374864210714632543799 910429938512398629020592044208486969404800479988610197196058 631666872994808558901323829669944590997424504087073759918823 627727188732519779505950995276120874975462497043601418278094 646496291056393887437886487337119181045825783647849977012476 632889835955735432513185323958463075557409114262417474349347 553428646576611667797396668820291207379143853719588249808126 867838374559731746136085379534524221586593201928090878297308 431392844403281231558611036976801357304216168747609675871348 312025478589320767169132448426236131412508780208000261683151 027341827977704784635868170164365024153691398281264810213092 761244896359928705114964975419909342221566832572080821333186 116811553615836546984046708975602900950537616475847728421889 679646244945160765353408198901385442487984959953319101723355 556602139450399736280750137837615307127761926849034352625200 015888535147331611702103968175921510907788019393178114194545 257223865541461062892187960223838971476088506276862967146674 697562911234082439208160153780889893964518263243671616762179 168909779911903754031274622289988005195444414282012187361745 992642956581746628302955570299024324153181617210465832036786 906117260158783520751516284225540265170483304226143974286933 061690897968482590125458327168226458066526769958652682272807 075781391858178889652208164348344825993266043367660176999612 831860788386150279465955131156552036093988180612138558600301 435694527224206344631797460594682573103790084024432438465657 245014402821885252470935190620929023136493273497565513958720 559654228749774011413346962715422845862377387538230483865688 976461927383814900140767310446640259899490222221765904339901 886018566526485061799702356193897017860040811889729918311021 171229845901641921068884387121855646124960798722908519296819 372388642614839657382291123125024186649353143970137428531926 649875337218940694281434118520158014123344828015051399694290 153483077644569099073152433278288269864602789864321139083506 217095002597389863554277196742822248757586765752344220207573 630569498825087968928162753848863396909959826280956121450994 871701244516461260379029309120889086942028510640182154399457 156805941872748998094254742173582401063677404595741785160829 230135358081840096996372524230560855903700624271243416909004 153690105933983835777939410970027753472000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000

Программный код

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
vector<int> multiply (const vector<int> &s, int b, int base) {
  vector<int> c;
  int carry = 0;
  for (int i = 0; i < s.size(); i++) {
    long long res = (long long)s[i] * b + carry;
    carry = res / 1000;
    c.push_back(res % base);    
  }
  if (carry > 0) { // если в разряде переноса все еще остались цифры
    c.push_back(carry);
  }
  return c;
}
int main() {
  int n;
  int base = 1000;
  cin >> n;
  vector<int> res;
  res.push_back(0);
  res.push_back(1);
  for (int i = 1; i < n; i++) {
    res = multiply(res, i + 1, base);
  }
  cout << res[res.size() - 1];
  for (int i = res.size() - 2; i >= 1; i--) {
    cout << setw(3) << setfill('0') << res[i];
  }
}

#include <iostream>

#include <vector>

#include <iomanip>

using namespace std;

vector<int> multiply (const vector<int> &s, int b, int base) {

vector<int> c;

int carry = 0;

for (int i = 0; i < s.size(); i++) {

long long res = (long long)s[i] * b + carry;

carry = res / 1000;

c.push_back(res % base);

}

if (carry > 0) { // если в разряде переноса все еще остались цифры

c.push_back(carry);

}

return c;

}

int main() {

int n;

int base = 1000;

cin >> n;

vector<int> res;

res.push_back(0);

res.push_back(1);

for (int i = 1; i < n; i++) {

res = multiply(res, i + 1, base);

}

cout << res[res.size() - 1];

for (int i = res.size() - 2; i >= 1; i--) {

cout << setw(3) << setfill('0') << res[i];

}

#include <iostream>
#include <string>
using namespace std;

string multiplication (string x, int y) { 
    int carry = 0, temporary = 0;
    string answer = "";
    for (int i = 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;
}
return answer;
}
int main() {
    int n;
    string s = "1";
    cin >> n;
    for (int i = 2; i <= n; i++) {
         s = multiplication(s, i);
    } 
    cout << s << endl;
}

#include <iostream>

#include <string>

using namespace std;

string multiplication (string x, int y) {

int carry = 0, temporary = 0;

string answer = "";

for (int i = 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;

}

return answer;

}

int main() {

int n;

string s = "1";

cin >> n;

for (int i = 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>.

Ссылки :
Задача на e-olymp
Код № 1 на ideone
Код № 2 на ideone
Засчитанное решение № 1
Засчитанное решение № 2

Related Images:

e-olymp 7612. Алекс и квадраты оригами

04/12/2019 by Эвелина Алексютенко

Задача

Алекс любит оригами — японское искусство складывания из бумаги. Большинство конструкций оригами начинаются с квадратного листа бумаги. Алекс собирается сделать подарок для своей матери. Подарочная конструкция требует три одинаковых квадратных листа бумаги, но у Алекса имеется только один прямоугольный лист. Он может из него вырезать квадраты, стороны которых должны быть параллельны сторонам листа. Помогите Алексу определить максимально возможный размер квадратов, который он способен вырезать.

Входные данные

В одной строке два целых числа [latex] h [/latex] и [latex] w [/latex] [latex] \left ( 1\leqslant h,w\leqslant 1000 \right ) [/latex] — высота и ширина куска бумаги.

Выходные данные

Выведите одно действительное число — наибольшую длину стороны квадратов. Всегда можно вырезать три одинаковых квадрата из листа бумаги размером [latex] h \times w[/latex] так, чтобы их стороны были параллельны сторонам листа.
Ответ следует вывести с точностью не меньше трех десятичных знаков.

Тесты

Входные данные	Выходные данные
30 11	10.0000
8 3	2.6667
210 297	105.0000
60 59	29.5000
250 100	83.3333

Программный код

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
    double h, w, ans = 0;
    cin >> h >> w;
    if (w < h) {
        swap (w, h);
    }
    ans = ( w >= 3 * h ? h : max (h / 2, w / 3) );
    cout << fixed << setprecision(4) << ans;
}

#include <iostream>

#include <algorithm>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double h, w, ans = 0;

cin >> h >> w;

if (w < h) {

swap (w, h);

}

ans = ( w >= 3 * h ? h : max (h / 2, w / 3) );

cout << fixed << setprecision(4) << ans;

}

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
 
int main() {
    double h, w, tmp = 0,  ans = 0;
    cin >> h >> w;
    if (w < h) {
        tmp = h;
        h = w;
        w = tmp;
    }
    if (w >= 3 * h) {
        ans = h;
    }
    else {
        ans = max (h / 2, w / 3);
    }
    cout << fixed << setprecision(4) << ans;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double h, w, tmp = 0, ans = 0;

cin >> h >> w;

if (w < h) {

tmp = h;

h = w;

w = tmp;

}

if (w >= 3 * h) {

ans = h;

}

else {

ans = max (h / 2, w / 3);

}

cout << fixed << setprecision(4) << ans;

}

Алгоритм решения

Допустим, что [latex] w [/latex] всегда больше чем [latex] h [/latex] . Из условия следует, что варианта расположения данных квадратов два:

В первом случае ответом будет [latex] \max\left ( \frac{h}{2}, \frac{w}{3} \right ) [/latex]. Во втором же, ответом будет [latex] h [/latex] .

Детали реализации

В первом коде программы используется используется библиотека
#include <algorithm> , которая включает в себя функцию swap() , так же, используется библиотека #include <cmath> , которая включает в себя функцию max() .
Для вывода ответа с точностью не меньше трех десятичных знаков используется библиотека
#include <iomanip> и манипуляторы fixed и setprecision() .