Uzb Eng

C15C. Perestanovka
: 2 c
: 64

TATU talabasi Abdulla informatika fanidan masalalar ishlashga juda ham qiziqadi. U yaqinda codeforces.ru saytidan Farqli perestanovka masalasini ishlaganda vaqt limiti oldi. Bu masala sharti quyidagicha: Perestanovka p deb n ta bir-biridan farqli va qiymati 1<= pi <=n oraliqda bolgan musbat butun sonlardan tashkil topgan p1, p2, , pn ketma-ketlikka aytiladi. n bu p1, p2, , pn perestanovkaning uzunligini bildiradi. Sizning vazifangiz uzunligi n ga teng bolgan shunday p ning perestanovkasini topingki bunda |p1-p2|, |p2-p3|, ..., |pn-1-pn| qiymatlar toplami k ta bir biridan farqli sonlardan iborat bolsin. Bu masalani Abdulla quyidagicha ishladi, va uning do{}while(); qismi necha marta ishlaganini tekshirish maqsadida buni count ozgaruvchisida sanadi :
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
int count = 0;
void solve(int n, int k){
	int *a = new int[n];
	for(int i = 0; i < n; i ++) a[i] = i + 1;
	setb;
	do{
		b.clear();
		count ++;
		for(int i = 1; i < n; i ++) b.insert(abs(a[i] - a[i-1]));
		if(b.size() == k) return break;
	}while(next_permutation(a,a+n));
	for(int i = 0; i < n; i ++) cout << a[i] <<  ;
}
int main(){
 	int n, k;
	cin >> n >> k;
	solve(n,k);
	return 0;
}
Abdulla bu yechimi oxirida cout << count; qoyib count ning oxirgi natijasini kormoqchi boldi. Ammo uning dasturi juda sekin ishlashi bois kop natijalarni juda sekin topyapti. Abdullaga dasturi tugaganida count ning oxirgi qiymatini topishga yordam bering.

:
Bitta qatorda 2 ta butun n va k soni kiritiladi (1 <= k < n);

:
Bitta butun son count ning dastur nihoyasidagi qiymatini chiqaring. Bunda qiymat juda katta bolib ketishi mumkin shuning uchun uni 1000000007 (1e9 + 7) ga bolgandagi qoldiqni chiqaring.

3 2
3 1
5 2
5 4
2
1
2
20
: Kombinatorika
: Sunnat TUIT


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.