Ալգորիթմներ և Տվյալների Կառուցվածքներ

Պարողների զուգակցում

Տրված են n տղամարդ և k կին, որոնց պարային ունակությունները համապատասխանաբար տրված են և ։ Ցանկանում եք նրանց բաժանել զույգերի այնպես, որ յուրաքանչյուր զույգի ունակությունների մակարդակների տարբերությունը չգերազանցի 1-ը։

Քանի՞ զույգ է հնարավոր կազմել այս պարային մրցույթի համար:

dancers.webp

Մուտք

Մուտքի առաջին տողում տրված է երկու ամբողջ թիվ n և k (1 ≤ n, k ≤ ):

Հաջորդ տողում տրվում են n ամբողջ թվեր (1 ≤ ≤ 100), որոնք բաժանված են բացատներով:

Երրորդ տողում տրվում են k ամբողջ թվեր (1 ≤ ≤ 100), որոնք նույնպես բաժանված են բացատներով:

Ելք

Ծրագիրը պետք է տպի հնարավոր ամենաշատ զույգերի քանակը, որն հնարավոր է ստանալ մուտքում տրված տվյալներով:

Օրինակներ

Մուտք

Ելք

4 5
2 4 6 3
5 1 5 7 10

3

4 4
1 2 3 4
51 52 53 54

0

5 3
2 2 2 2 2
2 3 4

2

Բացատրություն

  1. Կազմում ենք զույգեր այսպես → 2 ↔ 1, 4 ↔ 5 և 6 ↔ 5

  2. Անհնար է որևէ զույգ կազմել

  3. Կազմում ենք զույգեր այսպես → 2 ↔ 2 և 2 ↔ 3

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue