Chatbox

Các bạn vui lòng dùng từ ngữ lịch sự và có văn hóa,sử dụng Tiếng Việt có dấu chuẩn. Chúc các bạn vui vẻ!
07/10/2013 15:10 # 1
vnttqb
Cấp độ: 13 - Kỹ năng: 8

Kinh nghiệm: 5/130 (4%)
Kĩ năng: 39/80 (49%)
Ngày gia nhập: 21/03/2011
Bài gởi: 785
Được cảm ơn: 319
[olp Tin học] Tổng hợp bài giải giao lưu với ĐH FPT


B. Nearest Fraction
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given three positive integers x, y, n. Your task is to find the nearest fraction to fraction  whose denominator is no more than n.

Formally, you should find such pair of integers a, b (1 ≤ b ≤ n; 0 ≤ a) that the value  is as minimal as possible.

If there are multiple "nearest" fractions, choose the one with the minimum denominator. If there are multiple "nearest" fractions with the minimum denominator, choose the one with the minimum numerator.

Input

A single line contains three integers x, y, n (1 ≤ x, y, n ≤ 105).

Output

Print the required fraction in the format "a/b" (without quotes).

Sample test(s)
input
3 7 6
output
2/5
input
7 2 4
output
7/2
 

---________________________________________________________________________________________________

 

#include<iostream>
#include<stdio.h>
 
using namespace std;
long long a,b1,n;
long long x,y;
float T(float a)
{
if (a < 0)
a = a*(-1);
return a;
}
 
int MIN(float a, float b, float c)
{
if ( a<=b && a<= c)
return 1;
if ( b<=a && b<= c)
return 2;
if ( c<=b && c<= a)
return 3;
}
 
int main()
{
// freopen("in.txt","r",stdin);
    cin>>x>>y>>n;
double Min = 100000;
for (int b = 1; b <= n; b++)
{
long long a1= (x*b)/y;
long long a0= a1-1;
long long a2= a1+1;
 
double t0= T(x*1.0/y - a0*1.0/b );
double t1= T(x*1.0/y - a1*1.0/b );
double t2= T(x*1.0/y - a2*1.0/b );
 
int c = MIN ( t0,t1,t2);
 
if ( c == 1 && t0 < Min)
{
a= a0;
b1 = b;
Min = t0;
}
if ( c == 2 && t1 < Min)
{
a= a1; b1 = b;
Min = t1;
}
if ( c == 3 && t2 < Min)
{
a= a2; b1 = b;
Min = t2;
}
}
 
cout<<a<<"/"<<b1;
 
}


======================================================================================================

Cuộc đời là một dòng sông. Ai không bơi thì chết. 
 

Name: Tien (Tory) TRAN
Email: TranTien29@gmail.com


 
07/10/2013 16:10 # 2
vnttqb
Cấp độ: 13 - Kỹ năng: 8

Kinh nghiệm: 5/130 (4%)
Kĩ năng: 39/80 (49%)
Ngày gia nhập: 21/03/2011
Bài gởi: 785
Được cảm ơn: 319
Phản hồi: [olp Tin học] Tổng hợp bài giải giao lưu với ĐH FPT


B. Xenia and Ringroad
time limit per test
 2 seconds
memory limit per test
 256 megabytes
input
 standard input
output
 standard output

Xenia lives in a city that has n houses built along the main ringroad. The ringroad houses are numbered 1 through n in the clockwise order. The ringroad traffic is one way and also is clockwise.

Xenia has recently moved into the ringroad house number 1. As a result, she's got m things to do. In order to complete the i-th task, she needs to be in the house number ai and complete all tasks with numbers less than i. Initially, Xenia is in the house number 1, find the minimum time she needs to complete all her tasks if moving from a house to a neighboring one along the ringroad takes one unit of time.

Input

The first line contains two integers n and m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105). The second line contains m integers a1, a2, ..., am (1 ≤ ai ≤ n). Note that Xenia can have multiple consecutive tasks in one house.

Output

Print a single integer — the time Xenia needs to complete all tasks.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cincout streams or the %I64dspecifier.

Sample test(s)
input
4 3
3 2 3
output
6
input
4 3
2 3 3
output
2
Note

In the first test example the sequence of Xenia's moves along the ringroad looks as follows: 1 → 2 → 3 → 4 → 1 → 2 → 3. This is optimal sequence. So, she needs 6 time units.

 

#include<iostream>
#include<stdio.h>
 
using namespace std;
long long n,m;
long long x; // vi tri dang dung
long long sum  = 0;
long long tinh(long long d)
{
if (d >= x)
return d-x;
else
return (n-x  + d);
 
}
int main()
{
// freopen("in.txt","r",stdin);
cin>>n>>m;
x = 1;
for ( int i= 1; i<= m;i++ )
{
int d;
cin>>d;
 
sum += tinh(d);
 
// cout<<"\n di tu "<<x <<"toi"<<d<< "--" <<sum<<"\n";
x = d;
}
cout<<sum;
}
 
 


======================================================================================================

Cuộc đời là một dòng sông. Ai không bơi thì chết. 
 

Name: Tien (Tory) TRAN
Email: TranTien29@gmail.com


 
Các thành viên đã Thank vnttqb vì Bài viết có ích:
07/10/2013 21:10 # 3
vnttqb
Cấp độ: 13 - Kỹ năng: 8

Kinh nghiệm: 5/130 (4%)
Kĩ năng: 39/80 (49%)
Ngày gia nhập: 21/03/2011
Bài gởi: 785
Được cảm ơn: 319
Phản hồi: [olp Tin học] Tổng hợp bài giải giao lưu với ĐH FPT


2299. Xếp hàng mua vé
Mã bài: NKTICK
 
Có N người sắp hàng mua vé dự buổi hoà nhạc. Ta đánh số họ từ 1 đến N theo thứ tự đứng trong hàng. 
Mỗi người cần mua một vé, song người bán vé được phép bán cho mỗi người tối đa hai vé. 
Vì thế, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé.
Biết ti là thời gian cần thiết để người i mua xong vé cho mình. Nếu người i+1 rời khỏi hàng và nhờ người i mua hộ vé
thì thời gian để người thứ i mua được vé cho cả hai người là ri.
Yêu cầu: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất.
 
Dữ liệu
Dòng đầu tiên chứa số N (1 ≤ N ≤ 60000).
Dòng thứ 2 ghi N số nguyên dương t1, t2, ..., tN. (1 ≤ ti ≤ 30000)
Dòng thứ ba ghi N-1 số nguyên dương r1, r2, ..., rN-1. (1 ≤ ri ≤ 30000)
Kết qủa
In ra tổng thời gian phục vụ nhỏ nhất.
Ví dụ
Dữ liệu:
5
2 5 7 8 4
4 9 10 10 
 
Kết qủa
18
 
Dữ liệu:
4
5 7 8 4
50 50 50 
 
Kết qủa
24
 
__________________________________________
 
#include<iostream>
//#include<stdio.h>
 
using namespace std;
 
int t[60010];
int r[60010];
int F[60010];
long long MIN(long long a,long long b)
{
return (a<b)?a:b;
}
 
int main()
{
int n;
// freopen("in.txt","r",stdin);
cin>>n;
for ( int i = 1; i<=n; i++)
cin>>t[i];
for ( int i = 1; i<=n; i++)
cin>>r[i];
 
F[n]= t[n];
F[n+1] =0;
for (int i = n-1; i>=1;i--)
{
long long th1 = F[i+1]+ t[i];
long long th2 = F[i+2] + r[i];
F[i] = MIN(th1,th2);
 
cout<<F[1];
 
}
 


======================================================================================================

Cuộc đời là một dòng sông. Ai không bơi thì chết. 
 

Name: Tien (Tory) TRAN
Email: TranTien29@gmail.com


 
Các thành viên đã Thank vnttqb vì Bài viết có ích:
08/10/2013 20:10 # 4
vnttqb
Cấp độ: 13 - Kỹ năng: 8

Kinh nghiệm: 5/130 (4%)
Kĩ năng: 39/80 (49%)
Ngày gia nhập: 21/03/2011
Bài gởi: 785
Được cảm ơn: 319
Phản hồi: [olp Tin học] Tổng hợp bài giải giao lưu với ĐH FPT


A. Jeff and Digits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jeff's got n cards, each card contains either digit 0, or digit 5. Jeff can choose several cards and put them in a line so that he gets some number. What is the largest possible number divisible by 90 Jeff can make from the cards he's got?

Jeff must make the number without leading zero. At that, we assume that number 0 doesn't contain any leading zeroes. Jeff doesn't have to use all the cards.

Input

The first line contains integer n (1 ≤ n ≤ 103). The next line contains n integers a1a2...an (ai = 0 or ai = 5). Number ai represents the digit that is written on the i-th card.

Output

In a single line print the answer to the problem — the maximum number, divisible by 90. If you can't make any divisible by 90 number from the cards, print -1.

Sample test(s)
input
4
5 0 5 0
output
0
input
11
5 5 5 5 5 5 5 5 0 5 5
output
5555555550
Note

In the first test you can make only one number that is a multiple of 90 — 0.

In the second test you can make number 5555555550, it is a multiple of 90.

___________________________________________________________________________________

 

#include<iostream>
 
using namespace std;
 
int main()
{
int n,x,d0,d5;
cin>>n;
d0 = d5 = 0;
for ( int i = 1; i<= n;i++)
{
cin>>x;
d5 += x/5;
}
d0 = n-d5;
 
x = d5/9;
 
//cout<<x<<" "<<d0<<"  "<<d5;
if ( d0 == 0 ) // && x <= 1)
cout<<"-1";
else
if ( x < 1 && d0 !=0 )
cout<<"0";
else
if ( x > 0 )
{
x = x*9;
for ( int i = 1 ; i<= x; i++)
cout<<"5";
for ( int i = 1; i<= d0; i++)
cout<<"0";
}
// cout<<"FINSH";
}

 



======================================================================================================

Cuộc đời là một dòng sông. Ai không bơi thì chết. 
 

Name: Tien (Tory) TRAN
Email: TranTien29@gmail.com


 
08/10/2013 20:10 # 5
vnttqb
Cấp độ: 13 - Kỹ năng: 8

Kinh nghiệm: 5/130 (4%)
Kĩ năng: 39/80 (49%)
Ngày gia nhập: 21/03/2011
Bài gởi: 785
Được cảm ơn: 319
Phản hồi: [olp Tin học] Tổng hợp bài giải giao lưu với ĐH FPT


A. TL
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Valera wanted to prepare a Codesecrof round. He's already got one problem and he wants to set a time limit (TL) on it.

Valera has written n correct solutions. For each correct solution, he knows its running time (in seconds). Valera has also wrote m wrong solutions and for each wrong solution he knows its running time (in seconds).

Let's suppose that Valera will set v seconds TL in the problem. Then we can say that a solution passes the system testing if its running time is at most v seconds. We can also say that a solution passes the system testing with some "extra" time if for its running time, aseconds, an inequality 2a ≤ v holds.

As a result, Valera decided to set v seconds TL, that the following conditions are met:

 

  1. v is a positive integer;
  2. all correct solutions pass the system testing;
  3. at least one correct solution passes the system testing with some "extra" time;
  4. all wrong solutions do not pass the system testing;
  5. value v is minimum among all TLs, for which points 1234 hold.

 

Help Valera and find the most suitable TL or else state that such TL doesn't exist.

Input

The first line contains two integers nm (1 ≤ n, m ≤ 100). The second line contains n space-separated positive integers a1, a2, ..., an(1 ≤ ai ≤ 100) — the running time of each of the n correct solutions in seconds. The third line contains m space-separated positive integers b1, b2, ..., bm (1 ≤ bi ≤ 100) — the running time of each of m wrong solutions in seconds.

Output

If there is a valid TL value, print it. Otherwise, print -1.

Sample test(s)
input
3 6
4 5 2
8 9 6 10 7 11
output
5
input
3 1
3 4 5
6
output
-1
 

 

________________________________________________________________________________________
 

#include<iostream>
 
using namespace std;
 
int main()
{
int cd,cs;
int maxcd,mincd;
int mincs;
int x;
 
 
cin>>cd >>cs;
 
maxcd =  -1;
mincd = mincs = 2001;
for ( int i = 1; i<= cd; i++)
{
cin>>x;
if ( x < mincd )
mincd = x;
else
if ( x > maxcd )
maxcd = x;
}
 
for ( int i = 1; i<= cs; i++)
{
cin>>x;
if ( x < mincs )
mincs = x;
 
}
// cout<<"MAX Dung "<< maxcd<<" MIN CD = "<<mincd;
 
// cout<<"\nMAX SAI "<< maxcs<<" MIN Cs = "<<mincs;
int v = -1;
for ( int i = maxcd ; i < mincs ; i++)
{
if ( mincd * 2 <= i )
{
v = i;
break;
}
}
cout<<v;
 
}


======================================================================================================

Cuộc đời là một dòng sông. Ai không bơi thì chết. 
 

Name: Tien (Tory) TRAN
Email: TranTien29@gmail.com


 
Các thành viên đã Thank vnttqb vì Bài viết có ích:
09/10/2013 15:10 # 6
vnttqb
Cấp độ: 13 - Kỹ năng: 8

Kinh nghiệm: 5/130 (4%)
Kĩ năng: 39/80 (49%)
Ngày gia nhập: 21/03/2011
Bài gởi: 785
Được cảm ơn: 319
Phản hồi: [olp Tin học] Tổng hợp bài giải giao lưu với ĐH FPT


Đề bài: Xuất ra dãy FIBO từ 1-- N;

với định nghĩa  Fibo(0) = 1 ; Fibo(1) = 1; --> Fibo(n) = Fibo(n-1) + Fibo(n-2);



Cách 1. Dùng đệ quy thường. 
 
#include<iostream>
 
using namespace std;
 
 
long long FIBO(long long n)
{
if ( n <= 1)
return 1;
return FIBO(n-1)+FIBO(n-2);
}
 
int main()
{
 
for ( int i = 0; i<= 10; i++)
 cout<<"FIBO ["<<i<<"]\t"<<FIBO(i)<<endl;
 
}


 

Cách 2: Đệ quy có nhớ

#include<iostream>
 
using namespace std;
 
long long F[100000];
 
long long FIBO(long long n)
{
if ( n <= 1)
return 1;
if ( F[n] != 0 ) 
return F[n];
else
F[n] = FIBO(n-1)+ FIBO(n-2);
return F[n];
}
 
int main()
{
F[0] = 1;
F[1] = 1;
 
for ( int i = 0; i<= 80; i++)
 cout<<"FIBO ["<<i<<"]\t"<<FIBO(i)<<endl;
 
 
}
 


======================================================================================================

Cuộc đời là một dòng sông. Ai không bơi thì chết. 
 

Name: Tien (Tory) TRAN
Email: TranTien29@gmail.com


 
Copyright© Đại học Duy Tân 2010 - 2019