fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3. typedef long long int ll;
  4. int main()
  5. {   
  6.  
  7. 	ios_base::sync_with_stdio(false);
  8.     cin.tie(NULL);
  9.     cout.tie(NULL);
  10.     ll t;ll o=1;
  11.     cin>>t;
  12.     while(t--)
  13.     {
  14.         ll n;
  15.         cin>>n;
  16.         if(n==1)
  17.         {
  18.         	ll x,y;
  19.             cin>>x>>y;
  20.             cout<<"Case #";
  21.             cout<<o;
  22.             o++;
  23.             cout<<": ";
  24.             cout<<"0 ";
  25.             cout<<x;
  26.         }
  27.         else
  28.         {
  29.             ll e[n+1],r[n+1];
  30.             ll i = 1;
  31.             while(i<=n)
  32.             {
  33.             	cin>>e[i]>>r[i];
  34.                 i++;
  35.             }
  36.  
  37.     //Generating all subsets
  38.     long long int d;
  39. 	d=pow(2,n);
  40. 	long long int j;
  41. 	i=0;
  42. 	ll e2[50];
  43.     ll r2[50];
  44. 	i=0;
  45. 	while(i<=49)
  46. 	{
  47.  
  48. 	    e2[i]=0;
  49. 	    r2[i]=0;
  50. 	    i++;
  51. 	}
  52. 	ll max2=-1;
  53. 	ll op=1e18;
  54. 	ll jee=1e18;
  55. 	i=0;
  56. 	while(i<d)
  57. 	{
  58.  
  59.  
  60. 	    j=1;  
  61.         ll count=0;ll ram=1;
  62.         while(j<=n)
  63.         {
  64.  
  65.  
  66.  
  67.  
  68.             if( i & (1<<(j-1))  )
  69.             {
  70.             e2[ram]=e[j];
  71.             r2[ram]=r[j];
  72.             ram++;
  73.             count++;
  74.             }
  75.             else
  76.             {
  77.             }
  78.  
  79.  
  80.  
  81.         j++;
  82.         }
  83.  
  84.  
  85.  
  86. 	if(count==0)
  87. 	{
  88.  
  89. 	}
  90. 	else
  91. 	{
  92.  
  93. 	    ll left = n-count ; 
  94.         ll sum=e2[1];
  95.         ll i1=2;
  96.         while(i1<=ram)
  97.         {
  98.             sum=sum+e2[i1];
  99.             ll x = e2[i1];
  100.             ll jx = 1;
  101.             while(jx<=i1-1)
  102.                 {
  103.  
  104.                     r2[jx]=r2[jx]-x;
  105.  
  106.                     jx++;
  107.                 }
  108.  
  109.                 i1++;
  110.         }
  111.  
  112.             //round___2...
  113.  
  114.         i1=1;ll good=0;
  115.         while(i1<=ram)
  116.         {
  117.  
  118.             if(r2[i1]>0)
  119.             {
  120.                 good=1;
  121.                 i1=1e18;
  122.             }
  123.             else
  124.             {
  125.  
  126.                 sum=sum+e2[i1];
  127.                 ll x = e2[i1];
  128.                 ll jx = i1+1 ;
  129.                 while(jx<=ram)
  130.                 {
  131.  
  132.  
  133.                     r2[jx]=r2[jx]-x;
  134.  
  135.  
  136.                     jx++;
  137.                 }
  138.  
  139.             }
  140.  
  141.  
  142.                 i1++;
  143.         }
  144.  
  145.         if(good==1)
  146.         {
  147.                 //cout<<sum;
  148.  
  149.             if(sum==max2)
  150.             {
  151.  
  152.                 op=min(op,left);
  153.             }
  154.             if(sum>max2)
  155.             {
  156.                 max2=sum;
  157.                 op=left;
  158.             }
  159.  
  160.  
  161.         }
  162.         else
  163.         {
  164.         	jee=min(jee,left);
  165.             //cout<<"INDEFINITELY";
  166.         }
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179. 	}
  180. 	i++;
  181.  
  182.  
  183. 	}
  184.  
  185.  
  186.     cout<<"Case #";
  187.     cout<<o;
  188.     o++;
  189.     cout<<": ";
  190.     if(jee==1e18)
  191.         {
  192.                 cout<<op<<" "<<max2;
  193.         }
  194.     else
  195.         {
  196.                 cout<<jee<<" ";
  197.                 cout<<"INDEFINITELY";
  198.         }
  199.  
  200.     }
  201.  
  202.  
  203.         cout<<"\n";
  204.     }
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.     return 0;
  213. }
Success #stdin #stdout 0s 4432KB
comments (?)
stdin
copy 
4
1
5 1
2
5 10
10 3
3
30 17
5 10
10 3
3
5 10
5 10
5 11
stdout
copy 
Case #1: 0 5
Case #2: 0 INDEFINITELY
Case #3: 1 INDEFINITELY
Case #4: 0 25
https://ideone.com/zKxKGi
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!