Woburn Challenge 2017-18 Finals Round - Junior Division

Problem 1: Cownterintelligence

The Great Cow-Monkey War of 2017 has left Scarberia in a fragile and unstable state. Interspecies tension is at an all-time high, and both sides are working relentlessly to rebuild their economies, social systems, and militias. Little do the cows and monkeys know that, amidst the turmoil, the world is at risk of being taken over by an even more dangerous foe — a group of aliens known as the Party of Extraterrestrial Gangsters (or PEG for short)! PEG has decided that it's the perfect time to divide and conquer Scarberia by exploiting its current internal hostilities.

Prior to their invasion, PEG would like to obtain some intel on the military of each group, starting with the cows. The entire cow army consists of N (1 ≤ N ≤ 100) soldiers numbered from 1 to N. PEG has sent S (0 ≤ S ≤ N) spies to infiltrate the cow army. Each of the spies has chosen a distinct cow soldier to abduct and steal the identity of. In other words, S of the N cow soldiers are now secretly imposters.

The commander of the cow army, Bo Vine, is a sharp leader. Recently, he has sensed something amiss with his subordinates and would like to find out if his army has been compromised. Being one of the greatest military strategists of our time, he had long planned for the day that something like this might happen. During the inception of the cow army, a secret system to identify spies was established. This system is based on the fact that all real cows have perfect pitch, and can moo at any musical frequency at will. In the past, Bo Vine had chosen a single secret musical note to share with every cow soldier on the first day of basic training. The fundamental frequency of the secret note to moo is F (1 ≤ F ≤ 10000) Hz, where F is an integer. When questioned, they must moo this note or be revealed as a spy.

Bo Vine has questioned all of the cows individually and gathered some data. He has recorded that the cow numbered i moos at a frequency of M_i (F ≤ M_i ≤ 10000) Hz, where M_i is an integer. However, upon inspecting the data, Bo Vine has noticed a big problem with his plan. He realized that he had only told the name of the secret note to the cows, and not its exact frequency. He forgot that the same musical note can be mooed in different octaves, and hence may have different frequencies. Thus, each real cow soldier could have mooed the secret note at frequency F, or at some higher octave with a frequency larger than the fundamental frequency F.

To give you a little background in music theory, pitches that are octaves above a given fundamental pitch will have frequencies 2x, 4x, 8x, and all other powers of two times the fundamental frequency. For example, if Bo Vine chose the secret note to be A at 440 Hz as the fundamental frequency, then any cows mooing at frequencies 440 Hz, 880 Hz, 1760 Hz, 3520 Hz, etc. should be deemed to be real cow soldiers. Any other frequency is indicative of an imposter! Given the fundamental frequency and the moo frequency of every cow soldier, please help Bo Vine identify which of them are actually alien imposters.

Subtasks

In test cases worth 5/10 of the points, F = 1 and 1 ≤ M_i ≤ 3 for each i.

Input Format

The first line of input consists of two space-separated integers, N and F.
N lines follow, the i-th of which consists of a single integer, M_i, for i = 1..N.

Output Format

Output S lines with a single integer per line, the numbers of all of the cows that are deemed to be imposters. You should output these numbers in ascending order.

Sample Input

6 440
880
500
3520
441
1320
440

Sample Output

2
4
5

Sample Explanation

There are 6 cow soldiers. Cows numbered 2, 4, and 5 mooed at frequencies 500 Hz, 441 Hz, and 1320 Hz respectively, which are not power-of-2 multiples above the fundamental frequency of 440 Hz.

All Submissions
Best Solutions

Point Value: 5 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 13, 2018
Author: Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)