e-olymp 1494. Санта Клаус

09/05/2018 by Томас Пасенченко

Задача

Санта Клаус

Санта Клаус готовится к Рождеству. В этот праздник он хочет вручить подарки [latex]n[/latex] детям. Его помощники Эльфы уже собрали два мешка, с которыми он отправится в новогоднее путешествие по всем странам мира. И чтобы Санта не запутался, Эльфы составили список детей, чьи подарки уже лежат в каждом из мешков. Санта хочет помочь Эльфам, и поэтому решил положить в третий мешок подарки для тех детей, которым они еще не подготовлены.

Помогите Санте, составьте список детей, чьи подарки надо положить в третий мешок.

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

Первая строка входного файла содержит три целых числа: [latex]n[/latex] — число детей, [latex]m[/latex] и [latex]k[/latex] — число подарков в первом и втором мешке соответственно [latex](1\leq n,\;m,\;k\leq 100;m+k\leq n)[/latex]. Вторая строка входного файла содержит [latex]m[/latex] целых чисел — номера детей, подарки для которых лежат в первом мешке. Третья строка входного файла содержит [latex]k[/latex] целых чисел — номера детей, подарки для которых лежат во втором мешке.

Гарантируется что Эльфы положили для каждого ребенка не более одного подарка. Номера всех детей являются целыми положительными числами не превосходящими [latex]n[/latex]. Все дети должны получить подарок на Рождество, иначе Санта расстроится.

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

В первой строке выведите одно число [latex]a[/latex] — сколько подарков должно быть в третьем мешке. Во второй строке выведите в произвольном порядке [latex]a[/latex] чисел — номера детей, которым эти подарки должны быть доставлены.

Тесты

Входные данные	Выходные данные
2 1 1 2 1	0
3 1 2 1 2 3	0
7 2 1 7 3 1	4 2 4 5 6
100 14 4 2 93 30 56 17 19 75 22 23 5 49 11 8 33 91 40 81 54	82 1 3 4 6 7 9 10 12 13 14 15 16 18 20 21 24 25 26 27 28 29 31 32 34 35 36 37 38 39 41 42 43 44 45 46 47 48 50 51 52 53 55 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 76 77 78 79 80 82 83 84 85 86 87 88 89 90 92 94 95 96 97 98 99 100
10 3 5 2 5 8 3 7 1 4 9	2 6 10
61 40 5 61 20 5 3 4 9 8 49 31 20 33 35 34 61 1 32 53 51 7 21 44 46 47 2 60 50 19 25	36 5 6 10 11 12 13 14 15 16 17 18 22 23 24 26 27 28 29 30 36 37 38 39 40 41 42 43 45 48 52 54 55 56 57 58 59
12 3 3 1 2 3 11 10 8	6 4 5 6 7 9 12

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

#include <iostream>
using namespace std;

int main() {
    int n, m, k, num;
    cin >> n >> m >> k;
    bool children[n];
    for (int i = 0; i < n; i++) {
        children[i] = false;
    }
    for (int i = 0; i < m + k; i++) {
        cin >> num;
        num--;
        children[num] = true;
    }
    cout << (n - m - k) << "\n";
    for (int i = 0; i < n; i++) {
        if (!children[i]) {
            cout << (i + 1) << " ";
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, k, num;

cin >> n >> m >> k;

bool children[n];

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

children[i] = false;

}

for (int i = 0; i < m + k; i++) {

cin >> num;

num--;

children[num] = true;

}

cout << (n - m - k) << "\n";

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

if (!children[i]) {

cout << (i + 1) << " ";

}

return 0;

}

Решение

Создадим массив типа bool , в котором каждому [latex]i[/latex]-ому ребёнку соответствует элемент с индексом [latex]i — 1[/latex], принимающий значение [latex]0[/latex], если для ребёнка ещё нет подарка, и [latex]1[/latex], если подарок уже имеется в одном из мешков. Далее, отмечаем детей, подарки для которых уже лежат в мешках. Наконец, выводим номера тех детей, подарки для которых не были найдены ни в одном из мешков.

Ссылки

Условия задачи на e-olymp
Код задачи на ideone

Related Images:

e-olymp 1489. Шоколад

13/04/2018 by Илья Черноморец

Задача

Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник $n \cdot m$, который полностью состоит из маленьких шоколадных долек — прямоугольников $2 \cdot 1$.

Петя делит шоколадку на две части, разламывая ее вдоль некоторой прямой, параллельной одному из краев шоколадки. Ни Петя, ни Маша не любят ломаные дольки, поэтому Петя хочет разломать шоколадку так, чтобы ни одна долька не была повреждена.

Помогите Пете поделиться шоколадкой с Машей.

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

В первой строке входного файла два целых числа $n$ и $m$ ($1 \le n, m \le 20$, хотя бы одно из чисел $n$ и $m$ — четно). Далее следуют $n$ строк по $m$ чисел в каждой — номера долек, в которые входят соответствующие кусочки шоколадки. Дольки имеют номера от $1$ до $\frac{n \cdot m}{2}$, и никакие две дольки не имеют одинаковые номера.

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

В выходной файл выведите «$Yes$», если Петя может разломать шоколадку, не повредив дольки. Иначе выведите «$No$».

TESTS

Входные данные	Выходные данные
2 3 1 1 2 3 3 2	Yes
5 6 1 2 2 3 3 4 1 5 6 7 7 4 8 5 6 9 10 10 8 11 11 9 12 13 14 14 15 15 12 13	No
4 7 1 1 2 5 8 11 6 2 14 4 7 3 9 5 3 7 10 6 13 2 3 4 3 8 12 5 7 7	Yes

Код решения

#include <iostream>
using namespace std;


bool BreakRow (int **chocolate, int n, int m){
  for (int i = 0; i < n - 1; i++){
    bool okRow = true;
    for (int j = 0; j < m; j++){
      if(chocolate[i][j] == chocolate [i + 1][j]){okRow = false;break;}
    }
    if (okRow) return true;
  }
  return false;
}
bool BreakColumn (int **chocolate, int n, int m){
  for (int i = 0; i < m - 1; i++){
    bool okColumn = true;
    for (int j = 0; j < n; j++){
      if(chocolate[j][i] == chocolate[j][i + 1]){okColumn = false;break;}
    }
    if (okColumn) return true;
  }
  return false;
}

int check (int **chocolate, int n, int m){
  if ( BreakRow(chocolate, n, m) || BreakColumn (chocolate, n, m)) cout<<"Yes";
  else cout<<"No";
}

int main() {
  int n, m;
  cin >> n >> m;
  int **chocolate = new int* [n];
  for(int i = 0; i < n; ++i){
    chocolate[i] = new int[m];
  }
  for( int i = 0; i < n;  i++){
    for(int j = 0; j < m; j++){
      cin >> chocolate [i][j];
    }
  }
  check(chocolate, n, m);
  return 0;
}

#include <iostream>

using namespace std;

bool BreakRow (int **chocolate, int n, int m){

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

bool okRow = true;

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

if(chocolate[i][j] == chocolate [i + 1][j]){okRow = false;break;}

}

if (okRow) return true;

}

return false;

}

bool BreakColumn (int **chocolate, int n, int m){

for (int i = 0; i < m - 1; i++){

bool okColumn = true;

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

if(chocolate[j][i] == chocolate[j][i + 1]){okColumn = false;break;}

}

if (okColumn) return true;

}

return false;

}

int check (int **chocolate, int n, int m){

if ( BreakRow(chocolate, n, m) || BreakColumn (chocolate, n, m)) cout<<"Yes";

else cout<<"No";

}

int main() {

int n, m;

cin >> n >> m;

int **chocolate = new int* [n];

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

chocolate[i] = new int[m];

}

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

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

cin >> chocolate [i][j];

}

check(chocolate, n, m);

return 0;

}

Решение

Для решения данной задачи нужно представить шоколадку как двухмерный массив и проверить, можно ли разломать плитку шоколада ровно, то есть одинаковое ли количество «строк» и «столбцов» шоколада. Если так, то возвращается значение true, и false в обратном случае. Для этого были созданы функции BreakRow и BreakColumn с возвращаемым значением типа bool. Затем стоит проверить возвращаемое значение. Если одна из функций принимает значение true, то выводим положительный ответ. В противном случае ответ отрицательный.

Ссылки

Условие решения на e-olymp.com
Код решения на ideone.com

Related Images:

А413б

27/11/2014 by Бровко Ілля

Задача

Таблица футбольного чемпионата задана квадратной матрицей порядка [latex]n[/latex], в которой все элементы, принадлежащие главной диагонали, равны нулю, а каждый элемент, не принадлежащий главной диагонали, равен [latex]2[/latex], [latex]1[/latex] или [latex]0[/latex] (числу очков, набранных в игре: [latex]2[/latex]- выигрыш, [latex]1[/latex]- ничья, [latex]0[/latex]- проигрыш).

б) Определить номера команд, прошедших чемпионат без поражений.

Количество команд.

Турнирная таблица.

Номера команд, прошедшие турнир без поражений.

Комментарий.

0	2	0	1
0	0	1	2
2	1	0	1
1	0	1	0

Пройдено.

0	1	2	2
1	0	2	2
0	0	0	1
0	0	1	0

1 2

Пройдено.

0	2	0
0	0	2
2	0	0

Ни одна из команд не прошла турнир без поражений.

Пройдено.

0	2	1	1
0	0	1	2
1	1	0	2
1	2	2	0

1 3 4

Пройдено.

От нас требуют определить номера команд, прошедших чемпионат без поражений. Турнирная таблица, которую нам следует проверить, имеет вид матрицы, где строки- это очки набранные командой, а столбцы- сами команды. Всего у нас столько команд, сколько элементов в столбце. Т.к команда не может играть сама с собой, диагональные элементы равны [latex]0[/latex].

Для начала вводим двумерный массив. Далее, в циклах, проверяем на наличие у команды поражения: для не диагональных элементов ([latex]i\neq j[/latex]), если команда хотя бы один раз проиграла, цикл обрывается и команда в дальнейшей проверке не участвует.

Если ни одна команда не прошла турнир без поражений, то для этого заводим счетчик [latex]k[/latex]. Если [latex]k>0[/latex], то хотя бы одна команда прошла турнир без поражений. Если [latex]k=0[/latex], то ни одна из команд не прошла без поражений.

Ниже представлен сам код (C++).

#include <iostream>
#include <vector>
using namespace std;
 
int main() 
{
	int n, k=0;
	bool win;
	cin>>n;
	int A[n][n];
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			cin>>A[i-1][j-1];							//ввод турнирной таблицы (матрицы)
		}
	}
	cout<<"Номера команд, прошедших чемпионат без поражений:";
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			if(i!=j)
			{
				if(A[i-1][j-1]==0)
				{
					win=false;
					break;							//проверка матрицы на проигравшие команды.
				}
				win=true;
			}
		}
		if(win==true)
		{
			cout<<" "<<i;
			k+=1;										//печать команд, прошедших чеспионат без поражений.
		}												//если таких команд нет, то для этого заведен специальный счетчки.
	}
	if(k==0)
	{
		cout<<"	ни одна из команд не прошла турнир без поражений.";
	}
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int n, k=0;

bool win;

cin>>n;

int A[n][n];

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

{

for(int j=1; j<=n; j++)

{

cin>>A[i-1][j-1]; //ввод турнирной таблицы (матрицы)

}

cout<<"Номера команд, прошедших чемпионат без поражений:";

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

{

for(int j=1; j<=n; j++)

{

if(i!=j)

{

if(A[i-1][j-1]==0)

{

win=false;

break; //проверка матрицы на проигравшие команды.

}

win=true;

}

if(win==true)

{

cout<<" "<<i;

k+=1; //печать команд, прошедших чеспионат без поражений.

} //если таких команд нет, то для этого заведен специальный счетчки.

}

if(k==0)

{

cout<<" ни одна из команд не прошла турнир без поражений.";

}

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Brovko
{
	public static void main (String[] args) throws java.lang.Exception
{
	int n, k=0;
	boolean win=true;
	Scanner in = new Scanner(System.in);
	n=in.nextInt();
	int[][] A = new int[n][n];
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			A[i-1][j-1]=in.nextInt();							//ввод турнирной таблицы (матрицы)
		}
	}
	System.out.printf("Номера команд, прошедших чемпионат без поражений:");
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			if(i!=j)
			{
				if(A[i-1][j-1]==0)
				{
					win=false;
					break;							//проверка матрицы на проигравшие команды.
				}
				win=true;
			}
		}
		if(win==true)
		{
			System.out.print(" ");
			System.out.format("%d ",i);
			k+=1;										//печать команд, прошедших чеспионат без поражений.
		}												//если таких команд нет, то для этого заведен специальный счетчки.
	}
	if(k==0)
	{
		System.out.print(" ни одна из команд не прошла турнир без поражений.");
	}
}
}