0730

//20210730 backtracking,recursive,dfs
//1
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int N,ans,cnt;
int sum,S;
 int arr[21];
//cnt :number of chosen numbers
bool print( int arr[], bool select[],int cnt,int curr){
	int sum=0;
	for(int i=0;i<N;i++){
		if(select[i]==true)
			{sum+=arr[i];
			cout<<arr[i];}
	}
	cout<<":"<<curr<<":"<<cnt<<'\n';
	//cout<<" "<<sum<<" ";
	if(sum==S) {cout<<"0이다";return true;}
	return false;
}
void recursion(int curr,int cnt, int arr[],bool select[]){ 
	if(cnt>=1&&print(arr,select,cnt,curr)) {ans++;}
	if(cnt==N) {return;}
	for(int i=curr;i<N;i++){
		if(select[i]==true) continue;
		  select[i]=true;
		  cnt++;
	    recursion(curr+1,cnt,arr,select);
	    cnt--;curr++;
	    select[i]=false;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin>>N>>S;
 memset(arr, 0, sizeof(arr));
	bool select[N]={false};
	for(int i=0;i<N;i++){
		cin>>arr[i];
	}
	sort(arr,arr+N);
	recursion(0,0,arr,select);
	cout<<"답"<<ans;
	return 0;
}
//2
#include<stdio.h>
int arr[20], n, s, ans = 0;
void dfs(int idx, int sum) {
	if (sum + arr[idx] == s) ans++; if (idx >= n - 1)return; dfs(idx + 1, sum); dfs(idx + 1, sum + arr[idx]);
}
int main(void) {
	scanf("%d %d", &n, &s); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); dfs(0, 0); printf("%d", ans);
}
//0807
//15513
//나눗셈을 사용하지 말 것 -> 오차 발생 --> 구조체 사용  
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;vector<pair<long double,int>> v;
vector <int> vec;
bool compare(pair<long double,int> a,pair<long double,int> b){
   if((a.first==b.first)&&a.second<b.second) return true;
   if(a.first>b.first) return true;
   return false;
}
int main() {
   cin>>N;int w=0,q=0;
   long double p=0;
   for(int i=1;i<=N;i++) {
      cin>>w>>q;
      p=1-(long double)q/10000.0;
      v.push_back({w/p,i});
   }
   sort(v.begin(),v.end(),compare);
   for(auto i : v)
      cout<<i.second<<" ";
   return 0;
}