Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2592
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2592
VaiNaSort
By Ricardo Martins, IFSULDEMINAS 
Brazil
Timelimit: 1
Professor Odracir Snitram studied various methods of ordering, as well as their respective complexities. One day, he decides to make a test, creating a method, with a box and N stones, numbered from 1 to N. The idea was to draw all the stones, one at a time, so that the sequence of numbers drawn was exactly 1 to N, that is, by drawing the number 1 first, then the number 2, then the 3, and so on, until the last one, which would be N. After drawing everything, if the attempt did not work, all the stones were Returned in the box, and the draw began again until it worked out. This method was named VaiNaSort!
Write a program that, given the amount of stones, and all attempts until you draw correctly, count the attempts.
Input
The input has several test cases. Each one starts with an integer N (2 ≤ N ≤ 10000), representing the amount of stones in the box. Next, there will be a few draw attempts, each formed with the numbers from 1 to N, in any order, until the expected order is achieved. The entry ends with N = 0.
Output
For each test case, print the total number of attempts.
| Input Sample | Output Sample |
|
3 |
4 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdbool.h>
bool verificaOrd(short vet[], short cmp[], unsigned short tam);
int main (void)
{
unsigned short numero, i;
unsigned short qtsOrd;
bool resultado;
while (true)
{
scanf("%hu", &numero);
if (numero == 0)
break;
short caixa[numero];
short cmp[numero];
// Enche um vetor comparação com números que vão de 1 até n;
for (i = 0; i < numero; i++)
cmp[i] = i+1;
// Quantidade de tentativas já começa com 1
// Pois mesmo que na primeira tentativa já fique ordenado
// Gastou uma tentativa;
qtsOrd = 1;
do
{
// Enche o vetor principal com a entrada do usuário;
for (i = 0; i < numero; i++)
scanf("%hu", &caixa[i]);
// Variável resultado recebe a resposta da função que verifica a ordenação;
resultado = verificaOrd(caixa, cmp, numero);
// Se não estiver ordenado;
// Quantidade de tentativas aumenta 1;
if (!resultado)
qtsOrd++;
} while (!resultado);
printf("%hu\n", qtsOrd);
}
}
bool verificaOrd(short vet[], short cmp[], unsigned short tam)
{
unsigned short i;
// Se encontrar um número diferenta em posições iguais, o vetor não
// Está ordenado e a função retorna falso;
for (i = 0; i < tam; i++)
if (vet[i] != cmp[i])
return false;
return true;
}
Input
2 1 3
3 2 1
3 1 2
1 2 3
4
1 2 3 4
0
Output
#2 Code Example with Python Programming
Code -
Python Programming
while True:
n = int(input())
if n == 0:break
cont = 0
while True:
m = list(map(int,input().split()))
if m == sorted(m):
cont += 1
print(cont)
break
else:cont += 1
Input
2 1 3
3 2 1
3 1 2
1 2 3
4
1 2 3 4
0
Output