Algorithm
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1252
Hmm! Here you are asked to do a simple sorting. You will be given N numbers and a positive integer M. You will have to sort the N numbers in ascending order of their modulo M value. If there is a tie between an odd number and an even number (that is their modulo M value is the same) then the odd number will precede the even number. If there is a tie between two odd numbers (that is their modulo M value is the same) then the larger odd number will precede the smaller odd number and if there is a tie between two even numbers (that is their modulo M value is the same) then the smaller even number will precede the larger even number. For remainder value of negative numbers follow the rule of C programming language: A negative number can never have modulus greater than zero. E.g. -100 MOD 3 = -1, -100 MOD 4 = 0 etc.
Input
The input file contains many sets of inputs. Each set starts with two integers N (0 < N ≤ 10000) and M (0 < M ≤ 10000) which denotes how many numbers are within this set. Each of the next N lines contains one number each. These numbers should all fit in 32-bit signed integer. Input is terminated by a line containing two zeroes.
Output
The first line of each set contains the value of N and M. The next N lines contain N numbers, sorted according to the rules mentioned above. Print the last two zeroes of the input file in the output file also.
| Sample Input | Sample Output |
|
15 3 |
15 3 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <iostream<
#include <algorithm>
using namespace std;
int M;
bool comp (int a, int b){
if (b%M == a%M){ /// retorna primeiro os impares e depois os pares;
if(abs(a)%2 ==abs(b)%2){ ///comparando dois pares ou dois impares
if (a%2 != 0){ ///impares
return a > b;
}else{ ///a e b s?o pares
return b > a;
}
}
return abs(a)%2 > abs(b)%2; /// impares antes dos pares
}
return a%M < b%M;
}
int main()
{
int N, cont;
scanf("%d", &N);
scanf("%d", &M);
while(N!=0 && M!=0)
{
int vetor[N];
printf("%d %dn", N, M);
for(cont=0;cont < N;cont++){
scanf("%d", &vetor[cont]);
}
sort(vetor,vetor+N,comp);
for(cont=0;cont < N;cont++){
printf("%dn", vetor[cont]);
}
scanf("%d", &N);
scanf("%d", &M);
}
printf("0 0n">;
return 0;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include<bits/stdc++.h>
using namespace std;
int m;
bool comp (int a, int b){
if (b%m == a%m)
if(abs(a)%2 ==abs(b)%2){
if (a%2 != 0){
return a > b;
}else{
return b > a;
}
}
return abs(a)%2 > abs(b)%2;
}
return a%m < b%m;
}
int main()
{
int n;
while(cin>>n>>m&&n&&m){
int a[n];
for(int i=0;i < n;i++)
{
cin>>a[i];
}
sort(a,a+n,comp);
cout<<n<<" "<<m<<endl;
for(int i=0;i < n;i++)
cout<<a[i]<<endl;
}
printf("0 0n">;
}
Input
Output