ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1021. Sacrament of the Sum

Posted by hit 20 Nov 2015 20:25
#include<stdio.h>
#include<stdlib.h>
int main()
{
int m,n,a[50000],b[50000],i,j,p,c;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d",&b[i]);
}
for(j=0;j<n;j++)
{
for(p=0;p<m;p++)
{
c=a[j]+b[p];

if(c==10000)
{
printf("YES");
exit(0);
}
}
}
printf("NO");
return 0;
}
Posted by Hexo 20 Nov 2015 23:45
in my mind, two loops is not required. Try to use binary search in sorted array.
steps:
1.Take from first array the number;
2.1000-[this number]
3.find 1000-[this number] in second array(use binary search)

This way, you have only one loop.

Edited by author 20.11.2015 23:45

Edited by author 20.11.2015 23:45
No subject
Posted by Hunter 27 Apr 2016 14:58
Thanks a lot!!!