11266 - Equations
Moderator: Board moderators
-
- New poster
- Posts: 20
- Joined: Mon May 28, 2007 4:36 pm
- Location: India
11266 - Equations
can smbd provide me some smple i/o
i have tested it for given i/o as well as some other i/o it is giving correct ans
but when submitted its wrong ans
thanks in advance
i have tested it for given i/o as well as some other i/o it is giving correct ans
but when submitted its wrong ans
thanks in advance
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
Input
Output
Hope it helps.
Code: Select all
3
6 325
10 25
41 255
36 78
10 100
25 125
200 575
8 20
6 6
5 5
-9 -9
8 8
1 1
7 7
-8 -8
10 10
6 -100
-5 -1
0 26
-1000 999
6 14
5 20
7 48
Code: Select all
56
1
16468
Hope it helps.
-
- New poster
- Posts: 20
- Joined: Mon May 28, 2007 4:36 pm
- Location: India
thanks
thanks for the sample i/o
my prog is giving the same output but still i am getting wrong ans
i am posting the code as i have no other option
#include<iostream>
using namespace std;
long long comb(long long n, long long r){
long long a[10], i, j;
for(i=0; i<r; i++) a=n-i;
for(i=r; i>1; i--)
for(j=0; j<r; j++)
if(a[j]%i==0){ a[j]/=i; break; }
i=1;
for(j=0; j<r; j++) i=(i*a[j])%200003;
return i;
}
void swap(long long& a, long long& b){
long long temp=a;
a=b;
b=temp;
}
int main(){
long long s, n, cases, lt[10][2], i, j, k, a, co[1024], d[10], cnt;
cin>>cases;
while(cases--){
cnt=0;
cin>>n>>s;
for(i=0; i<n; i++){
cin>>lt[0]>>lt[1];
if(lt[0]>lt[1]) swap(lt[0], lt[1]);
s-=lt[0];
d=lt[1]-lt[i][0]+1;
}
j=(1<<n);
for(i=0; i<j; i++){
co[i]=0;
for(a=0, k=0; k<n; k++)
if(((i>>k)%2)==1){ co[i]+=d[k]; a++; }
k=s-co[i];
if(k>=0){
if(a%2==0) cnt+=comb(n+k-1, n-1);
else cnt-=comb(n+k-1, n-1);
cnt%=200003;
}
}
cout<<cnt<<endl;
}
return 0;
}
my prog is giving the same output but still i am getting wrong ans
i am posting the code as i have no other option
#include<iostream>
using namespace std;
long long comb(long long n, long long r){
long long a[10], i, j;
for(i=0; i<r; i++) a=n-i;
for(i=r; i>1; i--)
for(j=0; j<r; j++)
if(a[j]%i==0){ a[j]/=i; break; }
i=1;
for(j=0; j<r; j++) i=(i*a[j])%200003;
return i;
}
void swap(long long& a, long long& b){
long long temp=a;
a=b;
b=temp;
}
int main(){
long long s, n, cases, lt[10][2], i, j, k, a, co[1024], d[10], cnt;
cin>>cases;
while(cases--){
cnt=0;
cin>>n>>s;
for(i=0; i<n; i++){
cin>>lt[0]>>lt[1];
if(lt[0]>lt[1]) swap(lt[0], lt[1]);
s-=lt[0];
d=lt[1]-lt[i][0]+1;
}
j=(1<<n);
for(i=0; i<j; i++){
co[i]=0;
for(a=0, k=0; k<n; k++)
if(((i>>k)%2)==1){ co[i]+=d[k]; a++; }
k=s-co[i];
if(k>=0){
if(a%2==0) cnt+=comb(n+k-1, n-1);
else cnt-=comb(n+k-1, n-1);
cnt%=200003;
}
}
cout<<cnt<<endl;
}
return 0;
}
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
try this case
answer is 50938
Code: Select all
1
6 5874
-521 5789
-7895 25
-123 456
987 10000
-1000 0
-10000 10000
-
- New poster
- Posts: 23
- Joined: Fri Sep 01, 2006 10:17 am
- Location: CSE, SUST
-
- New poster
- Posts: 20
- Joined: Mon May 28, 2007 4:36 pm
- Location: India
Hello ani_mitr86:
i think the following i/o set will be helpful to you:
Input:
i think the following i/o set will be helpful to you:
Input:
I got this output from my ac code:4
3 10
-1 3
2 4
6 7
1 6
0 5
2 6
0 5
0 4
10 50000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
hope you get ac.6
0
4
121326
-
- New poster
- Posts: 20
- Joined: Mon May 28, 2007 4:36 pm
- Location: India
-
- New poster
- Posts: 23
- Joined: Fri Sep 01, 2006 10:17 am
- Location: CSE, SUST
I have got the idea what should do. I use exclusion-inclusion to find the desired output.
What should I do for the following case:
Solutions are {1, 2, 3}, {1, 3, 2} .
Should I count twice for these solution set?
Can anyone explain why this case answer : 121326
Case:
What should I do for the following case:
Solutions are {1, 2, 3}, {1, 3, 2} .
Should I count twice for these solution set?
Can anyone explain why this case answer : 121326
Case:
Thnx again everyone who posts in this thread.10 50000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
Ofcourse.Piklu_sust wrote:I have got the idea what should do. I use exclusion-inclusion to find the desired output.
What should I do for the following case:
Solutions are {1, 2, 3}, {1, 3, 2} .
Should I count twice for these solution set?
What did you get? Because explaining this case would be too tough.Piklu_sust wrote:Can anyone explain why this case answer : 121326
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- New poster
- Posts: 23
- Joined: Fri Sep 01, 2006 10:17 am
- Location: CSE, SUST
Thanks Jan and everybody who posts in this thread.
After get several wrong answer I couldn't find my bug. So, ask this kind of question.
But now I got it accepted after finding silly bug in my code. problem is my nCr function. This function couldn't work with handing overflow.
Thanks again everybody.
After get several wrong answer I couldn't find my bug. So, ask this kind of question.
But now I got it accepted after finding silly bug in my code. problem is my nCr function. This function couldn't work with handing overflow.
Thanks again everybody.
-
- Learning poster
- Posts: 96
- Joined: Tue Apr 23, 2013 12:54 pm
Re: 11266 - Equations
This is my code .. .
My code gives following I/O
Input :
I tried but failed....
Help needed... pls
Code: Select all
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>
using namespace std;
/*------- Constants---- */
#define MX 1030
#define ll long long
#define ull unsigned long long
#define mod 200003
ll ara[15];
ll murikha,sum,n;
long long nCr(long long n, long long r){
long long a[10], i, j;
for(i=0; i<r; i++) a[i]=n-i;
for(i=r; i>1; i--)
for(j=0; j<r; j++)
if(a[j]%i==0){ a[j]/=i; break; }
i=1;
for(j=0; j<r; j++) i=(i*a[j])%200003;
return i%mod;
}
int main()
{
ll test,i,pri,res,low,high;
//printf("%lld",nCr(5, 4));
scanf("%lld",&test);
while (test--) {
scanf("%lld %lld",&n,&sum);
pri=0;
for(i=0;i<n;i++){
scanf("%lld %lld",&low,&high);
pri+= low;
ara[i]= high-low+1;
}
sum = sum -pri;
if(sum>=0)res = nCr(sum+n-1,n-1);
else {
printf("0\n");
continue;
}
sort(ara, ara+n);
ll p= 1<<n;
for (i=1; i<p; i++) {
int mask=1<<0;
int cnt=0;
int hurrah=0;
for(int j=0;j<n;j++){
mask=1<<j;
if(i&mask){
hurrah+= ara[j];
cnt++;
}
}
if(hurrah<=sum) {
if(cnt &1) res= (mod+res- nCr(sum-hurrah-1+n, n-1))%mod;
else res= (mod+res+ nCr(sum-hurrah-1+n, n-1))%mod;
}
//if(res>mod) res %=mod;
}
printf("%lld\n",res);
}
return 0;
}
Input :
- 4
3 10
-1 3
2 4
6 7
1 6
0 5
2 6
0 5
0 4
10 50000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
- 6
0
4
2291
I tried but failed....
Help needed... pls
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11266 - Equations
AC output for your input:
Code: Select all
6
0
4
121326
Check input and AC output for thousands of problems on uDebug!
Re: 11266 - Equations
My code passes all the testcases you guys gave, but still WA
Can someone help provide more testcases or find out what's wrong with my code?
Thanks!
Can someone help provide more testcases or find out what's wrong with my code?
Thanks!
Code: Select all
Code removed after AC
Last edited by arkidd on Wed Oct 22, 2014 7:48 pm, edited 1 time in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11266 - Equations
Input:AC output:
Code: Select all
50
3 46972
-5257 921
5414 8939
5461 5646
6 23143
-8238 -2321
-8821 6583
2913 7332
231 8528
6075 8971
-5437 1032
8 -10231
-4500 -306
4078 8151
-6891 6475
862 7646
2098 9704
-2633 2227
881 7561
13 3011
2 15513
-1816 5520
6473 9535
8 -26803
-5788 -2544
5075 5409
6463 9680
3406 6284
-692 6058
-7658 9676
9996 9998
-8888 -1033
1 -49524
-6675 -5493
9 -12361
3861 4191
2554 4448
-8221 4637
-3138 317
9451 9451
5222 9485
-6430 -2702
-4372 7984
-8912 1116
7 -22796
4794 5505
-5925 -5872
-6011 9270
-1895 1521
4897 7875
-1906 5427
4668 8740
3 47383
7116 9024
8770 9736
6180 9916
3 -38273
-604 5541
-9554 8522
-7185 8840
4 -14327
-9479 5465
-9045 -7537
-525 4409
-7012 -4170
3 23245
3130 7861
9172 9622
4470 9750
8 9745
-9706 452
4672 4991
-1314 1528
-3294 5291
-8008 -2343
-8522 -3721
4572 6127
-1223 5339
9 44144
-1691 2121
-3656 7609
5464 9956
-7754 -1419
4568 9611
4644 7478
3675 4910
6262 8386
7485 9504
1 2159
7801 7921
6 42012
-4807 9551
2441 3347
1253 1812
9664 9937
4496 9973
1226 7298
2 -37048
-1684 5296
3908 8133
9 -10266
-8383 -1675
-2909 5359
9744 9968
-2986 3657
2513 5319
-2015 2606
-6107 -1967
5397 9750
4261 9113
6 -11226
-1491 5419
-7564 9062
4289 6131
2642 8779
3711 8384
-6779 -5641
2 -17595
-8128 -4193
-9022 -6688
9 -31974
7054 8389
4919 7860
-3447 8421
9814 9882
2817 5299
3291 4141
9060 9321
-3523 3775
200 9420
8 -21525
4016 9417
-3320 -3174
-39 7193
3146 9933
-8842 8614
-5570 -1064
3696 8893
-7121 7337
1 -14374
-5217 -3114
1 -32139
4968 7877
2 16293
-1775 6899
-5717 8333
5 42921
3139 7632
-551 2720
-8254 -1862
4038 5673
3884 8203
10 -32120
-1021 1374
1549 7332
7851 7971
6006 6893
-8153 2884
7383 9438
6138 7068
8252 8751
-3462 5484
-3840 152
6 11052
-3504 -1036
-8076 3943
-7389 721
165 3542
828 9084
-7394 -4055
2 -3637
-7570 -152
404 7732
4 -49219
1088 7788
-9166 -493
-6352 1288
4105 9715
7 47833
-862 5417
-1949 819
2683 3778
4311 8911
-4448 -3353
-4288 1820
1236 5064
8 46412
-2944 5133
-8336 -6877
7967 8854
-68 1256
-4189 4930
3615 3925
-2892 6573
1981 8604
2 19046
8470 9289
8136 8204
9 38395
-8361 -119
9288 9968
-2682 6340
262 3272
-4475 -2861
-5201 540
-1602 3485
-266 4469
2031 3119
9 -26708
-7385 201
-7174 8187
7300 9838
5806 8349
-8483 -2502
-3436 -936
-5753 4431
-6527 3456
-5084 4978
8 -34365
3102 5256
-8625 6577
-810 4314
5708 9809
-8101 9216
-5919 -1518
822 9593
1104 2172
9 39503
998 8318
-4060 7850
-2240 7231
-2867 6927
-4528 9880
2409 8673
-3788 -1654
3313 5628
-2991 8325
1 -6409
-2556 3502
1 -20390
6272 6560
9 2923
96 4189
8006 8532
-3878 5793
8655 9139
7853 8730
-1164 9354
-8442 5822
-4102 2001
-3245 6708
2 36581
-4566 709
-6077 7022
7 27468
1845 6691
-4111 5400
-1941 -859
-7043 -985
7079 9719
9 5993
-3317 6904
10 -4203
8628 9906
-9516 -8968
-4269 -664
-2543 5594
-5275 1415
-8815 -6803
-511 7058
-9997 -7791
-3718 -1317
-7228 8200
2 19952
-5874 -947
-7749 5274
6 -21150
3159 9275
1894 5055
-947 4835
-9969 2938
-6661 -3096
-2966 -1771
2 -11801
-5847 -2450
7538 9946
6 47134
7490 8505
-4399 142
8308 8340
3204 7424
5025 7620
6934 8155
10 43111
-6311 -2125
-1353 4491
-1136 6063
8651 8800
-2509 3890
5279 8287
-2500 1908
-6759 8729
-5924 4011
-7559 3180
10 -36288
567 8020
-1252 6110
-2764 1460
-8785 -1016
-8051 -5534
-3657 4850
6066 6913
24 6381
-7734 -3090
-1372 7299
6 -22110
4081 4084
7154 9682
-5707 9131
8996 9515
-2216 4386
-9987 1574
Code: Select all
0
52649
0
0
0
0
0
0
0
0
61777
97540
73720
40112
0
0
0
0
0
0
0
0
0
0
0
0
0
111155
3530
0
0
0
0
0
90898
0
166425
0
0
0
0
102431
82223
0
0
0
0
73360
0
0
Check input and AC output for thousands of problems on uDebug!