Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2530

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2530

Cheating

 

By Flávio Zavan, UFPR BR Brazil

Timelimit: 1

Students in the 4th grade of the Trale Lewous School took a Math exam in the beginning of the day. Everyone handed over a sheet containing only their answers and the respective indices. Teacher Maria Eduarda suspects that Ricardinho copied his answers from Juan, the best student in the class.

Ricardinho was called to talk with the teacher during the break time, in order to check if he really cheated or not. However, afraid of being caught, the prankish boy distracted the teacher and erased the indices of his answers. Hence, if the sheet contained initially "1) 20 2) 30 3) 35 ...", now it contains only "20 30 35 ...".

The exam was composed of N questions, which answers were always numbers. However, the boy answered only M of them. The teacher is sure that Ricardinho wrote down his answers in order, i.e., if he answered, for example, questions 2 and 4, then the answer for question 2 is wrote before the answer for question 4.

With all the N answers gave by Juan, also in order, Maria Eduarda will nullify Ricardinho’s exam if there is some way to match the value of the M answers given by Ricardinho with M of the N answers given by Juan, respecting their orders.

Write a program that, given the answers of both boys, determine if Ricardinho’s exam must be nullified.

 

Input

 

The input contains several test cases. The first line of each test case contains two integers N and M (1 ≤ MN ≤ 105). The second line contains N integers si (1 ≤ si ≤ 103) describing Juan’s answer. The third line contains M integers rj (1 ≤ rj ≤ 103) describing Ricardinho’s answers.

The input ends with end-of-file (EOF).

 

Output

 

For each test case, print a line containing "sim" if the exam must be nullified or "nao" otherwise (without quotes).

 

 

 

Input Sample Output Sample

5 3
2 7 4 3 2
7 3 2
5 3
2 7 4 3 2
2 4 7

sim
nao

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>

#define true 1
#define false 0
#define MAXSIZE 100100


int main (void)
{

	unsigned i, j;
	unsigned n, m;
	unsigned juan[MAXSIZE];
	unsigned ricardinho[MAXSIZE];

	while (scanf("%u %u", &n, &m) != EOF)
	{

		for (i = 0; i  <  n; ++i)
			scanf("%u", &juan[i]);

		for (i = 0; i  <  m; ++i)
			scanf("%u", &ricardinho[i]);

		i = j = 0;
		while (i  <  m && j < n)
		{

			if (ricardinho[i] == juan[j])
				++i;

			++j;

		}

		if (i == m)
			printf("sim\n");
		else
			printf("nao\n");

	}


}
Copy The Code & Try With Live Editor

Input

x
+
cmd
5 3
2 7 4 3 2
7 3 2
5 3
2 7 4 3 2
2 4 7

Output

x
+
cmd
sim
nao
Advertisements

Demonstration


Previous
#2523 Beecrowd Online Judge Solution 2523 Will's Message Solution in C, C++, Java, Js and Python
Next
#2533 Beecrowd Online Judge Solution 2533 Internship Solution in C, C++, Java, Js and Python