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 
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 ≤ M ≤ N ≤ 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 |
sim |
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");
}
}
Input
2 7 4 3 2
7 3 2
5 3
2 7 4 3 2
2 4 7
Output
nao