e-olymp 4752. Кинотеатр

28/03/2019 by Анна Неделева

Задача

Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера n × m, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.

Школьники заняли свои места следующим образом: они входили в зал в порядке, в котором шли их номера, и полностью занимали сначала первый ряд, потом второй, потом третий и т.д.

Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).

Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.

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

В первой строке заданы числа $n$ и $m$ $(1 ≤ n, m ≤ 1000)$.

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

Выведите одно число — количество учеников, которые в результате пересадки остануться сидеть на тех же местах.

Тесты

№	Входные данные	Выходные данные
1	3 3	3
2	3 4	2
3	6 3	2
4	5 9	5
5	7 5	3

Код программы

#include <iostream>
using namespace std;

int main() {
  int arr[1000][1000], n, m, count1 = 1, count2 = 1, result = 0;
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      arr[i][j] = count1++;
  for (int j = 0; j < m; j++) {
    for (int i = 0; i < n; i++) {
      if (arr[i][j] == count2) result++;
      count2++;
    }
  }
  cout << result << "\n";
}

#include <iostream>

using namespace std;

int main() {

int arr[1000][1000], n, m, count1 = 1, count2 = 1, result = 0;

cin >> n >> m;

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

arr[i][j] = count1++;

for (int j = 0; j < m; j++) {

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

if (arr[i][j] == count2) result++;

count2++;

}

cout << result << "\n";

}

Код программы с линейным массивом

#include <iostream>
using namespace std;
 
int main() {
  int arr[1000 * 1000], n, m, result = 0;
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      arr[i * m + j] = i * m + j;
  for (int j = 0; j < m; j++) 
    for (int i = 0; i < n; i++) 
      if (arr[i * m + j] == j * n + i) result++;
  cout << result << "\n";
}

#include <iostream>

using namespace std;

int main() {

int arr[1000 * 1000], n, m, result = 0;

cin >> n >> m;

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

arr[i * m + j] = i * m + j;

for (int j = 0; j < m; j++)

for (int i = 0; i < n; i++)

if (arr[i * m + j] == j * n + i) result++;

cout << result << "\n";

}

Код программы без массива

#include <iostream>
using namespace std;
 
int main() {
  int n, m, result = 0;
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (i * m + j == j * n + i) result++;
  cout << result << "\n";
}

#include <iostream>

using namespace std;

int main() {

int n, m, result = 0;

cin >> n >> m;

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

if (i * m + j == j * n + i) result++;

cout << result << "\n";

}

Решение задачи

Для решения задачи проверяем значения до пересадки и после, если они совпадут соответственно, то инкрементируем счётчик. А в конце выводим результат.

Ссылки

Related Images:

e-olymp 2061. Юные программисты

19/10/2018 by Кирилл Веремйов

Задача

Известно, что в школе не менее чем $k_{1}$учеников, но не более чем $k_{2}$ учеников. Также известно, что каждый мальчик дружит с $n$ девочками, а каждая девочка с $m$ мальчиками. Какое минимальное количество учеников может быть в школе, и сколько в школе мальчиков и девочек?

Юные программисты, как Вы видите, до сих пор решают эту задачку. Помогите им.

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

В первой строке входного файла находится $4$ числа, разделённых пробелами: $k_{1}$, $k_{2}$, $n$ и $m$. Все входные данные натуральные числа, не превышающие $10000$, $k_{1}\leq k_{2}$.

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

В единственной строке вывести через пробел три числа: сначала количество учеников в школе, потом количество мальчиков и затем девочек. Гарантируется, что входные данные корректны и ответ всегда существует.

Тесты

Входные данные	Выходные данные
20 30 4 5	27 15 12
5 10000 54 44	98 44 54
1 10000 100 100	200 100 100
1 2 1 1	2 1 1
100 120 2 3	100 60 40
50 50 25 25	50 25 25
9900 10000 99 56	9920 3584 6336
9999 10000 9998 2	10000 2 9998
101 110 2 3	105 63 42

Решение

#include <iostream>
using namespace std;
 
int main() {
    int k1, k2, m, n; 
    int x = 0, y = 0, M = 10001; 
//x-мальчики, y-девочки, M- минимальное из вариантов количества учеников (10001 сначала, чтобы первый раз прошло условие внутри цикла) 
    cin >> k1 >> k2 >> n >> m; 
 
    for(int i = 0; i <= k2; i++){
        for(int j = k1-i; j <= k2; j++){ //j=k1-i, так как сумма i+j должна быть хотя бы k1. Рассматривать варианты меньше, смысла не имеет
/* M>i+j— если сумма меньше предыдущего из меньших, то перезаписываем переменные, если больше- пропускаем. i*j== количество дружащих пар.
 k1<=i+j — общее число учеников должно быть больше или равно k1 и меньше, либо равно k2 (i+j<=k2). Количество мальчиков в классе должно
 быть больше либо равно количеству, которое требуется девочкам для дружбы (i>=m), аналогично с девочками (i>=n)*/
            if(M > i + j && i * n == j * m  && k1 <= i + j && i + j <= k2 && i>=m && j>=n){ 
                x = i; 
                y = j;
                M = i+j;
            }
        }
    }   
    cout<< x + y << " " << x << " " << y << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k1, k2, m, n;

int x = 0, y = 0, M = 10001;

//x-мальчики, y-девочки, M- минимальное из вариантов количества учеников (10001 сначала, чтобы первый раз прошло условие внутри цикла)

cin >> k1 >> k2 >> n >> m;

for(int i = 0; i <= k2; i++){

for(int j = k1-i; j <= k2; j++){ //j=k1-i, так как сумма i+j должна быть хотя бы k1. Рассматривать варианты меньше, смысла не имеет

/* M>i+j— если сумма меньше предыдущего из меньших, то перезаписываем переменные, если больше- пропускаем. i*j== количество дружащих пар.

k1<=i+j — общее число учеников должно быть больше или равно k1 и меньше, либо равно k2 (i+j<=k2). Количество мальчиков в классе должно

быть больше либо равно количеству, которое требуется девочкам для дружбы (i>=m), аналогично с девочками (i>=n)*/

if(M > i + j && i * n == j * m && k1 <= i + j && i + j <= k2 && i>=m && j>=n){

x = i;

y = j;

M = i+j;

}

cout<< x + y << " " << x << " " << y << endl;

return 0;

}

Объяснение

Решение основано на достаточно простой идее перебора всех вариантов количества мальчиков и количества девочек и нахождения наименьшего из них, удовлетворяющего условию. Для этого создаётся два цикла, внешний из которых отвечает за переменную мальчиков, а внутренний— за переменную девочек. Внутреннее условие находит минимальное количество учеников в классе.

e-olymp

ideone

Related Images:

e-olymp 2061. Юные программисты

30/09/2015 by Андрей Яроцкий

Задача

Известно, что в школе не менее чем [latex]k_1[/latex] учеников, но не более чем [latex]k_2[/latex] учеников. Также известно, что каждый мальчик дружит с [latex]n[/latex] девочками, а каждая девочка с [latex]m[/latex] мальчиками. Какое минимальное количество учеников может быть в школе, и сколько в школе мальчиков и девочек?

Тесты:

№	Ввод	Вывод
1	20 30 4 5	27 15 12
2	40 50 5 4	45 20 25

Код программы:

#include <iostream>
using namespace std;
 
int main() {
   int k1, k2, n, m;
   int b, g; //b-boys;g-girls
   cin >> k1 >> k2 >> n >> m;
   for (g = n; true; g++)
   {
      b = g * m / n;
      if (((g * m) % n) == 0 && b + g >= k1) break; // перебираем варианты пока количество мальчиков не станет целым а сумма всех учеников будет больше k1
   }
   cout << b + g << " " << b << " " << g << endl;
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int k1, k2, n, m;

int b, g; //b-boys;g-girls

cin >> k1 >> k2 >> n >> m;

for (g = n; true; g++)

{

b = g * m / n;

if (((g * m) % n) == 0 && b + g >= k1) break; // перебираем варианты пока количество мальчиков не станет целым а сумма всех учеников будет больше k1

}

cout << b + g << " " << b << " " << g << endl;

return 0;

}

Решение:

Увеличиваем количество девочек на 1 пока количество мальчиков по формуле [latex]b = g \cdot m / n[/latex] не станет целочисельным значением и сумма мальчиков и девочек будет больше или равна минимальному возможному количеству учеников [latex]k_1[/latex].

Условие задачи можно найти на сайте e-olymp.
Ссылка на решение задачи на ideone.com здесь.
Ссылка на полностью решенную задачу здесь.

Related Images:

e-olimp 7365. Молоко и пирожок

30/09/2015 by Настя Ивасенко

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее 30 кг. В первых классах школы учится [latex]n[/latex] учеников. Стакан молока имеет емкость 200 мл, а упаковки молока – 0.9 л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

Тесты

Количество детей	Вес	Количество упаковок молока	Количество пирожков
3	30 29 30	1	1
5	25 41 56 20 20	1	3
4	30 30 30 30	0	0
7	25 26 27 28 29 23 24	2	7

Код

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

int main() {
    int p=0; //пирожки
    int n, k; //количество детей, вес и упаковки молока
    double m, u, w; 
    cin >> n;
    m=0.2; u=0.9;
    for(int i=0; i<n; i++) {
        cin >> w;
        if (w<30) p++;
        if(w>=30) p=p+0;
    }
    k= ceil(p*m/u);
    cout << k << " " << p;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int p=0; //пирожки

int n, k; //количество детей, вес и упаковки молока

double m, u, w;

cin >> n;

m=0.2; u=0.9;

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

cin >> w;

if (w<30) p++;

if(w>=30) p=p+0;

}

k= ceil(p*m/u);

cout << k << " " << p;

return 0;

}

Решение

Возьмем количество пирожков за счетчик. Используя for найдем количество пирожков для детей, вес которых не превышает 30кг.

По количеству пирожков мы можем найти количество упаковок молока. При этом мы можем получить не целое число. Чтобы избежать этого, подключаем библиотеку <cmath> и используем округление вверх ceil .

Посмотреть код на ideone можна здесь.

Проверить правильность на e-olimp можна здесь.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: ученики

e-olymp 4752. Кинотеатр

Задача

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

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

Тесты

Код программы

Код программы с линейным массивом

Код программы без массива

Решение задачи

Ссылки

Related Images:

e-olymp 2061. Юные программисты

Задача

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

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

Тесты

Решение

Объяснение

Related Images:

e-olymp 2061. Юные программисты

Related Images:

e-olimp 7365. Молоко и пирожок

Тесты

Код

Решение

Related Images: