D.O.P.E Online Judge! prob:-Modulus
–AC–
#include
int main()
{
long long int a,b,res,tmp,i,j,k,c;
for(k=0;k<10;k++){
scanf("%lld%lld%lld",&a,&b,&c);
res=a%c;
res=(res*b)%c;
printf("%lld\n",res);
}
return 0;
}
D.O.P.E Online Judge! prob:-Modulus February 28, 2010
TJU 3288. Stockholm Numbers December 8, 2009
TJU 3288. Stockholm Numbers
original thinking implemented
1->1*2+1=3 //1 has odd parity
2->2*2+1=5//2has odd parity
3->3*2=6//3has even parity
4->4*2+1=9//4has odd parity
5->5*2=10//5has even parity
and so on
……………….
--AC--
#include<stdio.h>
int main()
{
long long int i,j,k,K,tmp,rem,cases;
scanf("%lld",&cases);
while(cases--)
{
scanf("%lld",&K);
j=0;
tmp=K;
while(K>0)
{
rem=K%2;
if(rem==1)
++j;
K=K/2;
}
if(j%2==0)
printf("%lld\n",2*tmp);
else
printf("%lld\n",2*tmp+1);
}
return 0;
}
TJU 3150. Sixth Grade Math November 13, 2009
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int f_hcf(int n1,int n2)
{
if(n1==0) return n2;
else if(n2==0) return n1;
else if(n1==n2) return n1;
if(n1>n2) return f_hcf(n1%n2,n2);
else if(n1<n2) return f_hcf(n1,n2%n1);
return 0;
}
int f_lcm(int n1,int n2)//this function can remove to just get lcm=(n1*n1)/hcf
{
int i,j,k1,k2;
int hcf=f_hcf(n1,n2);
if(n1>n2&&hcf==1) return n1*n2;
else if(n1<n2&&hcf==1) return n2*n1;
else if(n1==n2) return n1;
while(n1!=n2)
{
if(n1>n2) {
k1=n2/hcf;
k2=n1/hcf;
n1=n1*k1;
n2=n2*k2;
}
else if(n2>n1)
{
k1=n2/hcf;
k2=n1/hcf;
n1=n1*k1;
n2=n2*k2;
}
}
if(n1==n2) return n1;
return 0;
}
int main()
{
int i,j,k,cases;
int n1,n2;
int lcm,hcf;
scanf("%d",&cases);
k=1;
while(cases--)
{
scanf("%d %d",&n1,&n2);
hcf=f_hcf(n1,n2);
lcm=f_lcm(n1,n2);
printf("%d %d %d\n",k++,lcm,hcf);
}
return 0;
}
———-2nd Verssion—–
AC
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int f_hcf(int n1,int n2)
{
if(n1==0) return n2;
else if(n2==0) return n1;
else if(n1==n2) return n1;
if(n1>n2) return f_hcf(n1%n2,n2);
else if(n1<n2) return f_hcf(n1,n2%n1);
return 0;
}
int main()
{
int i,j,k,cases;
int n1,n2;
int lcm,hcf;
scanf("%d",&cases);
k=1;
while(cases--)
{
scanf("%d %d",&n1,&n2);
hcf=f_hcf(n1,n2);
lcm=(n1*n2)/hcf;
printf("%d %d %d\n",k++,lcm,hcf);
}
return 0;
}
SPOJ 4872. Good Sequence October 10, 2009
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
int i,j,k,cases;
int temp,rem,count;
int n[1000];
scanf("%d",&cases);
//calculating good number
j=0;
for(i=1;i<501;i++)
{
temp=i;
count=1;
while(temp>0)
{
rem=temp%2;
if(rem==1) count++;
temp=temp/2;
}
if(count%2==0) {
//printf("%d ",i);
n[j++]=i;
}
}
while(cases--)
{
scanf("%d",&j);
printf("%d\n",n[j-1]);
}
return 0;
}
SPOJ 4906. Pythagorean Triples October 10, 2009
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{
int cases,i,j,k;
int a,b,c;
float tmp;
scanf("%d",&cases);
while(cases--)
{
scanf("%d%d",&a,&b);
j=a*a+b*b;
if((float)sqrt(j)==(int)sqrt(j))
{
printf("YES "); printf("%d\n",(int)sqrt(j));
}
else
printf("NO\n");
}
return 0;
}
ACM-ICPC Japan Domestic 2006 October 2, 2009
1.Problem A – Dirichlet’s Theorem on Arithmetic Progressions
2.Problem B – Organize Your Train part II
3.Problem C – Hexerpents of Hexwamp
ACM-ICPC JAPAN Domestic 2005 October 2, 2009
2Problem B – Polygonal Line Search
4Problem D – Traveling by Stagecoach
Exploring Caves October 2, 2009
ACM International Collegiate Programming Contest
Japan Domestic, 2002-10-02
Problem A
Exploring Caves
There are many caves deep in mountains found in the countryside. In legend, each cave has a treasure hidden within the farthest room from the cave’s entrance. The Shogun has ordered his Samurais to explore these caves with Karakuri dolls (robots) and to find all treasures. These robots move in the caves and log relative distances and directions between rooms.
Each room in a cave is mapped to a point on an integer grid (x, y >= 0). For each cave, the robot always starts from its entrance, runs along the grid and returns to the entrance (which also serves as the exit). The treasure in each cave is hidden in the farthest room from the entrance, using Euclid distance for measurement, i.e. the distance of the room at point (x, y) from the entrance (0, 0) is defined as the square root of (x*x+y*y). If more than one room has the same farthest distance from the entrance, the treasure is hidden in the room having the greatest value of x. While the robot explores a cave, it records how it has moved. Each time it takes a new direction at a room, it notes the difference (dx, dy) from the last time it changed its direction. For example, suppose the robot is currently in the room at point (2, 4). If it moves to room (6, 4), the robot records (4, 0), i.e. dx=6-2 and dy=4-4. The first data is defined as the difference from the entrance. The following figure shows rooms in the first cave of the Sample Input. In the figure, the farthest room is the square root of 61 distant from the entrance.
Based on the records that the robots bring back, your job is to determine the rooms where treasures are hidden.
Input
In the first line of the input, an integer N showing the number of caves in the input is given. Integers dxi and dyi are i-th data showing the differences between rooms. Note that since the robot moves along the grid, either dxi or dyi is zero. An integer pair dxi = dyi = 0 signals the end of one cave’s data which means the robot finished the exploration for the cave and returned back to the entrance. The coordinates are limited to (0,0)-(1000,1000).
Output
Print the position (x, y) of the treasure room on a line for each cave.
Sample Input
3
1 0
0 1
-1 0
1 0
0 5
-1 0
0 -1
5 0
0 1
0 -1
1 0
0 -4
-3 0
0 3
2 0
0 -2
-1 0
0 1
0 -1
1 0
0 2
-2 0
0 -3
3 0
0 4
-4 0
0 -5
-2 0
0 0
1 0
-1 0
0 0
2 0
0 1
-1 0
0 1
-1 0
0 -2
0 0
Output for the Sample Input
6 5
1 0
2 1
The ACM ICPC
Types of problem in prog. contest October 1, 2009
there are only 16 types of programming contest problems! Furthermore, the top several comprise almost 80% of the problems seen at the IOI. Here they are:
* Dynamic Programming
* Greedy
* Complete Search
* Flood Fill
* Shortest Path
* Recursive Search Techniques
* Minimum Spanning Tree
* Knapsack
* Computational Geometry
* Network Flow
* Eulerian Path
* Two-Dimensional Convex Hull
* BigNums
* Heuristic Search
* Approximate Search
* Ad Hoc Problems
The most challenging problems are Combination Problems which involve a loop (combinations, subsets, etc.) around one of the above algorithms – or even a loop of one algorithm with another inside it. These seem extraordinarily tricky to get right, even though conceptually they are “obvious”.
If you can master solving just 40% of these problem types, you can almost guarantee a silver medal at the IOI. Mastering 80% moves you into the gold range almost for sure. Of course, `mastery’ is a tough nut to crack! We’ll be supplying a plethora of problems so that you can hone your skills in the quest for international fame.
source-baidu blog
Recent Comments